Method and apparatus for factoring unambiguous finite state transducers

• US 6,944,588 B2
• Filed: 12/18/2000
• Issued: 09/13/2005
• 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
• Primary Examiner(s): Smits, Talivaldis Ivars
• Assistant Examiner(s): PIERRE, MYRIAM
• Application Number:
  US09/737,940
• Publication Number:
  US 20030046055A1
• Time in Patent Office: 1,730 Days
• Field of Search: 704/9, 704/257, 326/46, 707/101, 717/100
• US Class Current: 704/9
• 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 factors a functional (i.e., ambiguous) finite state transducer (FST) into a bimachine with a reduced intermediate alphabet. Initially, the method determines an emission matrix corresponding to a factorization of the functional FST. Subsequently, the emission matrix is split into a plurality of emission sub-matrices equal in number to the number of input symbols to reduce the intermediate alphabet. Equal rows of each emission sub-matrix are assigned an identical index value in its corresponding factorization matrix before creating the bimachine.

Claims