Levenshtein / Edit Distance Calculator

Inspectable records

Ledger state

The current ledger marks this instrument verified clean within the source-bound verification corpus.

Area

Computing & Information

Tranche

tranche-5

Evidence ID

t5-015

Ledger rows

1

No ledger note is attached.

Review findings

The core recurrence is correct for standard unit-cost Levenshtein distance, but the specification is incomplete. NEEDS_REVIEW is required until the boundary conditions, cost function, text-unit definition, normalization policy, and alignment-selection behavior are explicitly fixed.

Formula and scope findings

• The recurrence is the standard Levenshtein recurrence, but the required boundary conditions are missing: d[0][j]=j and d[i][0]=i, with d[0][0]=0.
• The cost term is undefined; standard Levenshtein distance requires cost=0 when the compared units are equal and cost=1 otherwise.
• The string-unit model is unspecified: characters could mean Unicode code points, UTF-16 code units, grapheme clusters, or another tokenization.
• An aligned diff is not necessarily unique when multiple minimum-cost alignments exist; no tie-breaking or canonical-alignment rule is specified.

Unit assumptions

• The test vectors assume strings are segmented into Unicode code points, not UTF-16 code units or grapheme clusters.
• Insertion, deletion, and substitution each have unit cost 1; matching units have cost 0.
• A gap is represented by '-' in the aligned diff display.
• No Unicode normalization is applied unless explicitly specified; composed and decomposed forms may therefore produce different distances.

Boundary hardening

BREAK_CLAIMED · SELF_FLAGGED

The extreme-length vector exposes an unstated scalability hazard: a million-character pair requires 1000002000001 DP cells, so an implementation without input-size or memory limits can exhaust resources instead of returning a usable result.

Errata and corrections

No applied erratum is attached to this unique-name record.

Inspectable example

4 review vectors are recorded. One source-bound sample is shown below.

{
  "inputs": {
    "string_a": "kitten",
    "string_b": "sitting"
  },
  "expected_outputs": {
    "edit_distance": 3,
    "aligned_diff": "kitten-\nsitting"
  },
  "working": "Use the alignment kitten- / sitting. Positions are: k→s substitution = 1; i→i match = 0; t→t match = 0; t→t match = 0; e→i substitution = 1; n→n match = 0; -→g insertion = 1. Total = 1+0+0+0+1+0+1 = 3."
}

Related workflows

No source-defined multi-instrument workflow membership is recorded.

Sources and evidence

These pointers bind the page to evidence. They do not grant authority or collapse verification into deployment.

• VERIFIED_LEDGER.json · VERIFIED_CLEAN
• evidence-tranche5/tranche5-results.json
• BOUNDARY_HAZARD_CATALOG.json