Two step method for correcting spelling of a word or phrase in a document

• US 6,616,704 B1
• Filed: 09/20/2000
• Issued: 09/09/2003
• Est. Priority Date: 09/20/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Milch, Daniel, Leeman, Jr., George B., Hantler, Sidney L., Gail, Jr., Harry R., Birman, Alexander
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US09/665,897
• Time in Patent Office: 1,084 Days
• Field of Search: 707/532, 707/533, 707/531, 715/532, 715/533, 715/531
• US Class Current: 715/234
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A very fast method for correcting the spelling of a word or phrase in a document proceeds in two steps: first applying a very fast approximate method for eliminating most candidate words from consideration (without computing the exact edit distance between the given word whose spelling is to be corrected and any candidate word), followed by a “slow method” which computes the exact edit distance between the word whose spelling is to be corrected and each of the few remaining candidate words. The combination results in a method that is almost as fast as the fast approximate method and as exact as the slow method.

Claims

1. A method for correcting the spelling of a word or phrase in a document comprising the steps of:

applying an approximate method for eliminating some candidate words from consideration, without computing an exact edit distance between a given word whose spelling is to be corrected and any candidate word;

followed by applying an exact method which computes an exact edit distance between the word whose spelling is to be corrected and each of the remaining candidate words, wherein G is a given word whose spelling is to be corrected and the approximate method comprises the steps of;

pre-computing a vector G_poll whose length is the number of letters in the alphabet from which G is constructed, the value of each component of G_poll being a number of times a letter corresponding to that component appears in G;

iterating on the letters in the candidate word or phrase C to be processed by defining two integers C_val which counts a number of letters already considered in C which do not appear in G, and G_val which counts a number of letters in G which do not appear among the characters already considered in C;

processing a next letter l in C by checking a count in a corresponding entry of G_poll, and if that entry is positive, decrementing both G_val and the value of the lth component of G_poll by one, but if that entry is zero, incrementing C_val by one;

determining if C_val is larger than a maximal edit distance Δ

, rejecting C from consideration; and

continuing letter by letter until either C has been rejected or all its letters have been processed, and in the latter case, if G_val is larger than Δ

, then rejecting C from consideration, but otherwise, accepting C, provided its actual distance from G is not more than Δ

.

2. The method for correcting the spelling of a word or phrase in a document recited in claim 1, wherein the exact method comprises the step of computing an exact edit distance from G.

3. A computer readable medium containing code implementing a method for correcting the spelling of a word or phrase in a document, the code contained in said computer readable medium comprising:

first code implementing an approximate method for eliminating most candidate words from consideration, without computing an exact edit distance between a given word whose spelling is to be corrected and any candidate word; and

second code implementing an exact method which computes an exact edit distance between the word whose spelling is to be corrected and each of the few remaining candidate words, said second code being called after execution of said first code, wherein G is a given word whose spelling is to be corrected and the first code includes;

code for pre-computing a vector G_poll whose length is the number of letters in the alphabet from which G is constructed, the value of each component of G_poll being a number of times a letter corresponding to that component appears in G;

code for iterating on the letters in the candidate word or phrase C to be processed by defining two integers C_val which counts a number of letters already considered in C which do not appear in G, and G_val which counts a number of letters in G which do not appear among the characters already considered in C;

code for processing a next letter l in C by checking a count in a corresponding entry of G_poll, and if that entry is positive, decrementing both G_val and the value of the lth component of G_poll by one, but if that entry is zero, incrementing C_val by one;

code for determining if C_val is larger than a maximal edit distance Δ

, rejecting C from consideration; and

code for continuing letter by letter until either C has been rejected or all its letters have been processed, and in the latter case, if G_val is larger than Δ

, then rejecting C from consideration, but otherwise, accepting C, provided its actual distance from G is not more than Δ

.

4. The computer readable medium recited in claim 3, wherein second code includes code for computing an exact edit distance from G.