Text Similarity & Diff Toolkit

Comparison Semantics and Tokenization

A comparison algorithm operates on tokens, so bytes, code points, grapheme clusters, words, lines, and syntax nodes define different optimization problems. Specify normalization, case policy, whitespace handling, edit costs, move detection, and deterministic tie-breaking before computing a score. Preserve original slices for display even when normalized tokens are compared.

Tokenization changes the optimization problem, not merely its presentation: a minimum line edit script need not induce a minimum word or grapheme edit script. Record the unit, normalization, cost model, and tie-breaking policy with every score or diff.

LCS and Edit-Script Engines

LCS maximizes retained ordered tokens and yields a shortest insertion/deletion script. Levenshtein instead minimizes insertion, deletion, and substitution costs. Full tables support direct traceback in $O(nm)$ space; rolling rows compute only the score in linear space, while Hirschberg reconstructs an LCS in $O(nm)$ time and $O(\min(n,m))$ auxiliary space.

from dataclasses import dataclass
from typing import Generic, Literal, Sequence, TypeVar

T = TypeVar("T")
Operation = Literal["equal", "delete", "insert", "replace"]

@dataclass(frozen=True)
class Edit(Generic[T]):
    operation: Operation
    old: T | None
    new: T | None

def lcs_row(a: Sequence[T], b: Sequence[T]) -> list[int]:
    previous = [0] * (len(b) + 1)
    for x in a:
        current = [0]
        for j, y in enumerate(b, 1):
            current.append(previous[j - 1] + 1 if x == y else max(previous[j], current[-1]))
        previous = current
    return previous

def hirschberg(a: Sequence[T], b: Sequence[T]) -> list[T]:
    if not a or not b:
        return []
    if len(a) == 1:
        return [a[0]] if a[0] in b else []
    mid = len(a) // 2
    forward = lcs_row(a[:mid], b)
    backward = lcs_row(a[mid:][::-1], b[::-1])
    split = max(range(len(b) + 1), key=lambda j: forward[j] + backward[len(b) - j])
    return hirschberg(a[:mid], b[:split]) + hirschberg(a[mid:], b[split:])

def lcs_diff(a: Sequence[T], b: Sequence[T]) -> list[Edit[T]]:
    common = hirschberg(a, b)
    edits: list[Edit[T]] = []
    i = j = 0
    for token in common:
        while a[i] != token:
            edits.append(Edit("delete", a[i], None)); i += 1
        while b[j] != token:
            edits.append(Edit("insert", None, b[j])); j += 1
        edits.append(Edit("equal", token, token)); i += 1; j += 1
    while i < len(a):
        edits.append(Edit("delete", a[i], None)); i += 1
    while j < len(b):
        edits.append(Edit("insert", None, b[j])); j += 1
    return edits

def levenshtein_trace(a: Sequence[T], b: Sequence[T]) -> tuple[int, list[Edit[T]]]:
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    parent: list[list[Operation | None]] = [[None] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1): d[i][0], parent[i][0] = i, "delete"
    for j in range(1, len(b) + 1): d[0][j], parent[0][j] = j, "insert"
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            diagonal = (d[i-1][j-1] + (a[i-1] != b[j-1]), 0, "equal" if a[i-1] == b[j-1] else "replace")
            cost, _, op = min(diagonal, (d[i-1][j] + 1, 1, "delete"), (d[i][j-1] + 1, 2, "insert"))
            d[i][j], parent[i][j] = cost, op  # type: ignore[assignment]
    edits: list[Edit[T]] = []
    i, j = len(a), len(b)
    while i or j:
        op = parent[i][j]
        if op in ("equal", "replace"):
            edits.append(Edit(op, a[i-1], b[j-1])); i -= 1; j -= 1
        elif op == "delete": edits.append(Edit(op, a[i-1], None)); i -= 1
        elif op == "insert": edits.append(Edit(op, None, b[j-1])); j -= 1
        else: raise AssertionError("missing parent")
    edits.reverse()
    return d[-1][-1], edits

