On this page
Approximate edit comparison for long documents
Edition: 8 October 2026. Initial decision: Conditional engineering. The product interpretation and pricing are hypotheses; independent proof and buyer validation remain open.
Research finding
Family 121 claims a randomized 1+epsilon approximation to unit-cost edit distance in near-linear expected time at fixed accuracy. It estimates distance; the selected statement does not produce an alignment. Family 099 warns that embedding edit distance into L1 necessarily incurs growing worst-case distortion.
Problem and buyer
Document archives and duplicated-text pipelines can spend substantial work comparing long candidate pairs. Exact unit-cost edit distance can be an expensive final filter even after candidate retrieval.
What the finding could enable
An approximate comparison service could triage long pairs and defer expensive exact work. It could support archive deduplication or change magnitude summaries while retaining a separate exact alignment step for user-facing diffs.
Technical and commercial limits
The guarantee is asymptotic, randomized and tied to fixed epsilon and explicit integer strings. It does not establish semantic equivalence, a diff, arbitrary weighted edits, or cheap approximate-nearest-neighbor indexing. Tokenization changes the problem.
Minimal architecture
Canonical tokenization -> exact equality test -> approximate distance backend -> confidence-aware threshold policy -> exact fallback. Persist preprocessing and confidence metadata to make comparisons reproducible.
Existing alternatives and differentiation
RapidFuzz already supplies optimized Levenshtein routines. Compare directly on the buyer's actual string lengths and edit regimes; a theoretical exponent is insufficient differentiation.
Monetization hypothesis
Hypothesis: usage pricing only after measurable compute savings, or AUD 2,000-8,000 for a document-pipeline integration. Short-string matching is likely too well served for an attractive new product.
Validation experiment
Measure runtime and error across identical, near-identical, repetitive and unrelated strings. Use exact distances as ground truth wherever feasible and test threshold false positives and false negatives independently.
Conditions to reject or defer
Reject if the crossover exceeds realistic document sizes, approximation causes unacceptable threshold mistakes, or buyers need alignments that dominate total cost.
Next concrete action
Extract finite numerical routines and parameter schedules, then estimate their overhead before writing a full backend.
Source evidence
Repository sources are pinned to revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. Selected scope notes and manuscript statements have been reviewed to the extent described above; these links do not represent successful kernel checks.
Family 121
Subject: Almost-linear approximation of edit distance.
Family 099
Subject: The sharp exponential scale of edit-distance distortion.
- Edit Distance in l1: Matching Bounds up to Constants in the Exponent
- Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance
- Tree Constructions for the l1 Distortion of Binary Edit Distance
- Formal scope notes
Current alternative sources
Primary documentation reviewed on 8 October 2026. Product availability demonstrates alternatives, not demand or willingness to pay for this proposal.