Method and apparatus for reducing the intermediate alphabet occurring between cascaded finite state transducers
AssigneeXerox Corporation
InventorAndre Kempe
Life of this patent
Estimating the term…
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.
Claims18
A method for removing redundant intermediate symbols from a first factor having an output side and a second factor 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 factor;
- representing each of the plurality of non-overlapping equivalence classes with a unique symbol;
- and
- 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.
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.
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.
Dependencies are inferred from the claim text.