Fuzzy & Prefix Search
Exact match fails two ways users hit every day, typos and half-typed queries. Here is the machinery that forgives both.
Part three of the search series. The inverted index only matches literal keys, so a typo or a half-finished word returns nothing. Fuzzy search fixes typos with edit distance (Levenshtein), computed by a small dynamic-programming grid and run at scale with automata or n-grams. Prefix search fixes as-you-type with tries and FSTs. Worked examples throughout, plus an interactive edit-distance grid.
- Search
