Method and apparatus for reducing the intermediate alphabet occurring between cascaded finite state transducers

• US 20020120437A1
• Filed: 12/18/2000
• Published: 08/29/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,965,858 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A method reduces the number of diacritics and other intermediate symbols occurring between two factors that result from any factorization such as extraction of infinite ambiguity, factorization of finitely ambiguous finite-state transducer, or bimachine factorization. The method a posteriori removes all redundant intermediate symbols. The method can be used with any two finite-state transducers (FSTs) that operate in a cascade. With longer cascades, the method can be applied pair-wise to all FSTs, preferably starting from the last pair.

Claims

2-1. The method of claim 1, wherein the first factor and the second factor are derived by factoring an input finite-state transducer (FST).

4. A method for removing redundant intermediate symbols from a first finite-state transducer (FST) having an output side and a second finite-state transducer (FST) having an input side, comprising the steps of:

identifying a plurality of non-overlapping equivalence classes of input symbols that are diacritics on the input side of the second FST;

representing each of the plurality of non-overlapping equivalence classes with a unique symbol; and

replacing on the output side of the first FST and on the input side of the second FST each occurrence of a diacritic that appears in one of the plurality of non-overlapping equivalence classes with the unique symbol that represents the corresponding equivalence class.

5. The method of claim 4, further comprising the step of removing redundant intermediate symbols from a third FST having an output side and the first FST having an input side, said step comprising the steps of:

identifying a plurality of non-overlapping equivalence classes of input symbols that are diacritics on the input side of the first FST;

representing each of the plurality of non-overlapping equivalence classes with a unique symbol; and

replacing on the output side of the first FST and on the input side of the third FST each occurrence of a diacritic that appears in one of the plurality of non-overlapping equivalence classes with the unique symbol that represents the corresponding equivalence class.

6. The method of claim 5, wherein said first FST, said second FST, and said third FST compose in the following order:

FST₃ o FST₁ o FST₂.

7. The method of claim 4, further comprising the step of minimizing the first FST and the second FST.

8. The method of claim 4, wherein the first FST and the second FST are adapted for performing language processing.

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

10. The method of claim 4, wherein the first FST and the second FST are lexical transducers.

11. An apparatus for removing redundant intermediate symbols from a first FST having an output side and a second FST having an input side, comprising:

means for identifying a plurality of non-overlapping equivalence classes of input symbols that are diacritics on the input side of the second FST;

means for representing each of the plurality of non-overlapping equivalence classes with a unique symbol; and

means for replacing on the output side of the first FST and on the input side of the second FST each occurrence of a diacritic that appears in one of the plurality of non-overlapping equivalence classes with the unique symbol that represents the corresponding equivalence class.

12. The apparatus of claim 11, further comprising means for removing redundant intermediate symbols from a third FST having an output side and the first FST having an input side, said removing means comprising:

means for identifying a plurality of non-overlapping equivalence classes of input symbols that are diacritics on the input side of the first FST;

means for representing each of the plurality of non-overlapping equivalence classes with a unique symbol; and

means for replacing on the output side of the first FST and on the input side of the third FST each occurrence of a diacritic that appears in one of the plurality of non-overlapping equivalence classes with the unique symbol that represents the corresponding equivalence class.

13. The apparatus of claim 12, wherein said first FST, said second FST, and said third FST compose in the following order:

FST₃ o FST₁ o FST₂.

14. The apparatus of claim 11, further comprising means for minimizing the first FST and the second FST.

15. The apparatus of claim 11, wherein the first FST and the second 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 11, wherein the first FST and the second FST are lexical transducers.