Typo-tolerant search with Damerau-Levenshtein edit distance

Type "kayboard" into a search box that only matches exact terms, and you get zero results for a product that exists. Every search engine that claims typo tolerance is really claiming: given a misspelled query, can it still find what you meant, without also matching so loosely that unrelated terms start showing up? That's a harder balance than it sounds.

Edit distance, and why the "Damerau" part matters

Levenshtein distance counts the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into another. "kayboard" → "keyboard" is one substitution: distance 1.

Plain Levenshtein distance treats a transposition — two adjacent characters swapped, like "kaeyboard" → "keyboard" — as two edits (delete + insert, or two substitutions), even though it's the single most common typo humans actually make. Damerau-Levenshtein distance adds transposition as its own edit operation, so a swapped pair costs 1, not 2. That one addition is the difference between matching a large share of real-world fat-finger typos on one edit versus requiring two.

Tachyon uses Damerau-Levenshtein distance for exactly this reason — see Typo Tolerance for the collection-level configuration.

Why a fixed tolerance doesn't work

The obvious next question: how many edits should be allowed? A fixed tolerance — say, "always allow 1 edit" — breaks in both directions.

For short tokens, one edit is enormous relative to the word. "cat" at distance 1 matches "bat", "car", "cats", "at", and more — the query stops meaning anything close to what was typed. For long tokens, one edit is barely a typo tolerance at all: a query for a 12-character technical term with two small mistakes gets no leniency, even though a human reading it would recognize it instantly.

The fix is scaling allowed edit distance to token length rather than fixing it globally. Tachyon's default thresholds: tokens under 4 characters must match exactly, tokens from 4–7 characters get one allowed edit, and tokens of 8 or more get two — configurable per collection via one_typo_min_len/two_typo_min_len/max_typos in Typo Tolerance. Short tokens stay precise; long tokens get real leniency; nothing in between is either too loose or too strict by a fixed global rule that can't fit both cases.

The cost side of the tradeoff

Typo-tolerant matching isn't free — every query token potentially expands into a set of candidate terms within the allowed edit distance, which has to be computed efficiently against the whole vocabulary rather than by brute- force comparison against every indexed term. This is exactly why the length-scaled thresholds matter operationally, not just for match quality: capping the search radius (max_typos) bounds how much candidate expansion a single query can trigger, which is what keeps typo-tolerant search fast enough to run on every query by default instead of being an expensive opt-in feature.

That's the design goal behind Tachyon's defaults: typo tolerance on for every query, with thresholds tuned so it stays both accurate and cheap enough to not need to be turned off.