def apply(source: Sequence[T], edits: Sequence[Edit[T]]) -> list[T]:
    output: list[T] = []; i = 0
    for edit in edits:
        if edit.operation == "equal": assert source[i] == edit.old == edit.new; output.append(edit.new); i += 1  # type: ignore[arg-type]
        elif edit.operation == "replace": assert source[i] == edit.old; output.append(edit.new); i += 1  # type: ignore[arg-type]
        elif edit.operation == "delete": assert source[i] == edit.old; i += 1
        else: output.append(edit.new)  # type: ignore[arg-type]
    assert i == len(source)
    return output

if __name__ == "__main__":
    distance, script = levenshtein_trace(list("kitten"), list("sitting"))
    assert distance == 3 and apply(list("kitten"), script) == list("sitting")
    diff = lcs_diff(list("ABCBDAB"), list("BDCABA"))
    assert apply(list("ABCBDAB"), diff) == list("BDCABA")
    assert len(hirschberg(list("ABCBDAB"), list("BDCABA"))) == 4

Alignment and Similarity Modes

Different objectives can give similar scores but different witnesses. LCS models insertions and deletions; Levenshtein permits substitution; Needleman-Wunsch aligns complete sequences; Smith-Waterman finds the best local region; Gotoh distinguishes gap opening from extension. Publish raw objectives with normalized scores because denominators such as maximum length, total length, and alignment length are not interchangeable.

Mode	Objective	Operations	Output	Complexity	Best use
LCS diff	Maximize retained order	Insert, delete	Common subsequence and hunks	$O(nm)$ time	Human-readable diffs
Levenshtein	Minimize unit or weighted edits	Insert, delete, substitute	Distance and script	$O(nm)$ time	Typographical comparison
Damerau-Levenshtein	Include transposition	Four edit types	Distance and script	Usually $O(nm)$	Spelling errors
Needleman-Wunsch	Maximize global score	Match, mismatch, gap	End-to-end alignment	$O(nm)$	Globally related sequences
Smith-Waterman	Maximize local score	Match, mismatch, gap, restart	Best local region	$O(nm)$	Shared regions in unrelated context
Gotoh	Apply affine gap costs	Match, mismatch, gap open/extend	Global or local alignment	$O(nm)$ with three states	Long contiguous gaps
Hirschberg	Reconstruct with divide and conquer	Objective-dependent	Linear-space witness	$O(nm)$ time, linear space	Large traceback problems

Approximate Dictionary Search

A BK-tree indexes terms under an integer metric. At a node distance $d$ from query $q$ and threshold $k$, the triangle inequality permits only child edges in $[d-k,d+k]$. Exact distance verifies candidates. For small fixed thresholds, intersecting a Levenshtein automaton with a trie shares dictionary prefixes; q-gram indexes offer another filter for large dictionaries.

Approximate lookup pipeline

flowchart TD
    A["Raw query"] --> B["Normalize and tokenize"]
    B --> C{"Candidate index"}
    C --> D["BK-tree range traversal"]
    C --> E["Trie × Levenshtein automaton"]
    C --> F["q-gram filter"]
    D --> G["Candidate terms"]
    E --> G
    F --> G
    G --> H["Exact distance and traceback"]
    H --> I{"Within threshold?"}
    I -- "No" --> J["Discard"]
    I -- "Yes" --> K["Stable rank and return witness"]

Evaluation and UX

Verify optimal costs against a trusted table and confirm that applying every reconstructed script yields the target. Test identity, symmetry for symmetric costs, metric properties where applicable, Unicode normalization, deterministic ties, empty inputs, and agreement between full and rolling distance computations. For large files, trim common ends, anchor unique lines, refine changed blocks at finer granularity, and use Hirschberg or justified banding.

Design Exercise

Which Diff Is Better?

Before: prepare(), validate(), save(), notify(). After: validate(), prepare(), save(), notify().

Two optimal cost-two LCS scripts exist. Diff A deletes the old prepare() and inserts it after validate(); Diff B inserts validate() first and deletes its old occurrence. Both reconstruct the same target, but one reads as moving prepare down and the other as moving validate up.

Choose using explicit UX criteria—few hunks, preservation of unique anchors, nearby stable context, and deterministic ties—not edit cost alone. Repeating the exercise at character granularity changes the optimization problem and may obscure the line-level reorder.

Cookie Consent