Method and system for comparing strings with entries of a lexicon

• US 5,774,588 A
• Filed: 06/07/1995
• Issued: 06/30/1998
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Li, Liang
• Primary Examiner(s): Johns, Andrew
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/477,481
• Time in Patent Office: 1,119 Days
• Field of Search: 382/229, 382/230, 382/231
• US Class Current: 382/230
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

A system and method for more efficiently comparing an unverified string to a lexicon, which filters the lexicon through multiple steps to reduce the number of entries to be directly compared with the unverified string. The method begins by preparing the lexicon with an n-gram encoding, partitioning and hashing process, which can be accomplished in advance of any processing of unverified strings. The unknown is compared first by partitioning and hashing it in the same way to reduce the lexicon in a computationally inexpensive manner. This is followed by an encoded vector comparison step, and finally by a direct string comparison step, which is the most computationally expensive. The reduction of the lexicon is accomplished without arbitrarily eliminating any large portions of the lexicon that might contain relevant candidates. At the same time, the method avoids the need to compare the unverified string directly or indirectly with all the entries in the lexicon. The final candidate list includes only highly possible and ranked candidates for the unverified string, and the size of the final list is adjustable.

Claims

1. A method of comparing strings with entries of a lexicon, comprising the steps of:

organizing entries of the lexicon by, for each entry;

(a) forming an n-gram vector representing a lexicon entry;

(b) folding said n-gram vector into a signature vector by combining multiple n-grams into bits;

(c) creating a list of bits having the same n-grams as the bits of the signature vector, beginning with the bit occurring most frequently in the lexicon and continuing in descending order;

(d) creating a partitioned vector whose element values are binary numbers whose digits represent the bits of the list of bits, partitioned into groups of digits forming the binary numbers, the digits being set or not set depending on whether the bit of the signature vector having the same n-grams is set;

(e) establishing a plurality of buckets having addresses corresponding to all possible element values of the partitioned vector;

(f) indexing said lexicon entry to the one or more of said buckets having an address corresponding to an element value of said lexicon entry'"'"'s partitioned vector;

reducing the number of lexicon entries to be compared to a particular unverified string by;

creating a partitioned vector for said unverified string according to steps (a)-(d);

indexing said unverified string to those buckets whose addresses correspond to an element value of said unverified string'"'"'s partitioned vector; and

comparing a representation of said unverified string with representations of only those lexicon entries that are indexed to the bucket addresses to which said unverified string is indexed.

2. The method of claim 1, wherein said bucket addresses comprise decimal numbers corresponding to the binary number formed by the bit values of an element of the partitioned vector.

3. The method of claim 1, wherein said step of reducing the number of lexicon entries to be compared further comprises defining a reduced portion of the lexicon limited to lexicon entries indexed to buckets whose addresses correspond to selected elements of the partitioned vector.

4. The method of claim 1, wherein the representations of said unverified string and said lexicon entries in said comparing step comprise folded n-gram signature vectors.

5. The method of claim 4, further comprising the step of further reducing the lexicon to those entries whose folded n-gram signature vectors have, on comparison to the unverified string'"'"'s folded n-gram signature vector, a normalized coincidence of corresponding bits higher than a predetermined coincidence threshold.

8. The method of claim 1, wherein said step of folding said n-gram vector into a signature vector comprises combining eight bits of said n-gram vector into one bit of said signature vector.

9. The method of claim 8, wherein said step creating a partitioned vector comprises partitioning said signature vector into groups of twelve bits.

17. The method of claim 1, further comprising the step of processing a second unverified string without further organizing the entries of said lexicon, by:

creating a partitioned vector for said second unverified string according to steps (a)-(d);

indexing said second unverified string to those buckets whose addresses correspond to an element value of said second unverified string'"'"'s partitioned vector, and

comparing a representation of said second unverified string with representations of only those lexicon entries that are indexed to the bucket addresses to which said second unverified string is indexed.

6. The method of claim 38, further comprising the step of comparing the unverified string in its original form and the further reduced entries of the lexicon in their original form.

7. The method of claim 6, wherein said step of comparing the unverified string in its original form and the entries of the further reduced entries of the lexicon in their original form comprises:

conducting a transformation cost analysis between the unverified string in its original form and the entries of the reduced portion of the lexicon in their original form; and

defining a final list of candidate entries based on normalized transformation cost scores determined in said transformation cost analysis.

10. A system for linking entries of a lexicon to an unverified string in an image, comprising:

an imager operative to acquire and store an image of a string of characters; and

a processor configured to;

organize entries of the lexicon by, for each entry;

(a) form an n-gram vector representing a lexicon entry;

(b) fold said n-gram vector into a signature vector by combining multiple ngrams into bits;

(c) determine a list of bits having the same n-grams as the bits of the signature vector, beginning with the bit occurring most frequently in the lexicon and continuing in descending order;

(d) create a partitioned vector whose element values are binary numbers whose digits represent the bits of the list of bits, partitioned into groups of digits forming the binary numbers, the digits being set or not set depending on whether the bit of the signature vector having the same n-grams is set;

(e) establish a plurality of buckets having addresses corresponding to all possible element values of the partitioned vector;

(f) index said lexicon entry to the one or more of said buckets having an address corresponding to an element value of said lexicon entry'"'"'s partitioned vector;

reduce the number of lexicon entries to be compared to a particular unverified string by;

creating a partitioned vector for said unverified string according to steps (a)-(d);

indexing said unverified string to those buckets whose addresses correspond to an element value of said unverified string'"'"'s partitioned vector; and

compare a representation of said unverified string with representations of only those lexicon entries that are indexed to the bucket addresses to which said unverified string is indexed.

11. A method of comparing an unverified string with entries of a lexicon, comprising the steps of:

for each entry of the lexicon, forming an n-gram vector representing the entry;

folding said n-gram vector into a signature vector of reduced bit length; and

partitioning the bits of each signature vector of each entry of said lexicon into groups each having a predetermined number of bits arranged in descending order of frequency of appearance of each bit in the lexicon;

forming buckets of the entries of the lexicon indexed to bits of said signature vectors by indexing an entry to a bucket identified by numerical values associated with one or more of the groups, the numerical values each formed by all the bits of a group;

comparing a representation of the unverified string with representations of only those lexicon entries mapped to the buckets of a subset of said buckets, by;

forming an n-gram vector representing the unverified string;

folding said n-gram vector of the unverified string into a signature vector of reduced bit length; and

partitioning the bits of the signature vector of the unverified string into groups each having a predetermined number of bits arranged in descending order of frequency of appearance of each bit in the lexicon,

indexing the unverified string to said buckets based on the numerical values formed by the bits of one or more of the groups of the unverified string'"'"'s partitioned signature vector, and

comparing a representation of the unverified string with representations of only those lexicon entries indexed at least one of the same buckets as the unverified string.

12. The method of claim 11, wherein said numerical value is the binary number formed by the bits of the group.

13. The method of claim 12, wherein said bucket addresses comprise decimal numbers corresponding to the binary number formed by the bit values of the partitioned vector.

14. The method of claim 13, wherein said step of reducing the number of lexicon entries to be compared further comprises defining a reduced portion of the lexicon limited to lexicon entries indexed to buckets whose addresses correspond to selected groups of the partitioned vector.

15. The method of claim 14, further comprising the step of further reducing the lexicon to those entries whose folded n-gram signature vectors have, on comparison to the unverified string'"'"'s folded n-gram signature vector, a normalized coincidence of corresponding bits higher than a predetermined coincidence threshold.

16. The method of claim 15, further comprising the step of comparing the unverified string in its original form and the further reduced entries of the lexicon in their original form.