Edit distance

A catalog search gets a product name with a typo. Exact equality finds nothing, but the app can compare the query with a small candidate list and rank names by how many character edits separate them.

Trying every possible edit sequence repeats the same comparisons. Levenshtein distance records answers for pairs of prefixes, using insertion, deletion, and substitution at unit cost. It measures those edits, not whether two names mean the same thing.

Ranking a misspelled catalog query

Levenshtein distance is the fewest unit-cost insertions, deletions and substitutions needed to transform one string into another. Exact matching is one endpoint of approximate text comparison. Transposing adjacent characters is not an allowed single edit, so ab to ba needs two edits.

A recursive prototype compares prefixes and branches over their possible final edits. Repeated prefix pairs appear many times; dynamic programming stores each answer once.

Comparing prefixes instead of edit sequences

For prefix lengths i and j, deletion uses the previous row's same column, insertion uses the current row's previous column, and alignment uses the previous diagonal plus zero or one depending on equality. Empty-prefix boundaries encode inserting or deleting every code point.

A distance-only result needs only the previous row. Updating one row in place also works if the old diagonal is saved before overwriting a cell. Put the shorter string on the column axis to bound DP row storage by O(min(n,m)). Converting both inputs to complete code-point arrays adds O(n+m) representation storage, so distinguish that from recurrence state; iterating the longer input avoids its copy.

Compare Unicode code points, not UTF-16 code units or visible graphemes. A supplementary symbol is one edit unit. A composed accent and its combining sequence may have different distance because canonical normalization is deliberately absent.

const supplementary = Array.from("😀");
const combining = Array.from("é");
console.log(supplementary.length, combining.length); // 1 2
const emptyToPrefix = [0, 1, 2, 3];
console.log(emptyToPrefix[3]); // 3 insertions from empty to a three-point prefix

Distance is not the whole search engine

The uncached prototype can be exponential. Final DP costs O(nm) time and O(min(n,m)) row state. Retaining a full table is useful when reconstructing an edit script but unnecessary for distance alone. This is a precise unit-cost model; weighted edits or transposition-aware spelling distance require altered recurrences.

A production catalog still needs a way to find plausible candidates before comparing their edit distances.