Page MenuHomeWickedGov Phorge
Files F5964116

TODO
No OneTemporary
Actions

Size
3 KB
Referenced Files
None
Subscribers
None

TODO
View Options

Instead of exhaustively tracing the states
use the flag diacritics feature.
From start state there are two edges to state N
one labelled "@D.char0@" "a"
and the other labelled "@R.char0.a" (an epsilon edge).
(Actually, all the "really labelled" edges can share a
state where they pass through "@D.char0@" first.
Then from that state "@D.char1@" "b" and "@R.char1.b" etc.
We match (say) "abc" then follow the edges for "de" but fail to match the
outgoing edge (say, "f"). We then follow the edge for [abcdegh?@R.char5.a@@R.char5.b@...] which
emits "@P.char2.x" (for edge labelled x) then rejoins a common state to do
"@R.char7.x" -> "@P.char3.x" / "@D.char7@" -> "@C.char7@" then rejoin then
"@R.char8.x@" -> "@P.char4.x" / "@D.char8@ -> "@C.char8@" then rejoin then
emit "abc" then "@P.char0.d@" "@P.char1.e@"
before branching to the start state again.
The number of flag diacritic vars is one less than the longest string
(ie, if longest string is "abcdef" we match "abcde" then fail "f" without
any partial matches along the way, so we emit "a", then need to set flag
diacritics for "bcde" and the letter which wasn't "f".
If N is the number of entries and M is the longest word and A the alphabet
size, we expect O(NM) states and O(NM) edges for the straightforward match,
then O(AMN) states for backtracking. Crucially we don't get O(A^2) as a
factor anywhere, but UTF-8 is (probably) still worthwhile because a factor of
4 increase in M is still much cheaper than a factor of 256 increase in A.
Of course maybe the actual A for CJK languages is closer to 4*256 than it
is to 65536.
One option: always use a "readahead" buffer of N characters long, so the
state transitions are always on "@R.charN.M@". Catch: we can't "read ahead"
for @IDENTITY@! so the presence of an identity character means we need to
purge the buffer, echo it, and restart. Basically use "@D.charN@" to
indicate @IDENTITY@ (which includes end-of-string, conveniently enough).
Tricky: every "read character" state is going to have a epsilon edge to
"@C.charN" and then that path though the graph must always end in
either ?:? or epsilon to a final state. But we can waste a lot of
evaluation time if we take that edge early.
Better (more efficient) to only readahead where necessary. But will still
have two edges
Sample:
ab -> aa
abcd -> bbbb
cbc -> ccc
ba -> dd
Input: abcbad
-----------------
Version in hfst seems to do something slightly different which is:
after match 'ab' we then immediately emit 'aa' but continue in a new
state machine which accepts (?* - 'cd') -- that is, it can't match any
strings that match the completion which would make emitting 'ab' incorrect.
something like:
buildState($tree, $notTree, $prefix)
which builds a machine matching $tree but disallowing any input which would
match $notTree. (And $prefix because we need to jump states/push input
back into the buffer sometimes?)
ie, as soon as we match 'ab' we fork: one outgoing edge continues matching
'abcd' or 'abdd' or whatever strings have 'ab' as a prefix; the other
immediately emits 'aa' and loops back to run the original machine, but
disallowing 'cd' or 'dd' as inputs.
From the 'abc' state we don't need to worry about misses any more; any
misses would have been caught by alternative branch from 'ab'.
We pretend there's a top-level ?:? match, which matches when there is no
longer match. So all edges from root emit @ID@ then loop back to match
from the root *except the relevant suffix strings*.
In theory this could be done with flag diacritics where we indicate the
value of the characters not allowed when we loop back?

File Metadata

Mime Type
text/plain
Expires
Sat, Oct 3, 10:05 (1 w, 2 d ago)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
b5/ff/cf57a892d443463af1e5ab40d556
Default Alt Text
TODO (3 KB)

Event Timeline