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

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 Gpoll whose length is the number of letters in the alphabet from which G is constructed, the value of each component of Gpoll 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 Cval which counts a number of letters already considered in C which do not appear in G, and Gval 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 Gpoll, and if that entry is positive, decrementing both Gval and the value of the lth component of Gpoll by one, but if that entry is zero, incrementing Cval by one;
• code for determining if Cval 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 Gval is larger than Δ, then rejecting C from consideration, but otherwise, accepting C, provided its actual distance from G is not more than Δ.