Contextual tagger utilizing deterministic finite state transducer

• US 5,610,812 A
• Filed: 06/24/1994
• Issued: 03/11/1997
• Est. Priority Date: 06/24/1994
• Status: Expired due to Term

• Current Assignee: Binary Services LLC (Intellectual Ventures LLC)
• Original Assignee: Mitsubishi Electric Information Technology Center America, Inc. (Mitsubishi Electric Corporation)
• Inventors: Schabes, Yves, Roche, Emmanuel
• Primary Examiner(s): McElheny, Jr., Donald E.
• Assistant Examiner(s): Tkacs, Stephen R.
• Application Number:
  US08/264,981
• Time in Patent Office: 991 Days
• Field of Search: 364/419.01, 364/419.08, 364/419.02, 364/419.1, 364/419.11, 364/419.16, 395/12, 395/600
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

A system for assigning part-of-speech tags to English text includes an improved contextual tagger which utilizes a deterministic finite state transducer to improve tagging speed such that large documents can have its sentences accurately tagged as to parts of speech to permit fast grammar checking, spell checking, information retrieval, text indexing and optical character recognition. The subject system performs by first acquiring a set of rules by examining a training corpus of tagged text. Then, these rules are transformed into a deterministic finite-state transducer through the utilization of non-deterministic transducers, a composer and a determiniser. In order to tag an input sentence, the sentence is initially tagged by first assigning each word in the sentence with its most likely part of speech tag regardless of the surrounding words in the sentences. The deterministic finite-state transducer is then applied on the resulting sequence of part of speech tags using the surrounding words and obtains the final part of speech tags. The Subject System requires an amount of time to compute the part-of-speech tags which is proportional to the number of words in the input sentence and which is independent of the number of rules it has applied.

Claims

1. A computer system for correcting part of speech tags of words of sentences in a text, comprising:

means for receiving an initially tagged input sentence; and

,

a contextual part of speech tagger for correcting part-of-speech tags of the words of said initially tagged input sentence, said tagger including a deterministic finite state transducer for tagging said words in accordance with context and in a single pass.

2. The system of claim 1 wherein said deterministic finite state transducer includes for each input word means for making only one tagging choice.

3. The system of claim 2 wherein said means for making only one tagging choice includes means for postponing any choice until sufficient context is detected to ascertain that one tagging choice among the possible tagging choices is correct.

4. The system of claim 1 wherein said input sentence has words, each word having an identifiable sequential position, and wherein said deterministic finite state transducer includes means for selecting a word at one position for analysis to determine the part of speech thereof, means for choosing the part of speech of said selected word based on the parts of speech of prior words in said sentence and means for inhibiting the choice of the part of speech for said selected word if the parts of speech of said prior words do not lead to a singular conclusion as to the part of speech of said selected word.

5. The system of claim 4 wherein said deterministic finite state transducer includes means coupled to said inhibiting means for analyzing the parts of speech of additional words in said sentence until the choice of the part of speech of said selected word is unambiguously clear.

6. The system of claim 5 wherein means for analyzing the parts of speech of said additional words only selects additional words which are subsequent in position to that of said selected word.

7. The system of claim 1 and further including means for initially tagging said sentence by first assigning the most likely part of speech to a word in said sentence without regard to surrounding words, and, means utilizing said deterministic finite state transducer for obtaining a final part-of-speech tag for said word using surrounding words for context.

8. The system of claim 1 wherein said deterministic finite state transducer is derived from a set of tagging rules generated from a training corpus of tagged text and wherein said deterministic finite state transducers includes non-deterministic transducers having said tagging rules as an input thereto, a composer for combining the outputs of said non-deterministic transducers into an omnibus non-deterministic transducer, and a determiniser for postponing decisions as to tagging choice until enough context information is available to make the correct tagging choice.

9. The system of claim 1 wherein said deterministic finite state transducer utilizes only a finite number of predetermined parts of speech sequences corresponding to differing contexts for the words in said sentence.