Edit distance

Short description: Minimum-cost transformation between strings or symbol sequences

Edit distance is a family of measures for the difference between two finite sequences. An edit-distance model specifies a collection of permitted changes to a sequence, assigns a cost to each change, and finds the minimum total cost of transforming one sequence into another. In computer science, the sequences are often strings, but the same framework can apply to tokens, biological sequences and other ordered symbolic data.

Levenshtein distance is the best-known special case: it counts single-symbol insertions, deletions and substitutions, each with unit cost. The term edit distance is sometimes used as shorthand for Levenshtein distance, but is more general. Different allowed operations, edit costs, sequence representations and alignment constraints can produce different answers for the same pair of strings. Consequently, an edit-distance value is meaningful only in the context of its specified edit model.

Edit distances are used in spelling correction, approximate string matching, optical character recognition, record linkage, version comparison, bioinformatics and sequence analysis. An edit distance measures changes to a chosen representation; it does not by itself determine whether two names identify the same entity, two words have the same meaning, or two sequences are biologically related.

Definition and edit operations

Let $\mathrm{\Sigma }$ be an alphabet and let $x,y\in {\mathrm{\Sigma }}^{*}$ be finite strings. An edit script is a finite sequence of permitted operations that transforms $x$ into $y$. For an operation set ${𝒪}$ and a non-negative cost function $c$, the corresponding edit distance is

$d_{{𝒪},c}(x,y)=\underset{P:x\Rightarrow y}{\min }\sum _{o\in P}c(o),$

where the minimum is taken over all valid edit scripts $P$. The value can be treated as infinite if the operation set cannot transform one sequence into the other. With zero-cost operations, unequal sequences may have distance zero; with asymmetric costs, the distance from $x$ to $y$ may differ from the reverse distance.

Common primitive operations include:

• Insertion: add one symbol, for example ab → acb.
• Deletion: remove one symbol, for example acb → ab.
• Substitution: replace one symbol, for example cat → cut.
• Adjacent transposition: swap neighboring symbols, for example form → from.
• Block or application-specific edits: some models include merges, splits, token operations, or other transformations. Such models must define the relevant operation precisely.

A substitution need not have the same cost as an insertion or deletion. In sequence alignment, for example, different substitution scores and gap penalties reflect a domain-specific model. The classical Levenshtein model instead gives each insertion, deletion and substitution cost 1; matching equal symbols costs 0.

Major types of edit distance

Model	Permitted operations or comparison rule	Important distinction
Levenshtein distance	Single-symbol insertion, deletion and substitution	Each operation normally costs 1; measures the minimum number of these edits.
Insertion–deletion (indel or LCS) distance	Insertion and deletion only	A substitution is represented by a deletion followed by an insertion.
Hamming distance	Substitution at aligned positions only	Defined as a finite distance only for equal-length strings (or with an explicit convention for unequal lengths).
Damerau–Levenshtein distance	Insertion, deletion, substitution and adjacent transposition	In its unrestricted form, successive edits may involve the same characters; the unit-cost form is a metric.
Optimal string alignment (OSA) distance	Restricted insertion, deletion, substitution and adjacent transposition	A common short recurrence computes this restricted variant, not unrestricted Damerau–Levenshtein distance; OSA is not a metric.
Weighted edit distance	A specified set of operations with non-uniform costs	Costs may depend on the edited symbols or the application; the resulting function need not be symmetric.
Sequence alignment with gap penalties	Substitutions and insertions/deletions with specified gap costs	Linear, affine or other gap penalties alter the optimization objective; local alignment is not simply whole-string edit distance.

Jaro and Jaro–Winkler are related string-similarity measures, but they are not edit distances obtained merely by allowing transposition operations. Jaro similarity combines a count of matching symbols, a matching window and an ordering penalty; Jaro–Winkler additionally rewards a common prefix. Converting such a similarity score to $1-\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{y}$ does not generally produce a mathematical metric. These methods should be classified separately from minimum-cost edit-script models; see Jaro–Winkler distance.

Relation to the longest common subsequence

For strings $x$ and $y$ of lengths $m$ and $n$, let $\mathrm{LCS}(x,y)$ denote the length of a longest common subsequence. The unit-cost insertion–deletion distance is

$d_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{l}}(x,y)=m+n-2\mathrm{LCS}(x,y).$

