Source: https://guthlabs.ai/docs/instruments/levenshtein-edit-distance-calculator/

instrument / verified-clean

# Levenshtein / Edit Distance Calculator

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

Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**

## Inspectable records

[01**Overview**Purpose and lifecycle](<https://guthlabs.ai/docs/instruments/levenshtein-edit-distance-calculator/>)[02**Mechanism**Method and assumptions](<https://guthlabs.ai/docs/instruments/levenshtein-edit-distance-calculator/mechanism/>)[03**Implementation**Binding and validation](<https://guthlabs.ai/docs/instruments/levenshtein-edit-distance-calculator/implementation/>)[04**Qualification**Evidence and errata](<https://guthlabs.ai/docs/instruments/levenshtein-edit-distance-calculator/qualification/>)

## 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`