---
title: "algorithm-levenshtein-rust-approximant — Mova code model"
description: "Mova code model of algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs.groupant/>

# algorithm-levenshtein-rust-approximant

The groupant beside algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial descriptive instance
- **source:** [`algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs)
- **source SHA-256:** `b8839fded6e08c8b…`
- **part of:** [algorithm-levenshtein](https://md.groupants.elamur.ai/free/en/mova/algorithms/src/levenshtein/mod.rs.groupant/)
- **repository folder:** [`algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/levenshtein/mod.rs.groupant/rust_approximant.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | `model.md` |
| **tests** | existing checks referenced | [tests](#tests) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial relational specification | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |

## Model text


Migration: consolidated into model.md, 2026-11-04, operator decision; fresh hash-bound references to the former files were rebound to the sections below.

### descriptant

#### Executable byte Levenshtein approximant

Modeling epoch 2026-10-30. This opt-in companion returns a scalar distance
estimate, an enclosing interval and a fallback flag. Production stays unchanged.
All four ErrorBudget caps (1%, 2%, 5%, 10%) use one deterministic certificate.
The method is an original composition and derivation of elementary edit-distance
bounds, not an attribution to a new published algorithm.

Before measurement: a scan should beat quadratic DP for long strings whose
histogram lower bound and aligned upper bound agree closely. Equal histograms
with many shifted positions should fall back and can regress due to scan cost.
A large identical context should shrink the DP middle. This is a prediction,
not a measured throughput claim. The shared runner owns comparative timings.

Only byte unit-cost insertion/deletion/substitution is modeled. Unicode scalar
or grapheme distance, weighted edits, edit scripts and downstream task accuracy
are unsupported. Successful allocations are assumed on fallback; resource
failure is not covered by the scalar numerical guarantee. The certificate
needs two fixed 256-entry usize histograms and no heap allocation.

### approximant

#### Forward approximant and mathematical combiner

Observation: scalar byte Levenshtein distance D, exact zero when D=0.
Trim common affixes, form histogram lower L and aligned-edit upper U, and
return U only after the safe integer certificate (U-L)*100<=p*L; otherwise
return production D on the trimmed middle. models.md derives each bound and
the trimming equality, specifies ordered behavior complement and reverse
reconstruction, and explains composition and arithmetic invariants.

Combiner premises are source-bound: lawful byte equality, p in {1,2,5,10},
finite valid slices, and successful fallback allocation. Composition preserves
L<=D<=U and output overestimate at most p percent. A successful exact fallback
collapses the interval. Parent consumers must separately analyze their own
observation metric; this scalar theorem is not a bound for branching or tasks.

Retained epoch observation, 2026-10-30: histogram collisions can make L zero
even for large nonzero D. Exact fallback is therefore essential. The n=100
nonexact fixture changes dispatch between 2% and 5%, whereas n=300 certifies
at every cap. This illustrates that budget is a ceiling, not target error.
Prospective costs and unsupported observations are in descriptant.md.

### models

## Mathematical models

### behavior_complement

Universe: pairs of finite byte slices, a supported budget p and an Estimate
on successful completion. Write D for exact unit-cost edit distance. Exclude
distance<D, lower_bound>D, upper_bound<D, lower_bound>distance,
distance>upper_bound and distance-D>p*D/100; when D=0 exclude distance!=0.
Also exclude a true fallback flag on an accepted certificate, and a false flag
on a rejected certificate. For fallback exclude any nondegenerate interval.
These are model relations, not merely a list of negative tests.

### reverse_reconstruction

Given (v,l,u,false), compatible inputs are exactly pairs whose trimmed aligned
upper bound is u=v, symmetric histogram bound is l and certificate passes.
Given (v,v,v,true), compatible inputs have exact distance v and rejected
cheap bounds. Byte renaming and shared prefix/suffix insertion produce many
compatible antecedents. Enumerating bounded byte pairs and retaining these
relations gives finite preimages; no unique or unbounded reconstruction is
claimed. Successful allocation is an additional environmental premise.

### forward and trimming proof

For common initial byte c, first-edit recurrence gives
D(cx,cy)=min(D(x,y),1+D(x,cy),1+D(cx,y)).
By triangle inequality D(x,y)<=D(x,cy)+1 and <=D(cx,y)+1.
Thus matching initial bytes can be removed without changing distance.
Reverse both strings: reversing an edit sequence preserves its cost, so
D(reverse(x),reverse(y))=D(x,y), and the same argument removes a common suffix.
Repeatedly remove a maximal common prefix, then suffix of the remaining
slices. These segments never overlap, including when one slice becomes empty.

Let h_a,h_b be byte histograms of the trimmed middle; let
A=sum_c max(h_a(c)-h_b(c),0), B=sum_c max(h_b(c)-h_a(c),0).
Each unit edit can lower A by at most one, and likewise B; both must reach
zero at the target. Hence D>=max(A,B,abs(len(a)-len(b)))=L.
Using both directions makes the bound and returned interval symmetric.
The length-gap bound follows because one edit changes length by at most one.
Align the first min(n,m) positions, substitute each mismatch and insert/delete
the remaining length gap. This constructs an edit sequence of cost
U=aligned_mismatches+abs(n-m), proving D<=U.

Accept iff U-L<=floor(L*p/100). For L>0,
(U-D)/D <= (U-L)/L <= p/100. For L=0 this accepts only U=0, so
the true zero has exact output. Otherwise call the real production distance
on the trimmed middle and return its exact value as both interval endpoints.
The elementary derivation here is the mathematical source; no paper is
claimed for this particular composition.

### invariant, arithmetic and combiner

Histograms count input bytes exactly. Directional excess sums are bounded by
their own slice length. U<=max(n,m), so mismatch plus length gap cannot overflow.
The certificate evaluates floor(L*p/100) as
(L/100)*p+((L%100)*p)/100. Since p<=10, neither product nor sum overflows
usize. Subtraction is performed only after L<=U. No floats or larger caps.
The combiner joins the trimming equality, lower/upper proofs and integer
predicate, then dispatches to the certificate or exact production fallback.
Tests check actual wiring as well as individual premises.

### cost and scope

Accepted path O(n+m+256) time, O(256) stack storage. Fallback adds
O(n'*m'+1) time and O(min(n',m')+1) row storage for trimmed lengths n',m'.
Repeated/equal histograms may yield a weak bound. Small inputs can regress.
Classification: scalar_relative / interval_certificate / per_input_certificate.
Bound kind analytical with a scoped derivation; finite tests cannot establish
a universal theorem or a composition-wide or end-to-end accuracy claim.

### tests

#### Evidence and reproducible checks

2026-10-30: four embedded tests passed in a standalone Rust test compilation
linking the real mova-approx and mova-algorithms libraries. The shared runner
can compile the same source as a module without copying production code.

The independent full-matrix oracle checks all 127 binary strings of length
0 through 6 against all others: 16,129 ordered pairs, every supported budget.
It checks true-distance bounds, relative error, exact-zero behavior, repeated
determinism, symmetry, trimming equality and agreement with production.
Further cases include all 256 bytes, reversed bytes, empties, periodic shifts,
equal histograms, affixes and unequal lengths. Certificate tests cover every
lower bound 0..500 with gaps 0..60 at all caps plus usize::MAX and thresholds.

Nonexact fixture: [0;n]+[2,3,4] versus [1;n]+[3,4,2] has L=n, U=n+3, D=n+2.
At n=100 only P5/P10 certify; at n=300 all four certify a nonexact answer.
The equal-histogram ab/ba pair forces exact fallback at every cap.
Allocation failure and arbitrary resource exhaustion are not exercised.

Compiled mutation evidence and release repetition are recorded below.

Debug: 4/4 tests passed. Optimized: 4/4 passed twice with the same deterministic
assertions and named test results. Formatting check passed.
The compiled source mutation changed only the production dispatch condition
from if certified(lower, upper, budget) to if true. It compiled, then failed
3/4 tests: exhaustive relative error, adversarial relative error and budget
dispatch. The unmodified source was never overwritten. This negative control
demonstrates numerical and route checks can reject a broken certificate gate.
Actual benchmark timings are left to the shared runner; these are correctness
runs and do not support a speedup claim.