This follows because symbols belonging to a common subsequence can be retained, while the remaining symbols must be deleted or inserted. Consequently,

$d_{\mathrm{L}\mathrm{e}\mathrm{v}}(x,y)\le d_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{l}}(x,y),$

since the Levenshtein model can substitute one symbol at cost 1 instead of deleting and inserting at total cost 2.

Restricted and unrestricted transpositions

The distinction between OSA distance and unrestricted Damerau–Levenshtein distance matters whenever edits interact. For example:

CA → AC → ABC

requires one adjacent transposition followed by one insertion, for a total unrestricted Damerau–Levenshtein cost of 2. The usual restricted OSA recurrence instead returns 3 for CA and ABC. It does not account for this combination of operations in the same way. In particular, OSA violates the triangle inequality: its distances between CA, AC and ABC are respectively 1, 1 and 3. A simple additional term referring to two earlier rows and columns therefore does not by itself implement unrestricted Damerau–Levenshtein distance.

Examples

The unit-cost Levenshtein distance from kitten to sitting is 3:

1. kitten → sitten (substitute s for k).
2. sitten → sittin (substitute i for e).
3. sittin → sitting (insert g).

With substitutions forbidden, the same strings have insertion–deletion distance 5: a longest common subsequence has length 4, so $6+7-2(4)=5$.

Input strings	Unit-cost Levenshtein distance	Explanation
kitten, sitting	3	Two substitutions and an insertion.
form, from	2	Standard Levenshtein requires two edits; a Damerau-style adjacent transposition costs 1.
abc, abc	0	Identical sequences.
abc, empty string	3	Three deletions.
CA, ABC	3	Unrestricted Damerau–Levenshtein distance is 2, but standard Levenshtein remains 3.

Mathematical properties

For unit-cost Levenshtein distance, the following properties hold:

• Non-negativity and identity: $d(x,y)\ge 0$, with equality exactly when $x=y$.
• Symmetry: $d(x,y)=d(y,x)$.
• Triangle inequality: $d(x,z)\le d(x,y)+d(y,z)$.
• Length lower bound: $||x|-|y||\le d(x,y)$.
• Elementary upper bound: $d(x,y)\le \max (|x|,|y|)$, by substituting symbols in corresponding positions and inserting or deleting the remainder.
• Hamming bound: for strings of equal length, $d_{\mathrm{L}\mathrm{e}\mathrm{v}}(x,y)\le d_{\mathrm{H}\mathrm{a}\mathrm{m}}(x,y)$.

Non-negativity, symmetry, identity and the triangle inequality make classical Levenshtein distance a metric. These conclusions cannot automatically be transferred to every function called an edit distance. For example, unequal insertion and deletion costs may create an asymmetric directed distance. A zero-cost transformation between unequal strings can violate identity of indiscernibles. OSA distance fails the triangle inequality, as shown above.

For a fully general edit-script model, positive costs and reversibility with equal costs are sufficient to yield a metric when all strings can be connected using permitted edits. If costs are zero for edits between distinct strings, or if some edits cannot be reversed, additional analysis is needed.

Normalized distances and similarity scores

A frequently used application-specific score for classical unit-cost Levenshtein distance is

$S(x,y)=1-\frac{d_{\mathrm{L}\mathrm{e}\mathrm{v}}(x,y)}{\max (|x|,|y|)},$

when at least one string is nonempty; $S(\epsilon ,\epsilon )$ is usually defined as 1. The formula returns a similarity in the interval from 0 to 1, but it does not measure semantic identity or provide a calibrated probability that two records refer to the same entity. Dividing a metric by a denominator depending on both input strings also does not automatically preserve all metric axioms. The term normalized edit distance additionally denotes other optimization models in which a normalized edit-path objective is minimized directly; these should not be conflated with the simple score above.

Computing edit distance

Dynamic programming: the Wagner–Fischer recurrence

Main article: Wagner–Fischer algorithm

For sequences $x=x_1\dots x_m$ and $y=y_1\dots y_n$, let $D[i,j]$ be the unit-cost Levenshtein distance between the first $i$ symbols of $x$ and the first $j$ symbols of $y$. Define the initial values as

$D[i,0]=i,D[0,j]=j.$

For $i,j\ge 1$, the recurrence is

