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

• US 6,965,858 B2
• Filed: 12/18/2000
• Issued: 11/15/2005
• 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): Šmits, Tālivaldis Ivars
• Assistant Examiner(s): Shortledge, Thomas E.
• Application Number:
  US09/737,857
• Publication Number:
  US 20020120437A1
• Time in Patent Office: 1,793 Days
• Field of Search: 704/9, 704/10, 704/257, 704/1, 704/2
• 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

1. A method for removing redundant intermediate symbols from a first factor having an output side and a second factor having an input side, comprising:

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

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

replacing on the output side of the first factor and on the input side of the second factor 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; and

minimizing the first factor and the second factor.

2. The method of claim 1, wherein said representing step selects the unique symbol from one of the input symbols in the corresponding equivalence class.

3. 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:

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;

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; and

minimizing the first FST and the second FST.

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:

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₃∘

FST₁∘

FST₂.

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

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

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

10. 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;

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; and

means for minimizing the first FST and the second FST.

11. The apparatus of claim 10, 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.

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

FST₃∘

FST₁∘

FST₂.

13. The apparatus of claim 10, wherein the first FST and the second FST are adapted for performing language processing.

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

15. The apparatus of claim 10, wherein the first FST and the second FST are lexical transducers.