Method and apparatus for factoring unambiguous finite state transducers

• US 20030046055A1
• Filed: 12/18/2000
• Published: 03/06/2003
• Est. Priority Date: 04/03/2000
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kempe, Andre
• Granted Patent: US 6,944,588 B2
• Time in Patent Office: Days
• US Class Current: 704/1
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

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.

Claims

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 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 3, further comprising the step of assigning the intermediate symbols in 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. 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 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.

13. The method of claim 12, 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.

14. 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 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 right-sequential FST that are based on an alphabet of intermediate symbols identified using the plurality of emission sub-matrices.

15. The apparatus of claim 14, wherein the left-sequential FST and the right-sequential FST are adapted for performing language processing.

16. The apparatus of claim 15, wherein the language processing comprises one of tokenization, phonological analysis, morphological analysis, disambiguation, spelling correction, and shallow parsing.

17. The apparatus of claim 14, wherein the left-sequential FST and the right-sequential FST are lexical transducers.