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

Compute unit-cost insertion/deletion/substitution distance between exact code-point sequences. Case conversion, normalization, and transposition are different operations and are outside this distance.

Uncached recursive prefix comparisons repeat overlapping subproblems. A full matrix makes dependencies explicit, then a rolling pair of rows can retain only the previous/current frontier for a distance-only result.

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.

Distance between prefixes depends on substitution/match, deletion, and insertion. One previous row plus the current row retains those dependencies without storing the entire matrix. Swapping the shorter input into the columns bounds workspace. Final O(nm) time and O(min(n,m)) DP workspace, plus Unicode conversion arrays.

Java char length does not measure the unit used by this contract. Convert deliberately before reasoning about empty-prefix distance:

import java.util.*;

class Example {
    public static void main(String[] args) {
        String text = "😀a";
        int utf16Units = text.length();
        int codePoints = text.codePointCount(0, text.length());
        assert utf16Units == 3;
        assert codePoints == 2;
        assert "é".equals("é") == false;
    }
}

Changing units would charge a different number of deletions for the same supplementary symbol. Keeping exact normalization forms also means visually similar strings can have nonzero distance. Row compression must retain diagonal, above, and left dependencies before overwriting them.

Distance is not the whole search engine

Edit distance is useful for approximate matching and comparison, provided the chosen edit costs and text unit fit the domain. User-visible grapheme distance and domain-specific operations may need a different representation and recurrence.

Return unit-cost Levenshtein distance over exact Unicode code points. Transposition is two edits; case and normalization forms remain distinct. Empty-string distance equals the other string's code-point count. Java char iteration is insufficient for supplementary characters.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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