Edit Distance

Edit distance is the minimum number of single-character edit operations (insertion, deletion, substitution) required to transform one string into another; the Levenshtein distance is its most common form.

Purpose

Quantifies the degree of difference between strings, used for fuzzy matching and error correction.

Mechanism

General framework: define the allowed operation set and costs, then use dynamic programming to find the minimum total cost. Levenshtein allows insertion/deletion/substitution (each cost 1); Damerau-Levenshtein additionally allows transposition of adjacent characters; Hamming allows substitution only.

Use cases

Spelling correction
DNA sequence alignment
OCR error correction
Fuzzy deduplication

Examples

Input
```
cat → cut
```
Output
```
1 (substituting a→u)
```
Levenshtein

Common errors

Confusing different edit-distance variants: Make the operation set and costs explicit

Related terms

Levenshtein Distance

The Levenshtein distance is the minimum number of single-character insertions, deletions, and substitutions needed to make two strings identical.

Hamming Distance

The Hamming distance is the number of positions at which corresponding characters differ between two equal-length strings; it only applies to equal-length comparisons.

Fuzzy search is a search technique tolerant of spelling variations, matching approximate results based on edit distance, n-grams, or phonetic algorithms.

Related tools

Hamming Distance

Hamming Distance — pure client-side tool. Privacy-first, no server round-trip.

References