Methods and apparatus for performing spelling corrections using one or more variant hash tables

• US 9,552,349 B2
• Filed: 08/31/2006
• Issued: 01/24/2017
• Est. Priority Date: 08/31/2006
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Hantler, Sidney L., Laker, Meir M., Lenchner, Jonathan, Milch, Daniel
• Primary Examiner(s): Bashore, William
• Assistant Examiner(s): Faber, David
• Application Number:
  US11/513,782
• Publication Number:
  US 20080059876A1
• Time in Patent Office: 3,799 Days
• Field of Search: 715/256, 715/257, 715/259
• US Class Current: 1/1
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Methods and apparatus are provided for performing spelling corrections using one or more variant hash tables. The spelling of at least one candidate word is corrected by obtaining at least one variant dictionary hash table based on variants of a set of known correctly spelled words, wherein the variants are obtained by applying one or more of a deletion, insertion, replacement, and transposition operation on the correctly spelled words; obtaining from the candidate word one or more lookup variants using one or more of the deletion, insertion, replacement, and transposition operations; evaluating one or more of the candidate word and the lookup variants against the at least one variant dictionary hash table; and indicating a candidate correction if there is at least one match in the at least one variant dictionary hash table.

Claims

1. A method for correcting spelling of at least one candidate word, said method comprising:

obtaining at least one variant dictionary hash table based on variants of a set of known correctly spelled words, wherein said variants are obtained by applying one or more of a deletion, insertion, replacement, and transposition operation on said correctly spelled words, wherein said variants obtained by applying one or more of an insertion and replacement operation on said correctly spelled words comprise a wildcard character, wherein for a given correctly spelled word having a length W, said at least one variant dictionary hash table comprises W of said variants each comprising said wildcard character in a different position, and wherein said variants are stored in said at least one variant dictionary hash table and are mapped to one of said corresponding correctly spelled words from said set of known correctly spelled words which are stored in a dictionary hash table that is distinct from said at least one variant dictionary hash table;

performing one or more of a deletion, insertion, replacement, and transposition operation on the at least one candidate word to obtain one or more lookup variants, wherein said lookup variants obtained by applying one or more of an insertion and replacement operation on said at least one candidate word comprise a wildcard character;

evaluating one or more of said lookup variants utilizing said at least one variant dictionary hash table to identify matches; and

indicating a candidate correction if said evaluation step indicates that there is at least one match in the at least one variant dictionary hash table.

2. The method of claim 1, wherein said dictionary hash table is pre-created prior to obtaining said candidate word, further comprising the step of obtaining said dictionary hash table having entries in a dictionary of known correctly spelled words and wherein said dictionary hash table and said at least one variant dictionary hash table are based on said dictionary and are comprised of at least one distance one variation for each of said entries, wherein said distance one variation comprises one or more of a deletion, insertion, replacement, and transposition operation performed on said entries;

and

wherein the step of evaluating said lookup variants utilizing said at least one variant dictionary hash table further comprises the step of evaluating one or more distance one variants utilizing said at least one variant dictionary hash table.

3. The method of claim 2, wherein said distance one variation comprises a replacement operation to generate a replacement hash table having entries of single character wild card replacements of said entries in said dictionary and said method further comprises the steps of generating single character replacements and insertions of said candidate word and comparing said single character replacements and insertions against said replacement hash table.

4. The method of claim 3, wherein the replacement hash table is obtained by:

generating variants of each word in the dictionary, each variant is comprised of replacing any one character in the word with a wild card character and leaving other characters unchanged, thereby generating W variants for each word of length W; and

for each generated variant of a word in the dictionary, storing a key-value pair in a hash table, wherein a key is a generated variant having a value that is the word itself.

5. The method of claim 2, further comprising the steps of generating one or more distance one variants of said at least one candidate word and testing said distance one variants against one or more of said dictionary hash table and said at least one variant dictionary hash table, and accumulating matches.

6. The method of claim 5, wherein said one or more distance one variants comprises adjacent character transpositions of said at least one candidate word obtained by generating all variants of the candidate word wherein any one pair of adjacent characters are interchanged, and the remaining characters are left unchanged.

7. The method of claim 5, wherein said one or more distance one variants comprises single character wild card replacements of said at least one candidate word obtained by generating variants of said at least one candidate word by replacing any one character in said at least one candidate word with a chosen wild card character and leaving other characters unchanged, thereby generating W variants of said at least one candidate word of length W.

8. The method of claim 5, wherein said one or more distance one variants comprises single character wild card insertions of said at least one candidate word obtained by generating variants of said at least one word which comprise inserting a wild card character before or after any character of said at least one candidate word and leaving the other characters unchanged, thereby generating W+1 variants of said at least one candidate word of length W.

9. The method of claim 2, further comprising the step of testing said at least one candidate word against a deletion hash table, a deletions-transposition hash table, and a double deletion hash table and accumulating matches.

10. The method of claim 2, further comprising the steps of generating all adjacent character transpositions of said at least one candidate word and testing said adjacent character transpositions against transposition and deletion hash tables, and accumulating matches.

11. The method of claim 2, further comprising the steps of generating all single character deletions of said at least one candidate word and testing said single character deletions against transposition and deletion hash tables, and accumulating matches.

