How fuzzy search works: typo-tolerant matching explained

Type hxvault into a good command palette and it finds helix_vault. Type mainrs and it finds src/main.rs. No wildcards, no exact spelling, and often a typo or two forgiven. This behavior - fuzzy search - has become the default way developers and power users navigate everything from code editors to file managers. Here is how it actually works, with a live demo you can type into.

Try it first

This is a real fuzzy matcher running in your browser - a miniature version of the algorithm family used by tools like fzf, VS Code's quick-open, and Shuffle's command palette. The highlighted letters show which characters matched; the number is the match's score.

Step 1: subsequence matching

The core rule is simpler than most people expect: every character of the query must appear in the candidate, in order - but not necessarily adjacent. hxvault matches helix_vault because you can walk left to right and find h, then x, then v-a-u-l-t. That check is a single linear scan per candidate: for each query character, find its next occurrence in the text. If any character can't be found, the candidate is out.

Subsequence matching alone is binary - match or no match. The magic that makes fuzzy search feel smart is what happens next.

Step 2: scoring - the interesting part

A query like doc matches hundreds of paths. The ranking is what decides whether the one you meant is at the top. Practical scorers reward and penalize a handful of things:

• Consecutive runs. Matching d-o-c as an unbroken run in Documents is worth much more than three scattered letters. Real typing tends to produce prefixes and runs, so runs are strong intent signals.
• Word boundaries. A hit on the first letter after a /, _, -, ., or a lowercase-to-uppercase transition (camelCase) scores a bonus. This is why ffm finds fast-file-manager: three boundary hits beat any buried substring.
• Gap penalties. Every character skipped between matches costs a little. Tight matches beat sprawling ones.
• Length bias. All else equal, shorter candidates win - matching 5 of 10 characters is more meaningful than 5 of 80.

The demo above implements exactly these four rules in about thirty lines. Production matchers refine the weights - fzf's v2 algorithm is a variant of Smith-Waterman alignment, borrowed from bioinformatics, which uses dynamic programming to find the optimal assignment of query characters to positions rather than the greedy first-occurrence walk. Greedy is faster; alignment ranks better when a character could match in several places.

Step 3: typo tolerance

Strict subsequence matching fails the moment you transpose two letters - hlexi no longer matches helix. Tools that forgive typos bring in a second concept: edit distance. The Levenshtein distance between two strings is the minimum number of single-character insertions, deletions, and substitutions to turn one into the other (the Damerau variant adds transpositions, the most common real typo). A typo-tolerant matcher accepts candidates within a small distance budget - usually 1 for short queries, 2 for longer ones - and applies a score penalty per correction, so exact matches still rank first.

Computing edit distance for every candidate is more expensive than a linear scan, so engines use tricks to avoid doing it often: try the cheap subsequence pass first and only fall back to fuzzy-with-typos when it yields nothing, or use banded dynamic programming that abandons a candidate as soon as its minimum possible distance exceeds the budget.

Making it fast at file-system scale

A code editor fuzzy-searches a few thousand project files. A file manager's palette searches your home directory - easily half a million paths. At that scale the per-candidate cost dominates, and three engineering choices matter:

1. Index up front. Walk the directory tree once in the background and keep the paths in a compact in-memory list, rather than hitting the file system per keystroke.
2. Filter cheaply, score selectively. The binary subsequence test eliminates most candidates in nanoseconds; only survivors get the expensive scoring pass.
3. Search incrementally. When the query grows from doc to docu, every match of the longer query is necessarily a match of the shorter one - so you can search within the previous result set instead of the full corpus.

Do all three and ranking half a million paths takes single-digit milliseconds - which is why a well-built palette can re-rank the whole list on every keystroke and still feel instant. That budget question - what has to happen inside one frame - is a topic of its own; we cover it in What makes a file manager fast?

Where you've already used this

Fuzzy matching quietly became a standard interface: Sublime Text's Goto Anything popularized it in 2008, VS Code's ⌘P made it universal, fzfbrought it to the shell, and launchers like Alfred and Raycast brought it to the whole OS. File managers were late to the party - Finder still offers only exact-prefix "type-select" and full Spotlight search, with nothing in between. Shuffle's ⌘P palette exists precisely to fill that gap: typo-tolerant fuzzy search over your home directory, with the same subsequence-plus-boundaries scoring you just played with above - tuned so results update in about a millisecond.