Method and apparatus for reducing the intermediate alphabet occurring between cascaded finite state transducers
View Patent ↗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.
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 3 ∘FST 1 ∘FST 2 .
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 3 ∘FST 1 ∘FST 2 .
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.