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

Edit distance compares two prefixes. The last edit is an insertion, deletion, or substitution; matching final code points adds no cost. Base rows represent converting an empty prefix into a nonempty one.

Comparing prefixes instead of edit sequences

For ab and acb, inserting c is enough. A table cell describes a pair of prefix lengths, not two character indices. Its final step either deletes from the left, inserts from the right, or aligns both final characters with a match or substitution. Only the previous row and current row's preceding cell are needed to compute the next value.

left, right := []rune("a"), []rune("acb")
previous, current := []int{0, 1, 2, 3}, []int{1}
j, cost := 1, 0 // Compute the first cell, matching "a" with "a".
if left[0] != right[j-1] {
	cost = 1
}
best := previous[j] + 1 // Delete the left symbol.
if candidate := current[j-1] + 1; candidate < best {
	best = candidate
}
if candidate := previous[j-1] + cost; candidate < best {
	best = candidate
}
current = append(current, best)
fmt.Println(current) // [1 0]: the diagonal match beats either edit.

Distance is not the whole search engine

Each row depends only on the previous row and its own previous cell. Retain the shorter dimension for the DP buffer, while accounting separately for rune-decoding storage. The number measures edit cost, not a sequence of edits. Reconstruction needs retained decisions or a divide-and-conquer method. Autocorrection and data reconciliation use this model, but linguistic similarity may need weighted edits.

The recurrence evaluates O(nm) prefix pairs. Two rows use O(min(n,m)) DP storage when the shorter text indexes columns, in addition to any decoded input arrays. Returning an edit script needs extra reconstruction work. Transposing adjacent symbols is not a single Levenshtein edit.

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