Fuzzy string matcher

• US 5,276,741 A
• Filed: 05/16/1991
• Issued: 01/04/1994
• Est. Priority Date: 05/16/1991
• Status: Expired due to Fees

• Current Assignee: Computer Sciences Corporation (DXC Technology Company)
• Original Assignee: TRW Financial Systems & Services Incorporated
• Inventors: Aragon, David B.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/701,383
• Time in Patent Office: 964 Days
• Field of Search: 382/40, 382/14, 382/15, 382/57, 364/518, 395/61, 395/63
• US Class Current: 382/229
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

An apparatus and method useful in correcting character strings misread by a character recognition engine. The misread string is compared to character strings contained in a lexicon of valid character strings and the similarity between the strings measured. The valid strings can be ranked by degree of similarity should further selection be required to determine the appropriate value of the misread character string.

Claims

1. A method for comparing a test character string to a plurality of valid data strings to identify valid data strings which closely match the test character string, comprising the steps of:

(a) subdividing the test character string into sets of N adjacent characters;

(b) storing in a first count array a frequency of one set of N adjacent characters in the test string;

(c) comparing said frequency to an initial frequency value to obtain an initial holographic distance;

(d) repeating step (b) and (c) for all sets of N adjacent characters formed in step (a);

(e) subdividing a given valid data string into sets of N adjacent characters;

(f) storing in a second count array a frequency of one set of N adjacent characters found in said given valid character string;

(g) comparing said frequency of said set of N adjacent characters found in the test character string to said frequency of said given set of N adjacent characters found in said valid character string to obtain an updated holographic distance;

(h) repeating steps (f) and (g) for all sets of N adjacent characters formed in step (e);

(i) clearing said updated holographic distance to said initial holographic distance and clearing said second count array to an initial value; and

(j) repeating steps (e) through (i) inclusive for each of said plurality of valid character strings.

2. The method for comparing of claim 1 wherein step (a) and step (e) comprise the step of reading a given set of an adjacent characters into a register.

3. The method for comparing of claim 1 further comprising the step of storing a current holographic distance and wherein step (g) further comprises the steps of:

computing a squared Euclidean distance between said frequency of said given set of N adjacent characters found in the test character string and said frequency of said given set of N adjacent characters found in said valid character string to form a distance update;

adding said distance update to said current holographic distance to form said updated holographic distance; and

storing said updated holographic distance as said current holographic distance.

4. The method for comparing of claim 1 further comprising the step of storing a current holographic distance and wherein step (g) further comprises the steps of:

computing a Manhattan distance between said frequency of said given set of N adjacent characters found in the test character string and said frequency of said given set of N adjacent characters found in said valid character string to form a distance update;

adding said distance update to said current holographic distance to form said updated holographic distance; and

storing said updated holographic distance as said current holographic distance.

5. The method for comparing of claim 1 further comprising the step of selecting a subset of valid character strings as a function of the holographic distances from the test character string.

46. The method for comparing of claim 5 wherein the subset of valid character strings is within a predetermined holographic distance from the test character string.

47. The method for comparing of claim 5 wherein the subset of valid character strings includes not more than a predetermined number of the valid character strings, all other valid character strings having equal or greater holographic distances from the test string.

48. The method for comparing of claim 47 wherein the predetermined number is one.

6. A device for comparing a test character string to a plurality of valid data strings of a lexicon to identify valid data strings which closely match the test character string comprising:

a set of N registers, having an input coupled to said lexicon and to said test character string, for inputting a set of N adjacent characters to form a given N-gram;

a set of N registers, having an input coupled to said lexicon and to said test character string, for inputting a set of N adjacent characters to form a given N-gram;

a hashing logic circuit coupled to an output of said set of N registers, for asserting a count array address corresponding to the given N-gram;

a first count array, having an input coupled to an output of said hashing logic circuit, for storing a frequency of said given N-gram in the test character string;

a second count array, having an input coupled to an output of said hashing logic circuit, for storing a frequency of said given N-gram in a given valid character string;

means, coupled to said input of said first and second count arrays and to an output of said first and second count arrays, for incrementing said frequencies stored in said first and second count arrays;

an arithmetic logic unit for comparing said frequency stored in said first array to said frequency stored in said second array to obtain a distance update and having;

(i) a first set of inputs coupled to said first array;

(ii) a second set of inputs coupled to said second array; and

(iii) an output having m sum bits and a single carry bit; and

an accumulator for updating a current holographic distance to obtain an updated holographic distance and having;

