levenshtein.nx

levenshtein.nx -- Levenshtein edit distance. Computes the minimum number of single-character edits (insertions, deletions, substitutions) needed to transform string A into string B. Used for: typo correction, fuzzy search, near-duplicate detection, "did you mean" suggestions. Wagner-Fischer dynamic programming (1974). O(m * n) time, O(min(m, n)) space using the two-row optimisation. Invariants: LV1 Symmetric: distance(a, b) == distance(b, a) LV2 distance(a, "") == len(a); identity-distance is 0 LV3 Triangle inequality holds: distance(a, c) <= distance(a, b) + distance(b, c) LV4 Byte-level (not codepoint-level). ASCII text behaves as expected; multi-byte UTF-8 counts each byte as a distinct symbol -- callers wanting codepoint distances decode to int sequences first.