Method and apparatus for extracting short runs of ambiguity from finite state transducers

• US 20020152062A1
• Filed: 12/18/2000
• Published: 10/17/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 6,760,636 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 extracts all “short” ambiguity from an input FST (i.e., ambiguities of one arc in length). The method factors the input FST into a first factor and a second factor such that the second factor contains all ambiguity that is one arc long, and the first factor contains all other parts of the input FST. The method a priori prevents the creation of some redundant intermediate symbols.

Claims

1. A method for extracting short runs of ambiguity from an input finite-state transducer (FST) having a plurality of states and arcs, an input side, and an output side, comprising the steps of:

identifying at least one set of arcs in the input FST;

each set of arcs having a plurality of arcs that identify a single-arc ambiguity field with a common input symbol;

generating a first factor by assigning a diacritic to the output side of each arc within a set of arcs; and

generating a second factor having a single state and a set of ambiguous arcs;

at least one of the ambiguous arcs in the set mapping a diacritic to an output symbol.

2. The method of claim 1, further comprising the step of minimizing the first factor.

3. The method of claim 1, wherein the plurality of arcs in the set have a common source state and a common destination state.

4. The method of claim 1, wherein the diacritic for each set is unique.

5. The method of claim 1, wherein at least one of the ambiguous arcs in the set map any output symbol, which is in the first factor and not a diacritic, to itself.

6. The method of claim 1, wherein the first factor and the second factor are adapted for performing language processing.

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

8. The method of claim 1, wherein the first factor and the second factor are lexical transducers.

16. The apparatus of claim 1, wherein the first factor and the second factor are lexical transducers.

9. An apparatus for extracting short runs of ambiguity from an input finite-state transducer (FST) having a plurality of states and arcs, an input side, and an output side, comprising:

means for identifying at least one set of arcs in the input FST;

each set of arcs having a plurality of arcs that identify a single-arc ambiguity field with a common input symbol;

means for generating a first factor by assigning a diacritic to the output side of each arc within a set of arcs; and

means for generating a second factor having a single state and a set of ambiguous arcs;

at least one of the ambiguous arcs in the set mapping a diacritic to an output symbol.

10. The apparatus of claim 9, further comprising means for minimizing the first factor.

11. The apparatus of claim 9, wherein the plurality of arcs in the set have a common source state and a common destination state.

12. The apparatus of claim 9, wherein the diacritic for each set is unique.

13. The apparatus of claim 9, wherein at least one of the ambiguous arcs in the set map any output symbol, which is in the first factor and not a diacritic, to itself.

14. The apparatus of claim 9, wherein the first factor and the second factor are adapted for performing language processing.

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