Method and apparatus for aligning ambiguity in finite state transducers

• US 7,107,205 B2
• Filed: 12/18/2000
• Issued: 09/12/2006
• Est. Priority Date: 04/03/2000
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kempe, Andre
• Primary Examiner(s): Chawan, Vijay
• Assistant Examiner(s): Pierre, Myriam
• Application Number:
  US09/737,939
• Publication Number:
  US 20020046017A1
• Time in Patent Office: 2,094 Days
• Field of Search: 704/2, 704/9, 706/20
• US Class Current: 704/2
• 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 computer-implemented method for finite-state language processing that aligns ambiguity in an input finite-state transducer (FST) having an input side to provide a sequential FST, comprising the steps of:

receiving an input string at the FST;

concatenating a boundary symbol on a right side of the input FST;

creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by producing a minimal FST from the input FST and by extracting the input side and determinizing the input side from left to right, including, for every state q_i with a non-empty set E_Ei, creating two auxiliary arcs, both labeled with the diacritic ξ

_i, setting one of the two auxiliary arcs for each state q_i to lead from an initial state of the FST to each state q_i, setting the other of the two auxiliary arcs for each state q_i to lead from each state q_i to an only final state of the FST, composing a factor Ξ

₂′

to remove all partial ε

loops using an equation

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 1, wherein the language processing comprises one of tokenization, phonological analysis, morphological analysis, disambiguation, spelling correction, and shallow parsing.

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

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

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

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

10. An apparatus for finite-state language processing that aligns ambiguity in an input finite-state transducer (FST) having an input side to provide a sequential FST, comprising:

means for receiving an input string at the FST;

means for concatenating a boundary symbol on a right side of the input FST;

means for creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by producing a minimal FST from the input FST and by extracting the input side and determinizing the input side from left to right, including, for every state q1 with a non-empty set E_i, creating two auxiliary arcs, both labeled with the diacritic ξ

_i, setting one of the two auxiliary arcs for each state qi to lead from an initial state of the FST to each state q_i, setting the other of the two auxiliary arcs for each state q1 to lead from each state q_i to an only final state of the FST, composing a factor Ξ

₂′

to remove all partial ε

loops using an equation

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

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

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

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

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

16. A computer readable medium encoded with a computer program that causes a computer to perform finite-state language processing that aligns ambiguity in an input finite-state transducer (FST) having an input side to provide a sequential FST, comprising the steps of:

receiving an input string at the FST;

concatenating a boundary symbol on a right side of the input FST;

creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by producing a minimal FST from the input FST and by extracting the input side and determinizing the input side from left to right, including, for every state q_i with a non-empty set E_i, creating two auxiliary arcs, both labeled with the diacritic ξ

_i, setting one of the two auxiliary arcs for each state q₁ to lead from an initial state of the FST to each state q₁, setting the other of the two auxiliary arcs for each state q_i to lead from each state q1 to an only final state of the FST, composing a factor Ξ

₂′

to remove all partial c loops using an equation,