(i) a lowest order input coupled to an asserted signal;

(ii) m inputs coupled to said m sum bits of said arithmetic logic unit;

(iii) a most significant bit coupled to said carry bit of said arithmetic logic unit; and

(iv) an output.

7. The device of claim 6 further comprising a means, coupled to said means for adding, for selecting a subset of said valid character strings.

8. The device of claim 7 wherein said means for selecting comprises a comparator.

9. The device of claim 6 wherein said first and said second count arrays each comprise a static random access memory.

10. The device of claim 6 wherein said first and second count arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

11. The device of claim 6 wherein said hashing logic comprises a look-up table.

12. The device of claim 6 wherein said means for adding comprises a two'"'"'s complement adder.

13. The device of claim 6 wherein said first and second count arrays store a plurality of Boolean flags.

14. A device for comparing a test character string to a plurality of valid data strings of a lexicon to identify valid data strings which closely match the test character string comprising:

a set of N registers, having an input coupled to said lexicon and to said test character string, for inputting a set of N adjacent characters to form a given N-gram;

a hashing logic circuit coupled to an output of said set of N registers, for asserting a count array address corresponding to the given N-gram;

a first count array, having an input coupled to an output of said hashing logic circuit, for storing a frequency of said given N-gram in the test character string;

a second count array, having an input coupled to an output of said hashing logic circuit, for storing a frequency of said given N-gram in a given valid character string;

means, coupled to said input of said first and second count arrays and to an output of said first and second count arrays, for incrementing said frequencies stored in said first and second count arrays;

an arithmetic logic unit for comparing said frequency stored in said first array to said frequency stored in said second array to obtain a distance update and having;

(i) a first set of inputs coupled to said first array;

(ii) a second set of inputs coupled to said second array; and

(iii) an output having m sum bits and a single carry bit; and

an accumulator for updating a current holographic distance to obtain an updated holographic distance and having;

(i) a lowest order input coupled to an asserted signal;

(ii) m inputs coupled to said m sum bits of said arithmetic logic unit;

(iii) a most significant bit coupled to said carry bit of said arithmetic logic unit; and

(iv) an output.

15. The device of claim 14 wherein said first and second count arrays each comprise static random access memory.

16. The device of claim 14 wherein said first and second count arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

17. The device of claim 14 wherein said accumulator comprises a two'"'"'s complement adder.

18. The device of claim 14 wherein said hashing logic comprises a look-up table.

19. The device of claim 14 further comprising a means, coupled to said accumulator, for selecting a subset of said valid character strings.

20. The device of claim 19 wherein said means for selecting comprises a comparator.

21. A device for comparing a test character string to a plurality of valid data strings to identify valid data strings which closely match the test character string comprising:

a set of N registers, having an input coupled to a lexicon and to the test character string, for inputting a set of N adjacent characters to form a given N-gram;

a hashing logic circuit coupled to an output of said set of N registers, for asserting a count array address corresponding to the given N-gram;

a first count array, having an input coupled to an output of said hashing logic circuit, for storing a frequency of said given N-gram in a given valid character string read from said lexicon;

means, coupled to said input of said first and second count arrays and to an output of said first and second count arrays, for incrementing said frequencies stored in said first and second count arrays;

an arithmetic logic unit for comparing said frequency stored in said first array to said frequency stored in said second array to obtain a distance update and having;

(i) a first set of inputs coupled to said second array;

(ii) a second set of inputs coupled to said second array; and

(iii) an output having m sum bits and a single carry bit;

a multiplexer, having a first input coupled to said m sum bits of said arithmetic logic unit, a second input coupled to said carry bit of said arithmetic logic unit and m outputs; and

an accumulator for updating a current holographic distance to obtain an updated holographic distance and having;

(i) a lowest order input coupled to an asserted signal;

(ii) m inputs coupled to said m outputs of said multiplexer;

(iii) a most significant bit input coupled to said carry bit of said arithmetic logic unit; and

(iv) an output.

22. The device of claim 21 wherein said first and second count arrays each comprise static random access memory.

23. The device of claim 21 wherein said first and second count arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

24. The device of claim 21 wherein said accumulator comprises a two'"'"'s complement adder.

25. The device of claim 21 wherein said hashing logic comprises a look-up table.

26. The device of claim 21 further comprising a means, coupled to said accumulator, for selecting a subset of said valid character strings.

27. The device of claim 26 wherein said means for selecting comprises a comparator.

