Method and apparatus for aligning ambiguity in finite state transducers

• US 20020046017A1
• Filed: 12/18/2000
• Published: 04/18/2002
• 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 7,107,205 B2
• Time in Patent Office: Days
• US Class Current: 704/1
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A method prepares a functional finite-state transducer (FST) with an epsilon or empty string on the input side for factorization into a bimachine. The method creates a left-deterministic input finite-state automation (FSA) by extracting and left-determinizing the input side of the functional FST. Subsequently, the corresponding sub-paths in the FST are identified for each arc in the left-deterministic FST and aligned.

Claims

1. A method for aligning ambiguity in an input finite-state transducer (FST) having an input side, comprising the steps of:

creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by extracting the input side and determinizing the input side from left to right; and

identifying each arc in the left-deterministic FSA, and for each such arc;

identifying at least one corresponding sub-path in the input FST; and

aligning the sub-path with at least one other corresponding sub-path by prepending arcs with symbols representative of an empty string.

2. The method of claim 1, further comprising the step of inserting the sub-path in an aligned FST after aligning the sub-path.

3. The method of claim 2, further comprising the step of minimizing the aligned FST.

4. The method of claim 3, further comprising the step of factoring the aligned FST to produce a left-sequential FST and a right-sequential FST.

5. The method of claim 4, where in the left-sequential FST and the right-sequential FST are adapted for performing language processing.

6. The method of claim 5, wherein the language processing comprises one of tokenization, phonological analysis, morphological analysis, disambiguation, spelling correction, and shallow parsing.

7. The method of claim 4, wherein the left-sequential FST and the right-sequential FST are lexical transducers.

8. The method of claim 3, further comprising the step of replacing the boundary symbols with empty string symbols before minimizing the aligned FST.

9. The method of claim 1, further comprising the step of concatenating a boundary symbol between any final states existing in the input FST and a new final state.

10. The method of claim 9, further comprising the step of minimizing the input FST with the new final state.

12. The apparatus of claim 1, further comprising means for inserting the sub-path in an aligned FST after aligning the sub-path.

11. An apparatus for aligning ambiguity in an input finite-state transducer (FST) having an input side, comprising:

means for creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by extracting the input side and determinizing the input side from left to right; and

means for identifying each arc in the left-deterministic FSA, and for each such arc said identifying means;

identifying at least one corresponding sub-path in the input FST; and

aligning the sub-path with at least one other corresponding sub-path by prepending arcs with symbols representative of an empty string.

13. The apparatus of claim 12, further comprising means for minimizing the aligned FST.

14. The apparatus of claim 13, further comprising means for factoring the aligned FST to produce a left-sequential FST and a right-sequential FST.

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.