$\begin{array}{rl}D[i,j]=\min \{& D[i-1,j]+1,\\ & D[i,j-1]+1,\\ & D[i-1,j-1]+[x_i\ne y_j]\},\end{array}$

where $[x_i\ne y_j]$ is 0 when the two symbols are equal and 1 otherwise. The three cases represent deletion, insertion and substitution (or an unchanged matching symbol). The answer is $D[m,n]$. This algorithm is usually associated with Wagner and Fischer (1974), although closely related recurrences were developed by several researchers.

For non-negative symbol-dependent insertion, deletion and substitution costs, the recurrence can be generalized by replacing each unit increment with the corresponding specified cost, and initializing the first row and column with cumulative insertion or deletion costs. Context-sensitive penalties, block edits or unrestricted transpositions may require additional state or a different recurrence.

Time, memory and reconstruction

Filling the entire dynamic-programming matrix takes $\mathrm{\Theta }(mn)$ time and $\mathrm{\Theta }(mn)$ space. When only the final distance is needed, each row depends on the preceding row and the current row, reducing working memory to $O(\min (m,n))$ by placing the shorter sequence on the stored dimension.

The full matrix permits backtracking to reconstruct a minimum-cost edit script or alignment. A two-row implementation discards most of the information required for ordinary backtracking, but divide-and-conquer techniques based on Hirschberg's algorithm can recover an optimal alignment using linear additional space, with a suitable edit-distance formulation.

An implementation intended for production use should specify its behavior for empty strings, long inputs, operation weights, text encoding and normalization, distance cutoffs, and whether it must return only a number or also an edit script.

Threshold-limited and banded algorithms

For threshold search, the task is often to decide whether $d(x,y)\le k$, rather than compute the full distance. The length lower bound immediately rejects a pair if $||x|-|y||>k$. When the threshold is small, computing only cells within a suitable band around the dynamic-programming diagonal can avoid processing the full matrix. Ukkonen studied algorithms for approximate matching and small-error searches based on such restrictions.

Banding must preserve all paths that could satisfy the specified threshold. Using an arbitrary narrow band without such a guarantee can create false negatives. For large $k$, the advantage over full dynamic programming diminishes.

Bit-parallel algorithms

Bit-parallel methods encode multiple dynamic-programming states in machine words, allowing a processor to update many logical positions with bit operations. Gene Myers described a bit-vector algorithm for approximate string matching that improved performance in important short-pattern settings. The benefit depends on pattern length, word size, alphabet representation and the precise matching task. Myers's 1999 bit-vector algorithm should not be confused with other algorithms bearing the Myers name.

Theoretical complexity

The classical dynamic-programming bound is not a proof that all exact edit-distance algorithms require quadratic time. Masek and Paterson presented a subquadratic-by-logarithmic-factor algorithm under restrictions on the alphabet and costs.

For general exact unit-cost edit distance on equal-length strings, Backurs and Indyk established a conditional fine-grained lower bound: an $O(n^{2-\delta })$-time algorithm for any fixed $\delta >0$ would refute the Strong Exponential Time Hypothesis (SETH). This does not rule out logarithmic improvements, specialized input classes, faster threshold-based algorithms or approximation algorithms.

Unicode, normalization and sequence units

Edit distance operates on a sequence of elements. It does not itself prescribe whether an element is a byte, an encoded code unit, a Unicode code point, an extended grapheme cluster, a token or a domain-specific symbol. Two correct implementations of the same recurrence can therefore give different answers if they compare different representations.

In Unicode, the character é can be represented as the single code point U+00E9 or as the sequence U+0065 followed by U+0301 (combining acute accent). Without preprocessing:

• Code-point Levenshtein distance between these two representations is 2.
• Grapheme-cluster Levenshtein distance can be 1 if each cluster is compared as a distinct unnormalized sequence.
• Code-point Levenshtein distance after canonical NFC normalization is 0, because the normalized representations agree.

Unicode normalization and Unicode text segmentation are separate choices. NFC or NFD handles canonical equivalence; NFKC or NFKD also applies compatibility mappings that may intentionally collapse distinctions between some symbols. Extended grapheme clusters approximate units a user perceives as characters but do not automatically make differently encoded sequences equal under a raw equality comparison.

For multilingual applications, normalization and segmentation policies should be documented and applied consistently to both the indexed data and incoming queries. This is especially important when comparing combining marks, emoji sequences, decorated Unicode symbols or text written in different scripts. No single representation is optimal for every task: a phonetic application may compare phonemes, a search engine may compare tokens, and a spelling corrector may compare Unicode character sequences.

