Apparatus for identifying unknown words by comparison to known words

• US 5,392,212 A
• Filed: 07/07/1993
• Issued: 02/21/1995
• Est. Priority Date: 07/07/1993
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Commerce
• Original Assignee: THE GOVERNMENT OF THE UNITED STATES OF AMERICA, AS REPRESENTED BY THE SECRETARY OF COMMERCE
• Inventors: Geist, Jon C.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): SHINGALA, GITA
• Application Number:
  US08/086,982
• Time in Patent Office: 594 Days
• Field of Search: 364/419.11, 364/419.12, 364/419.13, 364/419.14, 364/419.1, 382/40
• US Class Current: 715/236
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

An apparatus for correlating an unknown word with a plurality of dictionaryords includes a first memory area storing data corresponding to the unknown word and a plurality of second memory areas respectively storing data corresponding to the plurality of dictionary words. A control mechanism coupled to the first and second memory areas divides the unknown word into a plurality of unknown word fragments and divides each of the plurality of dictionary words stored in the second memory areas into a plurality of dictionary word fragments. An arithmetic logic unit compares the unknown word fragments to the dictionary word fragments and generates an output signal indicating a hit when an unknown word fragment corresponds to at least one of the dictionary word fragments. A hit counter counts the number of hits. The first memory area and the plurality of second memory areas may be implemented using circular shift registers.

Claims

1. An apparatus for comparing an unknown word to a plurality of known, dictionary words to identify the unknown word comprising:

a first memory area storing data corresponding to an unknown word;

a plurality of second memory areas, each second memory area respectively storing data corresponding to one of a plurality of known, dictionary words;

control means coupled to the first memory area and the second memory areas including an unknown word decoder for decoding each of the unknown words and for forming unknown word digraphs respectively representing the plurality of unknown words, the control means storing the unknown word digraphs in the first memory area and including a dictionary word decoder for decoding each of the plurality of dictionary words for each of the known, dictionary words and for forming a plurality of dictionary word digraphs from the known, dictionary words respectively representing the known, dictionary words, and the control means respectively storing each of the plurality of dictionary word digraphs in the plurality of second memory areas;

an arithmetic logic unit coupled to the first memory area and the second memory areas for comparing the unknown word digraphs to the dictionary word digraphs and generating an output signal indicating a hit when an unknown word digraph corresponds to at least one of the dictionary word digraphs; and

a hit counter for counting and indicating the number of hits.

2. The apparatus of claim 1 wherein the arithmetic logic unit generates an output signal indicating a miss when an unknown word does not correspond to at least one of the dictionary words and including a miss counter for counting and indicating the number of misses.

3. The apparatus of claim 2 wherein the arithmetic logic unit includes an AND gate for determining a hit count for each of the known, dictionary words and the miss counter includes an XOR gate for determining the miss count for each of the known, dictionary words.

4. The apparatus of claim 3 wherein the arithmetic logic unit includes a plurality of AND gates and a plurality of XOR gates operating in parallel for simultaneously determining the hit and miss count for each of the known, dictionary words.

5. The apparatus of claim 1 wherein the first memory area and each of the plurality of second memory areas include circular shift registers.

6. The apparatus of claim 2 wherein the control means includes means for determining a confidence factor associated with each known, dictionary word equal to:

##EQU2##

7. An apparatus for comparing an unknown word to a plurality of known dictionary words to identify the known word comprising:

a plurality of known word circular shift registers respectively storing one of a plurality of known word digraphs, each known word corresponding to one of a plurality of known, dictionary words;

an unknown word circular shift register storing data corresponding to an unknown word; and

control means for decoding each of the unknown words to form an unknown word digraph, for storing the unknown word digraph in the unknown word circular shift register, and for simultaneously shifting the unknown word circular shift register and each of the plurality of known word circular shift registers to compare the unknown word digraph to the known word digraphs.

8. The apparatus of claim 7 comprising:

an arithmetic logic unit including a plurality of logic AND gates coupled to the unknown word circular shift register and the known word circular shift registers for simultaneously comparing a plurality of bits respectively output from the plurality of known word circular shift registers with a bit output from the unknown word circular shift register and generating an output signal indicating a hit when bits for each known word circular shift register correspond to bits in the unknown word circular shift register; and

a counter for counting and indicating the number of hits.

9. The correlating apparatus of claim 8 wherein the arithmetic logic unit includes a plurality of logic XOR gates coupled to the unknown word circular shift register and respectively coupled to the plurality of known word circular shift registers for determining a miss count for each known word digraph of the plurality of unknown word digraphs by simultaneously comparing a plurality of bits respectively output from the plurality of unknown word circular shift registers with a bit output from the unknown word circular shift register using the plurality of logic XOR gates, the miss count for each known word digraph indicating the number of bits, for each known word circular shift register, which do not correspond to bits in the unknown word circular shift register.