28. A device for comparing a test character string to a plurality of valid data strings of a lexicon to identify valid data strings which closely match the test character string comprising:

a set of N registers, having an input coupled to said lexicon and to said test character string, for inputting a set of N adjacent characters to form a given N-gram;

a first hashing logic circuit, coupled to an output of said set of N registers, for asserting a first count array address corresponding to the given N-gram;

a first count array, having an input coupled to an output of said first hashing logic circuit, for storing a frequency of said given N-gram in the test character string;

a second count array, having an input coupled to an output of said first hashing logic circuit, for storing a frequency of said given N-gram in a given valid character string read from said lexicon;

means, coupled to said input of said first and second count arrays and to an output of said first and second count arrays, for incrementing said frequencies stored in said first and second count arrays;

means, having an input coupled to said output of said first and second count arrays, for comparing said frequency stored in said first count array and said frequency stored in second count array to obtain a first distance update;

means, coupled to an output of said means for comparing, for adding said first distance update to a current holographic distance to obtain a first updated holographic distance;

a second hashing logic circuit, coupled to M outputs of said set of N registers, for asserting a second count array address corresponding to the M outputs wherein M<

N;

a third count array, having an input coupled to an output of said second hashing logic circuit, for storing a frequency of a given M-gram in the test character string;

a fourth count array, having an input coupled to an output of said second hashing logic circuit, for storing a frequency of said given M-gram in a given valid character string read from said lexicon;

means, coupled to said input of said third and fourth count arrays and to an output of said third and fourth count arrays, for incrementing said frequencies stored in said third and fourth count arrays;

means, having an input coupled to said output of said third and fourth count arrays, for comparing said frequency stored in said third count array and said frequency stored in said fourth count array to obtain a second distance update;

means, coupled to an output of said means for comparing, for adding said second distance update to a second current holographic distance to obtain a second updated holographic distance; and

means, coupled to said means for obtaining a first updated holographic distance and to said means for obtaining a second updated holographic distance, for adding said first updated holographic distance to said second updated holographic distance to obtain a total updated holographic distance.

29. The device of claim 28 further comprising a means, coupled to said means for obtaining a total updated holographic distance, for selecting a subset of said valid character strings.

30. The device of claim 29 wherein said means for selecting comprises a comparator.

31. The device of claim 28 wherein said first and second count arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

32. The device of claim 28 wherein said third and fourth count arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

33. The device of claim 28 wherein said first and said second hashing logic comprise a look-up table.

34. The device of claim 28 wherein said first and said second count arrays store a plurality of Boolean flags.

35. The device of claim 28 wherein said third and said fourth count arrays store a plurality of Boolean flags.

36. The device of claim 28 wherein said means for obtaining a first updated holographic distance comprises a two'"'"'s complement adder.

37. The device of claim 28 wherein said means for obtaining a second updated holographic distance comprises a two'"'"'s complement adder.

38. A system for resolving a character recognition error comprising:

a set of N registers, having an input coupled to a lexicon and to a test character string, for inputting a set of N adjacent characters to form a given N-gram;

a hashing logic circuit, coupled to an output of said set of N registers, for asserting a count array address corresponding to the given N-gram;

a first register array, having an input coupled to an output of said hashing logic circuit, for indicating occurrences of said given N-gram in the test character string;

a second register array, having an input coupled to an output of said hashing logic circuit, for indicating occurrences of said given N-gram in a given valid character string read from said lexicon;

an increment circuit coupled to said input of said first and second register arrays and to an output of said first and second register arrays for incrementing respective values stored in said first and second register arrays, the values corresponding to frequencies of said given N-gram in the respective character strings;

means, having an input coupled to said output of said first and second register arrays, for comparing said frequency stored in said first register array and said frequency stored in said second register array to obtain a distance update; and

means, coupled to an output of said means for comparing, for adding said distance update to a current holographic distance to obtain an updated holographic distance.

39. The system of claim 38 further comprising a means, coupled to said means for adding, for selecting a subset of said valid character strings.

40. The system of claim 39 wherein said means for selecting comprises a comparator.

41. The system of claim 38 wherein said first and said second register arrays each comprise a static random access memory.

42. The system of claim 38 wherein said first and second register arrays each comprise:

a plurality of storage elements having a first width; and

a plurality of storage elements having a second width.

43. The system of claim 38 wherein said hashing logic comprises a look-up table.

44. The system of claim 38 wherein said means for adding comprises a two'"'"'s complement adder.

45. The system of claim 38 wherein said first and second register arrays store a plurality of Boolean flags.