12. The method of claim 2, further comprising the steps of generating all single character replacements of said at least one candidate word and testing said single character replacements against a transposition-replacement, deletion-replacement, and insertion-replacement hash tables, and accumulating matches.

13. The method of claim 2, further comprising the steps of generating two character deletions of said at least one candidate word and testing said two character deletions against a double deletion hash table, and accumulating matches.

14. The method as recited in claim 2, further comprising a step of generating arbitrary character transpositions of said at least one candidate word by generating all variants of the candidate word wherein any one pair of not necessarily adjacent characters are interchanged, and the remaining characters are left unchanged.

15. The method of claim 2, further comprising the steps of generating all not necessarily adjacent character transpositions of said at least one candidate word and testing said not necessarily adjacent character transpositions against the transposition hash table and a deletion hash tables, and accumulating matches.

16. A system for correcting spelling of at least one candidate word, said system comprising:

a memory; and

at least one hardware processor, coupled to the memory, operative to;

obtain at least one variant dictionary hash table based on variants of a set of known correctly spelled words, wherein said variants are obtained by applying one or more of a deletion, insertion, replacement, and transposition operation on said correctly spelled words, wherein said variants obtained by applying one or more of an insertion and replacement operation on said correctly spelled words comprise a wildcard character, wherein for a given correctly spelled word having a length W, said at least one variant dictionary hash table comprises W of said variants each comprising said wildcard character in a different position, and wherein said variants are stored in said at least one variant dictionary hash table and are mapped to one of said corresponding correctly spelled words from said set of known correctly spelled words which are stored in a dictionary hash table that is distinct from said at least one variant dictionary hash table;

perform one or more of a deletion, insertion, replacement, and transposition operation on the at least one candidate word to obtain one or more lookup variants, wherein said lookup variants obtained by applying one or more of an insertion and replacement operation on said at least one candidate word comprise a wildcard character;

evaluate one or more of said lookup variants utilizing said at least one variant dictionary hash table to identify matches; and

indicate a candidate correction if said evaluation step indicates that there is at least one match in the at least one variant dictionary hash table.

18. The system of claim 16, wherein said dictionary hash table is pre-created prior to obtaining said candidate word, further comprising the step of obtaining said dictionary hash table having entries in a dictionary or known correctly spelled words and wherein said dictionary hash table and said at least one variant dictionary hash table are based on said dictionary and are comprised of at least one distance one variation for each of said entries, wherein said distance one variation comprises one or more of a deletion, insertion, replacement, and transposition operation performed on said entries;

and

wherein the step of evaluating said lookup variants utilizing said at least one variant dictionary hash table further comprises the step of evaluating one or more distance one variants utilizing said at least one variant dictionary hash table.

19. The system of claim 18, wherein said distance one variation comprises a replacement operation to generate a replacement hash table having entries of single character wild card replacements of said entries in said dictionary and said method further comprises the steps of generating single character replacements and insertions of said candidate word and comparing said single character replacements and insertions against said replacement hash table.

20. The system of claim 19, wherein the replacement hash table is obtained by:

generating variants of each word in the dictionary, each variant is comprised of replacing any one character in the word with a wild card character and leaving other characters unchanged, thereby generating W variants for each word of length W; and

for each generated variant of a word in the dictionary, storing a key-value pair in a hash table, wherein a key is a generated variant having a value that is the word itself.

21. The system of claim 18, further comprising the steps of generating one or more distance one variants of said at least one candidate word and testing said distance one variants against one or more of said dictionary hash table and said at least one variant dictionary hash table, and accumulating matches.

22. The system of claim 18, further comprising the steps of generating all adjacent character transpositions of said at least one candidate word and testing said adjacent character transpositions against transposition and deletion hash tables, and accumulating matches.

23. The system of claim 18, further comprising the steps of generating all single character deletions and replacements of said at least one candidate word and testing said single character deletions and replacements against transposition, transposition-replacement, deletion-replacement, insertion-replacement and deletion hash tables, and accumulating matches.

24. The system of claim 18, further comprising the steps of generating two character deletions of said at least one candidate word and testing said two character deletions against a double deletion hash table, and accumulating matches.

17. An article of manufacture for correcting spelling of at least one candidate word, comprising a non-transitory computer readable medium containing one or more programs which when executed implement the steps of:

obtaining at least one variant dictionary hash table based on variants of a set of known correctly spelled words, wherein said variants are obtained by applying one or more of a deletion, insertion, replacement, and transposition operation on said correctly spelled words, wherein said variants obtained by applying one or more of an insertion and replacement operation on said correctly spelled words comprise a wildcard character wherein for a given correctly spelled word having a length W, said at least one variant dictionary hash table comprises W of said variants each comprising said wildcard character in a different position, and, wherein said variants are stored in said at least one variant dictionary hash table and are mapped to one of said corresponding correctly spelled words from said set of known correctly spelled words which are stored in a dictionary hash table that is distinct from said at least one variant dictionary hash table;

performing one or more of a deletion, insertion, replacement, and transposition operation on the at least one candidate word to obtain one or more lookup variants, wherein said lookup variants obtained by applying one or more of an insertion and replacement operation on said at least one candidate word comprise a wildcard character;

evaluating one or more of said lookup variants utilizing said at least one variant dictionary hash table to identify matches; and

indicating a candidate correction if said evaluation step indicates that there is at least one match in the at least one variant dictionary hash table.