Approximate searching, indexing and filtering

Computing the distance between one pair of strings is different from finding every string within a threshold in a large collection. For a query $q$, a collection $S$ and a threshold $k$, an exact similarity search seeks

$\{s\in S:d(q,s)\le k\}.$

A brute-force approach computes the distance to every candidate. Large-scale systems often combine an index or candidate generator, inexpensive necessary-condition filters, and a final exact edit-distance verification step.

For classical unit-cost Levenshtein distance, useful safe conditions include length bounds and partition-based arguments. If a pattern is divided into $k+1$ non-overlapping pieces, an alignment using at most $k$ single-symbol edits leaves at least one appropriate piece unaffected. This motivates exact-seed filtering, but insertions and deletions may shift its position in the target; a correct implementation must account for allowed shifts, boundaries and verification. An approach that silently omits valid candidates is no longer an exact search algorithm.

Bidirectional string indices and search schemes are additional techniques used for low-error matching in large biological sequence collections. Their computational objective differs from merely optimizing one pairwise edit-distance calculation. Likewise, an approximate algorithm that estimates the distance is not interchangeable with a lossless threshold search unless its guarantees are explicitly established.

Applications and interpretation

Spelling correction and information retrieval

A word can be compared with dictionary entries to find low-distance correction candidates. A useful spelling system may supplement edit distance with word frequencies, keyboard adjacency, phonetic information and linguistic context. Low edit distance is a candidate-ranking signal rather than proof of the intended word.

Record linkage and entity resolution

Typographical differences in names, addresses or organization labels may be detected with character-level edit distance. Establishing whether records identify the same person or organization additionally requires domain evidence such as location, identifiers and other attributes. Similarity thresholds do not establish real-world identity, and pairwise similarity is not a transitive equivalence relation.

Biological sequence analysis

Unit-cost edit distance provides a simple model of insertions, deletions and substitutions in DNA or protein sequences. Biological alignment commonly uses substitution matrices, affine gap penalties, local or global alignment objectives and other models better suited to the error process or evolutionary assumptions. The score of a biological alignment should not be treated as interchangeable with unit-cost Levenshtein distance without specifying its operations and costs.

OCR, text processing and security

Optical character recognition may produce substitutions, missing symbols and segmentation errors that motivate special merge or split costs. For security-sensitive identifiers, two distinct Unicode sequences can look alike while having a nonzero code-point edit distance. Edit distance can assist in suspicious-name screening but does not replace script-aware confusable detection or other identifier policies.

Language edit distance

In theoretical computer science, language edit distance measures the smallest edit distance from a string to any string in a formal language $L\subseteq {\mathrm{\Sigma }}^{*}$:

$d(x,L)=\underset{y\in L}{\min }d(x,y).$

When $L$ is empty, a conventional extended-distance definition sets the value to infinity. This concept is about membership in formal-language sets and should not be confused with measuring similarity or learning difficulty between human languages.

Aho and Peterson presented a minimum-distance error-correcting parser for context-free languages, with a cubic-time dynamic-programming algorithm in their formulation. Research on language edit distance has also examined improvements using specialized algebraic algorithms and connections to RNA folding.

Historical development

Early work on string errors arose in information theory, spelling correction and sequence alignment. Frederick J. Damerau studied common human spelling errors in 1964. Vladimir I. Levenshtein published a foundational paper on deletion-, insertion- and substitution-related error correction in Russian in 1965; an English translation appeared in 1966. Wagner and Fischer subsequently described the string-to-string correction problem and a dynamic-programming solution in 1974. These contributions belong to related but distinct historical lines; naming the modern distance does not imply that all associated algorithms appeared in a single publication.

See also

• Levenshtein distance
• Damerau–Levenshtein distance
• Wagner–Fischer algorithm
• Longest common subsequence
• Approximate string matching
• String metric
• Levenshtein automaton
• Sequence alignment
• Graph edit distance

External links

• Unicode Standard Annex #15 – Unicode normalization forms.
• Unicode Standard Annex #29 – Unicode text segmentation.
• Edit Distance: Definition, Algorithms, Complexity and Applications – extended technical overview of edit models, algorithms and sequence representations (contributor-associated resource).