wikimedia / parsoid / 2014 / 2

85%

master: 85%

Build Type

push

travis-ci

Committed by jenkins-bot

Commit Message

<a href="https://github.com/wikimedia/parsoid/commit/461ed0ab1">LanguageConverter: switch to byte-oriented state machines

For Latin script languages, the maximum degree of a state machine
node is on the order of ~50, since the alphabet (plus digits,
punctuation, and spaces) is not very large.

However for CJK languages like Mandarin, the maximum degree of a
state machine node can be much higher, since there are thousands of
possible characters.  The foma tools seem to contain algorithms
which are ~quadratic (in space and time) in the degree of a node,
and they exhaust space and time bounds and fail for Mandarin
when the FST is expressed in terms of Unicode code points.

Building the machine to operate on UTF-8 octets (&quot;bytes&quot;) instead
of Unicode code points ensures that the maximum degree of an FST
node is 184 (for the first octet) but more commonly 64 (for
continuation bytes, which are 10xxxxxx in binary).  This
refactoring of the state machine allows us to operate directly
on strings in their native UTF-8 encoding, but more importantly
it distributes the out degree among nodes so that the foma
algorithms execute in reasonable amounts of space and time.

Change-Id: I</a><a class="double-link" href="https://github.com/wikimedia/parsoid/commit/93c872a93">93c872a93</a>

Coverage Stats

9276 of 11686 branches covered (79.38%)

15135 of 17882 relevant lines covered (84.64%)

24422.23 hits per line