String matching and fuzzy search

Levenshtein: insert, delete or substitute, 1 each.

OSA (optimal string alignment, "restricted Damerau"): also swaps two adjacent letters for 1, but never edits a substring twice. That makes CA → ABC cost 3, although CA → AC → ABC costs 2, so OSA breaks the triangle inequality. Lucene counts this when transpositions is true.

Damerau: the true Damerau–Levenshtein distance (Lowrance and Wagner, 1975). Letters may be inserted between a swapped pair, so CA → ABC costs 2. It is a metric.

LCS (longest common subsequence): only insertions and deletions; diff tools use it.

Substring: the longest common contiguous run.

Hamming: positions that differ, for equal lengths.

The diagram lays states out by distance from the start. Accepting states are double circles and edge labels list letters (¬ab means any letter but a and b). Tap a state to list the (i, e) pairs it stands for. Fit scales the drawing to the box; 100% draws it full size with scrolling. Transition table lists the same automaton as rows.

Run a word through it: the path lights up. The tool says where the word is rejected and checks the answer against the distance computed by dynamic programming.

Against a term dictionary: the automaton walks a trie of the built-in 8,000-word list (or your own terms) depth-first in sorted order. That is the idea behind Lucene’s Terms.intersect: a branch is abandoned the moment no state is left. The tool counts how much of the trie was visited and compares the matches with a brute-force distance check of every term (they always agree). The walk itself is listed underneath.

Levenshtein, "Binary codes capable of correcting deletions, insertions and reversals" (1966): kitten → sitting = 3. Damerau (1964), and Lowrance and Wagner, "An extension of the string-to-string correction problem", JACM 1975: CA → ABC is 2 for the true distance and 3 for OSA.

Jaro (1989) and Winkler (1990), as tabulated in the Wikipedia article: MARTHA/MARHTA 0.944 / 0.961, DWAYNE/DUANE 0.822 / 0.840, DIXON/DICKSONX 0.767 / 0.813.

K. Schulz and S. Mihov, "Fast string correction with Levenshtein automata", IJDAR 2002, and Lucene’s LevenshteinAutomata and FuzzyQuery (maxEdits ≤ 2, prefixLength, transpositions true by default). The tests check the automaton against brute-force distances on the whole word list and on thousands of random strings. Elasticsearch’s fuzziness AUTO means 0 edits below 3 characters, 1 for 3–5 and 2 above.

American Soundex as the US National Archives defines it: Robert and Rupert R163, Rubin R150, Ashcraft and Ashcroft A261 (H and W do not separate), Tymczak T522, Pfister P236 (a letter coded like the first letter is not repeated), Honeyman H555.

Metaphone: Lawrence Philips, "Hanging on the Metaphone", Computer Language 7(12), 1990. This page follows the rule order of Apache Commons Codec’s Metaphone (the tests use values from its test suite, such as TESTING → TSTN and SCHEDULE → SKTL), with Philips' CH → X throughout. Metaphone implementations differ in small ways.

Double Metaphone: Lawrence Philips, "The Double Metaphone search algorithm", _C/C Users Journal_, June 2000. This is a port of his C reference via the Python metaphone package. It matches that package on over a hundred names, except Hugh, where the Python port has a known slip and this page follows the C++. Smith → SM0 / XMT and Schmidt → XMT / SMT.

NYSIIS: R. L. Taft, "Name Search Techniques", New York State Identification and Intelligence System, 1970, in the commonly published form. It matches the jellyfish library. Taft truncated codes to 6 characters (an option here).

pg_trgm: show_trgm('word') = {" w"," wo","ord","rd ","wor"}; for 'word' against 'two words', similarity 0.363636, word_similarity 0.8 and strict_word_similarity 0.571429.

Peter Norvig, How to write a spelling corrector. The word counts are the 8,000 most frequent words of his big.txt. Tests: speling → spelling, korrectud → corrected, bycycle → bicycle, inconvient → inconvenient, arrainged → arranged, peotry → poetry, peotryy → poetry. edits1('somthing') has 442 strings.

Edit-distance strings are capped at 40 characters. Costs are all 1 (no weighted or keyboard-distance costs).

Automaton terms are capped at 16 letters and edits at 2, like Lucene. The page determinises generically instead of using Lucene’s precomputed parametric tables, so the state counts are those of the minimal DFA, not of Lucene’s internal representation. Letters are compared exactly (no case folding), and a character is one Unicode code point.

The phonetic codes are for English names: accents are stripped and non-letters are ignored, and other languages need their own rules (Cologne phonetics, Beider–Morse).

The spelling corrector knows 8,000 words. Norvig’s full list (about 30,000) corrects more, and rarer correct words may be "corrected" here. It ignores context.

Trigram similarity follows pg_trgm’s rules for letters and digits. PostgreSQL’s handling of some non-ASCII characters depends on its locale.