Page Menu
Home
WickedGov Phorge
Search
Configure Global Search
Log In
Files
F6085275
MutableFST.php
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Size
7 KB
Referenced Files
None
Subscribers
None
MutableFST.php
View Options
<?php
namespace
Wikimedia\LangConv\Construct
;
use
Wikimedia\Assert\Assert
;
/**
* A mutable FST.
*/
class
MutableFST
{
/** Special alphabet symbol for `nothing` used in AT&T format FST files. */
public
const
EPSILON
=
'@0@'
;
/** Special alphabet symbol for upper-side `?` used in AT&T format FST files. */
public
const
UNKNOWN
=
'@_UNKNOWN_SYMBOL_@'
;
/** Special alphabet symbol for lower-side `?` used in AT&T format FST files. */
public
const
IDENTITY
=
'@_IDENTITY_SYMBOL_@'
;
private
$alphabet
=
[];
private
$states
=
[];
/**
* Create a new MutableFST with the given alphabet.
* @param string[] $alphabet
*/
public
function
__construct
(
array
$alphabet
)
{
// Create start state
$this
->
newState
();
// Set up alphabet
foreach
(
$alphabet
as
$tok
)
{
$this
->
alphabet
[
$tok
]
=
true
;
}
$this
->
alphabet
[
self
::
EPSILON
]
=
true
;
$this
->
alphabet
[
self
::
IDENTITY
]
=
true
;
$this
->
alphabet
[
self
::
UNKNOWN
]
=
true
;
}
/**
* Add a new state to this FST.
* @return State the new state.
*/
public
function
newState
():
State
{
$id
=
count
(
$this
->
states
);
$s
=
$this
->
states
[]
=
new
State
(
$id
);
return
$s
;
}
/**
* Return the start state of this FST.
* @return State the start state.
*/
public
function
getStartState
():
State
{
return
$this
->
states
[
0
];
}
/**
* Apply the given FST to the array of input tokens. Symbols in
* 'upper' are matched and symbols in 'lower' are emitted.
* @param string[] $input
* @return array<array<string>>
*/
public
function
applyDown
(
array
$input
):
array
{
return
$this
->
applyUpDown
(
$input
,
true
);
}
/**
* Apply the given FST to the array of input tokens. Symbols in
* 'lower' are matched and symbols in 'upper' are emitted.
* @param string[] $input
* @return array<array<string>>
*/
public
function
applyUp
(
array
$input
):
array
{
return
$this
->
applyUpDown
(
$input
,
false
);
}
/**
* Apply the given FST to the array of input tokens.
* @param string[] $input array of input tokens
* @param bool $isDown Whether to apply 'up' or 'down'
* @return array<array<string>>
*/
private
function
applyUpDown
(
array
$input
,
bool
$isDown
):
array
{
// This is an extremely simple implementation, made for validating
// the FST not efficient execution.
$results
=
[];
$stack
=
[];
$flagRE
=
'/^@([PNRDCU])[.]([^.@]+)(?:[.]([^@]+))?@$/D'
;
$addTok
=
static
function
(
$toks
,
$t
)
use
(
$flagRE
)
{
if
(
$t
===
self
::
EPSILON
||
preg_match
(
$flagRE
,
$t
)
)
{
// skip token
}
else
{
$toks
[]
=
$t
;
}
return
$toks
;
};
$stack
[]
=
[
$this
->
getStartState
(),
0
,
[],
[]
];
while
(
count
(
$stack
)
>
0
)
{
[
$state
,
$pos
,
$flags
,
$emitted
]
=
array_pop
(
$stack
);
$tok
=
$pos
<
count
(
$input
)
?
$input
[
$pos
]
:
null
;
if
(
$tok
!==
null
&&
!
isset
(
$this
->
alphabet
[
$tok
]
)
)
{
$tok
=
self
::
UNKNOWN
;
}
foreach
(
$state
->
edges
as
$e
)
{
if
(
$isDown
)
{
$match
=
$e
->
upper
;
$output
=
$e
->
lower
;
}
else
{
$match
=
$e
->
lower
;
$output
=
$e
->
upper
;
}
// Treat IDENTITY and UNKNOWN as identical (applyDown/applyUp)
if
(
$match
===
self
::
IDENTITY
)
{
$match
=
self
::
UNKNOWN
;
}
if
(
$output
===
self
::
UNKNOWN
)
{
$output
=
self
::
IDENTITY
;
}
// Does this edge match?
if
(
$output
===
self
::
IDENTITY
&&
$tok
!==
null
)
{
$output
=
$input
[
$pos
];
}
if
(
$match
===
self
::
EPSILON
)
{
$stack
[]
=
[
$e
->
to
,
$pos
,
$flags
,
$addTok
(
$emitted
,
$output
)
];
}
elseif
(
preg_match
(
$flagRE
,
$match
,
$flagInfo
,
PREG_UNMATCHED_AS_NULL
)
===
1
)
{
$op
=
$flagInfo
[
1
];
$feature
=
$flagInfo
[
2
];
$value
=
$flagInfo
[
3
]
??
null
;
$f
=
$flags
[
$feature
]
??
null
;
if
(
$op
===
'P'
)
{
Assert
::
invariant
(
$value
!==
null
,
"P not C!"
);
$flags
[
$feature
]
=
$value
;
}
elseif
(
$op
===
'C'
)
{
Assert
::
invariant
(
$value
===
null
,
"C not P!"
);
$flags
[
$feature
]
=
null
;
}
elseif
(
$op
===
'N'
)
{
// @phan-suppress-next-line PhanImpossibleCondition
Assert
::
invariant
(
false
,
'N not supported'
);
}
elseif
(
$op
===
'R'
||
$op
===
'D'
)
{
$m
=
(
$value
===
null
)
?
(
$f
!==
null
)
:
(
$f
===
$value
);
if
(
$op
===
'R'
?
(
!
$m
)
:
$m
)
{
continue
;
}
}
elseif
(
$op
===
'U'
)
{
Assert
::
invariant
(
$value
!==
null
,
"Unify with what?"
);
if
(
$f
===
null
||
$f
===
$value
)
{
$flags
[
$feature
]
=
$value
;
}
else
{
continue
;
}
}
$stack
[]
=
[
$e
->
to
,
$pos
,
$flags
,
$addTok
(
$emitted
,
$output
)
];
}
elseif
(
$match
===
$tok
&&
$tok
!==
null
)
{
$stack
[]
=
[
$e
->
to
,
$pos
+
1
,
$flags
,
$addTok
(
$emitted
,
$output
)
];
}
}
if
(
$tok
===
null
&&
$state
->
isFinal
)
{
$results
[]
=
$emitted
;
}
}
return
$results
;
}
/**
* Perform simple optimization on the FST, trimming unreachable states
* and attempting to combine edges containing epsilons.
*/
public
function
optimize
():
void
{
$reachable
=
[];
$stateWorklist
=
[];
$stateWorklist
[
$this
->
getStartState
()->
id
]
=
$this
->
getStartState
();
while
(
count
(
$stateWorklist
)
>
0
)
{
$state
=
array_pop
(
$stateWorklist
);
$reachable
[
$state
->
id
]
=
true
;
$edgeWorklist
=
$state
->
edges
;
// worklist
while
(
count
(
$edgeWorklist
)
>
0
)
{
$edge
=
array_pop
(
$edgeWorklist
);
if
(
$edge
===
null
)
{
continue
;
/* removed edge */
}
if
(
$edge
->
to
->
isFinal
)
{
if
(
!
isset
(
$reachable
[
$edge
->
to
->
id
]
)
)
{
$stateWorklist
[
$edge
->
to
->
id
]
=
$edge
->
to
;
}
continue
;
}
$nEdge
=
count
(
$edge
->
to
->
edges
);
if
(
$nEdge
===
0
)
{
$state
->
edges
[
$edge
->
id
]
=
null
;
// remove
// XXX requeue all states which point to this
continue
;
}
elseif
(
$nEdge
===
1
)
{
$nextEdge
=
$edge
->
to
->
edges
[
0
];
if
(
$nextEdge
===
null
)
{
/* deleted. Fall through. */
}
elseif
(
$edge
->
lower
===
self
::
EPSILON
&&
$nextEdge
->
upper
===
self
::
EPSILON
)
{
$edge
->
lower
=
$nextEdge
->
lower
;
$edge
->
to
=
$nextEdge
->
to
;
$edgeWorklist
[]
=
$edge
;
continue
;
}
elseif
(
$edge
->
upper
===
self
::
EPSILON
&&
$nextEdge
->
lower
==
self
::
EPSILON
)
{
$edge
->
upper
=
$nextEdge
->
upper
;
$edge
->
to
=
$nextEdge
->
to
;
$edgeWorklist
[]
=
$edge
;
continue
;
}
elseif
(
$edge
->
upper
===
self
::
EPSILON
&&
$edge
->
lower
===
self
::
EPSILON
)
{
$edge
->
upper
=
$nextEdge
->
upper
;
$edge
->
lower
=
$nextEdge
->
lower
;
$edge
->
to
=
$nextEdge
->
to
;
$edgeWorklist
[]
=
$edge
;
continue
;
}
elseif
(
$nextEdge
->
upper
===
self
::
EPSILON
&&
$nextEdge
->
lower
===
self
::
EPSILON
)
{
$edge
->
to
=
$nextEdge
->
to
;
$edgeWorklist
[]
=
$edge
;
continue
;
}
}
// fall through
if
(
!
isset
(
$reachable
[
$edge
->
to
->
id
]
)
)
{
$stateWorklist
[
$edge
->
to
->
id
]
=
$edge
->
to
;
}
}
}
// Renumber states and edges
$j
=
0
;
for
(
$i
=
0
;
$i
<
count
(
$this
->
states
);
$i
++
)
{
$s
=
$this
->
states
[
$i
];
if
(
isset
(
$reachable
[
$s
->
id
]
)
)
{
$s
->
id
=
$j
++;
$this
->
states
[
$s
->
id
]
=
$s
;
// renumber edges
$k
=
0
;
for
(
$l
=
0
;
$l
<
count
(
$s
->
edges
);
$l
++
)
{
$e
=
$s
->
edges
[
$l
];
if
(
$e
!==
null
)
{
$e
->
id
=
$k
++;
$s
->
edges
[
$e
->
id
]
=
$e
;
}
}
array_splice
(
$s
->
edges
,
$k
);
}
}
array_splice
(
$this
->
states
,
$j
);
}
/**
* Write an AT&T format description of this FST to the given filehandle.
* @param resource $handle
*/
public
function
writeATT
(
$handle
):
void
{
// Write an AT&T format FST file
foreach
(
$this
->
states
as
$state
)
{
$state
->
writeATT
(
$handle
);
}
// Now write the final states
foreach
(
$this
->
states
as
$state
)
{
if
(
$state
->
isFinal
)
{
fwrite
(
$handle
,
strval
(
$state
->
id
)
.
"
\n
"
);
}
}
}
}
File Metadata
Details
Attached
Mime Type
text/x-php
Expires
Oct 5 2026, 13:36 (6 w, 1 d ago)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
18/47/3a1be84795851a971c0fa6529687
Default Alt Text
MutableFST.php (7 KB)
Attached To
Mode
rMWPROD MediaWiki Production
Attached
Detach File
Event Timeline
Log In to Comment