Career Catalogue
Switch tool

Engineering lab

Fuzzy-search lab

Try a small search problem before taking the idea into production. Compare exact matching with edit distance and see where typo tolerance introduces irrelevant results.

What you leave with An inspectable comparison and a threshold you can explain.

Compare your candidates

Up to 64 characters. Case and surrounding whitespace are ignored.

Up to 50 non-empty lines and 64 characters per candidate. Blank lines and repeated normalized candidates are ignored.

Try one real typo from your domain, with its intended result and a confusing near-match in the candidate list.

An insertion, deletion or substitution costs one edit. Swapping two letters costs two.

Reset replaces the query, candidates and threshold with the example above. Inputs are not saved.

Exact versus fuzzy

Try it before reading on

Recover the occupation, exclude the distraction

For the fixed query plumbr and candidates plumber and plumper, choose the smallest threshold that accepts the occupation and excludes the unrelated word. This exercise uses those fixed words, even if you change the lab inputs.

The worked example

plumbr → plumber: insert e before the last letter. Distance 1.

plumbr → plumper: replace b with p, then insert e. Distance 2.

At threshold 0 neither matches. At threshold 1 only plumber matches. At threshold 2 both match, although plumper is not the trade the person wanted. The threshold cannot infer that intent.

Before adopting fuzzy search, collect real misspellings and confusing near-matches from your own domain. Check both the useful results you recovered and the irrelevant results you introduced.

Inspect the algorithm and its edge cases

This is the same two-row dynamic-programming recurrence used by the lab. Inputs are trimmed, lowercased and normalized to Unicode NFC before comparison. Accents remain significant; each Unicode code point counts as a character.

function distance(left, right) {
  const a = Array.from(left), b = Array.from(right);
  let previous = Array.from({ length: b.length + 1 }, (_, j) => j);
  for (let i = 1; i <= a.length; i++) {
    const current = [i];
    for (let j = 1; j <= b.length; j++) {
      current[j] = Math.min(
        current[j - 1] + 1,                    // insert
        previous[j] + 1,                       // delete
        previous[j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1)
      );                                       // match or substitute
    }
    previous = current;
  }
  return previous[b.length];
}

Time grows with the product of the string lengths. Two rows keep memory proportional to the candidate length. The lab validates its input limits before computing and compares at most 50 candidates of 64 characters.

Useful checks for an implementation
LeftRightDistanceChecks
""cat3All characters inserted
kittensitting3Two substitutions and one insertion
abba2Transposition is not a single operation here
😀""1One code point, rather than two UTF-16 units

The algorithm can compare an empty string; the search form asks for a non-empty query so the result has a useful meaning. It compares whole candidate strings, rather than finding matching words inside a sentence.

Read the lab’s complete calculation and validation source.

The lab runs in your browser. Your query and candidate list stay on this page and are not saved or sent to a service.