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

1. Field of the Invention

The present invention generally relates to a very fast method for correcting the spelling of a word or phrase in a document. The method has application to any technique which searches documents.

2. Background Description

Suppose that we are given a word, G, and we wish to find one or more other words from a list of candidate words that are within a given edit distance from G. Here, the edit distance between two words is the smallest number of operations which transform the candidate word into the given word (each operation consisting of removing one letter, adding one letter, replacing one letter with another letter, or transposing two letters).

In “The String-to-String Correction Problem”, JACM, 21(1), pp. 168-173 (1974), R. A. Wagner and M. J. Fischer showed that the edit distance between two words G and C could be computed in time proportional to the length of G times the length of C. Subsequently, in “Algorithms for Approximate String Matching”, Information and Control, 64, pp. 100-118 (1985), E. Ukkonen improved the running time of the algorithm. This latter result is called the “slow method” in the following description.

According to the invention, there is provided a method which proceeds in two steps: first applying a very fast method (comparing G to each candidate word) for eliminating most candidate words from consideration (without computing the exact edit distance between G and any candidate word), followed by the “slow method” which computes the exact edit distance between G and each of the few remaining candidate words. The second step is the slow exact method well-known in the art as described by Ukkonen.

The invention consists of (1) a new fast approximate method and (2) combining this fast approximate method with the slow method. The combination results in a method that is almost as fast as the fast approximate method and as exact as the slow method.

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIGS. 1A and 1B, taken together, are a flow diagram showing the logic of the algorithm implemented by the invention.

In the following discussion, the following definitions are used:

G is the given word whose spelling is to be corrected.

S is the set of candidate words or phrases to be processed.

Δ is the maximal edit distance for determining whether a candidate word is acceptable; i.e., if the edit distance between G and a candidate word C exceeds Δ, then C is unacceptable.

W is the set of words that are within distance Δ of G.

G poll is a vector indexed by the letters of the alphabet under consideration.

We now explain the fast approximate method for deciding whether to eliminate candidate word C from consideration. We first pre-compute a vector G poll whose length is the number of letters (or, more generally, legal characters) in the alphabet from which G is constructed. The value of each component of G poll is the number of times the letter corresponding to that component appears in G. The method proceeds by iterating on the letters in C. Two integers are defined: C val (initially set to zero) counts the number of letters already considered in C which do not appear in G, and G val (initially set to the length of G) counts the number of letters in G which do not appear among the characters already considered in C. To process the next letter l in C, we check the count in the corresponding entry of G poll . If that entry is positive, we decrement both G val and the value of the lth component of G poll by one. If that entry is zero, we increment C val by one. After a letter from C is processed, if C val is larger than Δ, we reject C from consideration (i.e., C is unacceptable). We continue letter by letter until either C has been rejected or all its letters have been processed. In the latter case, if G val is larger than Δ, then we reject C from consideration. Otherwise, we accept C and compute its exact edit distance from G by the slow method. We proceed until all candidate words have been processed.

Referring now to the drawings, and more particularly to FIGS. 1A and 1B, there is shown a flow diagram of the logic of the process according to the invention. The process begins by inputting a list of candidate words at function block 101 . A test is made in decision block 102 to determine if all words from the candidate word list have been processed. If so, the process returns the set of words W to the main program; otherwise, the next (non-null) candidate word is accessed in function block 103 . In function block 104 , the value of the integer C val is initialized and set to zero. In function block 105 , the value of the integer G val is initialized and set to the length of the given word G. In function block 106 , the vector G poll is initialized by setting its entries equal to the number of times each corresponding letter of the alphabet appears in the word G. The next letter l of the candidate word C is accessed in function block 107 . A test is made in decision block 108 to determine if G poll (l) is greater than zero. If so, G poll (l) is decremented by one in function block 109 , and Gval is decremented by one in function block 110 . The process then proceeds to decision block 113 . If, however, G poll (l) is zero, then C val is incremented by one in function block 111 . A test is made in decision block 112 to determine if C val is greater than the maximal edit distance Δ. If so, the process loops back to decision block 102 to determine if there are more words to be processed. If not, the process proceeds to decision block 113 .

A test is made in decision block 113 to determine if all letters have been processed. If not, then the process loops back to function block 107 to access the next letter. Otherwise, a test is made in decision block 114 to determine if G val is less than or equal to the maximal edit distance Δ. If not, the process then loops back to decision block 102 to determine if there are more words to process. If so, Δ c is set (using the slow method) to the distance between the candidate word C and the word G whose spelling is to be corrected in function block 115 . A test is then made in decision block 116 to determine if the distance Δ c is less than or equal to the maximal edit distance Δ. If it is, C is added to W. The process then loops back to decision block 102 to determine if there are more words to process.

The pseudocode that implements the process shown in FIGS. 1A and 1B is listed below:

For each candidate word C of S

C val =0

G val =Length(G)

G poll (l)=number of times letter l appears in G

For each letter Q of C

If G poll (l)>0 then

G poll (l)=G poll (l)−1

G val =G val −1

Else

C val =C val +1

If C val >Δ then Process next candidate word

If G val ≦Δ then

Δ c =distance between C and G

If Δ c ≦Δ then add C to W

Process next candidate word

While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.