Edit distance measures how many character-level edits separate two strings. In search, it compares likely misspellings with frequent correction candidates so spelling suggestions can improve query relevance. section 6.5.2
A practical spelling-correction pipeline uses edit distance alongside query behavior:
- Build misspelling and correction candidates from low- and high-frequency query terms. section 6.5.2
- Compare candidates sharing an initial character, calculate their edit distance, and filter matches using term-length thresholds. section 6.5.2
- Prefer frequent correction terms when several nearby spellings are possible. section 6.5.2
Worked query correction
The query term “moden” is one edit from “modem” and is mapped to that frequent correction rather than to less likely alternatives such as “model” or “modern.” section 6.5.2
Listing 6.19 Mapping misspellings to their correct spellings
from nltk import edit_distance
def calculate_spelling_corrections(word_list):
(misspellings, corrections) = create_spelling_candidates(word_list)
matches_candidates = pandas.merge(misspellings, #1
corrections, on="initial") #1
matches_candidates["edit_dist"] = matches_candidates.apply(
lambda row: edit_distance(row.misspelling, #2
row.correction), axis=1) #2
matches_candidates["good_match"] = matches_candidates.apply(
lambda row: good_match(row.misspell_length, #3
row.correction_length, #3
row.edit_dist),axis=1) #3
cols = ["misspelling", "correction", "misspell_counts",
"correction_counts", "edit_dist"]
matches = matches_candidates[matches_candidates["good_match"]] \
.drop(["initial", "good_match"],axis=1) \
.groupby("misspelling").first().reset_index() \ #4
.sort_values(by=["correction_counts", "misspelling", #4
"misspell_counts"], #4
ascending=[False, True, False])[cols] #4
return matches
query_signals = get_search_queries()
word_list = valid_keyword_occurrences(query_signals, tokenize=True)
corrections = calculate_spelling_corrections(word_list)
display(corrections.head(20)) #5
Inspect the Python implementation that calculates edit distances with NLTK and filters matches through a configurable length-based heuristic. section 6.5.2
