Method and apparatus for factoring unambiguous finite state transducers
View Patent ↗A method factors a functional (i.e., ambiguous) finite state transducer (FST) into a bimachine with a reduced intermediate alphabet. Initially, the method determines an emission matrix corresponding to a factorization of the functional FST. Subsequently, the emission matrix is split into a plurality of emission sub-matrices equal in number to the number of input symbols to reduce the intermediate alphabet. Equal rows of each emission sub-matrix are assigned an identical index value in its corresponding factorization matrix before creating the bimachine.
1. A method for factoring with a functional finite-state transducer (FST) having a number of input symbols into a bimachine, the method comprising the steps of:
determining an emission matrix corresponding to a factorization of the functional FST into a first factor that collapses a set of alternative arcs and a second factor;
splitting the emission matrix into a plurality of emission sub-matrices equal in number to the number of input symbols; and
creating the bimachine having a left-sequential FST and a right-sequential FST that are based on an alphabet of intermediate symbols identified using the plurality of emission sub-matrices.
2. The method of claim 1 , further comprising the step converting the plurality of emission sub-matrices into a factorization sub-matrix.
3. The method of claim 2 , wherein matrix elements of each factorization sub-matrix include a transition defined by an input symbol, an intermediate symbol, and an output symbol; the intermediate symbol being defined using a state of the first factor and an input symbol of the state.
4. The method of claim 5 , further comprising the step of assigning the intermediate symbols of each factorization sub-matrix identical index values when their corresponding row in the emission sub-matrix are equal.
5. The method of claim 4 , wherein said creating step creates the bimachine using the factorization sub-matrices.
6. The method of claim 2 , further comprising the step of assigning identical indices for equal input symbols in the factorization matrix when rows indexing states of the first factor in the emission sub-matrix are equal.
7. The method of claim 6 , wherein at least one of the indices assigned by said assigning step is assigned a pre-existing symbol in the factorization matrix.
8. The method of claim 1 , wherein the first factor is a first deterministic finite state automaton and the second factor is a second deterministic finite state automaton.
9. The method of claim 1 , wherein the left-sequential FST and the right-sequential FST are adapted for performing language processing.
10. The method of claim 9 , wherein the language processing comprises one of tokenization, phonological analysis, morphological analysis, disambiguation, spelling correction and shallow parsing.
11. The method of claim 1 , wherein the left-sequential FST and the right-sequential FST are lexical transducers.
12. The method of claim 1 , wherein the set of arcs collapsed in the first factor is labeled with a diacritic on an output side, and the diacritic is mapped to a set of alternative output symbols in the second factor.
13. A method for factoring with a functional finite-state transducer (FST) having a number of input symbols into a bimachine, the method comprising the steps of:
determining an emission matrix corresponding to a factorization of the functional FST into a first factor that collapses a set of alternative arcs and a second factor;
converting the emission matrix into a factorization matrix; said converting step assigning identical indices for equal input symbols in the factorization matrix when rows indexing states of the first factor in the emission matrix are equal; and
creating the bimachine having a left-sequential FST and a right-sequential FST.
14. The method of claim 13 , further comprising the step of splitting the emission matrix into a plurality of emission sub-matrices equal in number to the number of input symbols.
15. The method of claim 13 , wherein the set of arcs collapsed in the first factor is labeled with a diacritic on an output side, and the diacritic is mapped to a set of alternative output symbols in the second factor.
16. An apparatus for factoring with a functional finite-state transducer (FST) having a number of input symbols into a bimachine, the apparatus comprising:
means for determining an emission matrix corresponding to a factorization of the functional FST into a first factor that collapses a set of alternative arcs and a second factor;
means for splitting the emission matrix into a plurality of emission sub-matrices equal in number to the number of input symbols; and
means for creating the bimachine having a left-sequential FST and a tight-sequential FST that are based on an alphabet of intermediate symbols identified using the plurality of emission sub-matrices.
17. The apparatus of claim 16 , wherein the left-sequential FST and the right-sequential FST are adapted for performing language processing.
18. The apparatus of claim 17 , wherein the language processing comprises one of tokenization, phonological analysis, morphological analysis, disambiguation, spelling correction, and shallow parsing.
19. The apparatus of claim 16 , wherein the left-sequential FST and the right-sequential FST are lexical transducers.
20. The apparatus of claim 16 , wherein the set of arcs collapsed in the first factor is labeled with a diacritic on an output side, and the diacritic is mapped to a set of alternative output symbols in the second factor.