Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 15 minutes

Edit distance is a large class of distance metric of measuring the dissimilarity between two strings by computing a minimum number of operations (from a set of operations) used to convert one string to another string. It can be seen as a way of pairwise string alignment.

Edit distance has several variants such as Levenshtein distance, Spatial Edit Distance, Graph edit distance and many others.

Edit distance has a vast range of applications in computational linguistics, computer science, natural language processing, bioinformatics and many others.

### Computation

Given two strings S1 and S2, edit distance is the minimum cost associated with operations to convert string S1 to S2. Common operations are:

- Insertion: Insert a character at a position (cost: 1)
- Deletion: Delete a character at any position (cost: 1)
- Replace: Replace a character at any position with another character (cost: 1)

Example:

Consider the following strings:

```
S1 = aadbdeg
S2 = aabdec
```

Operations used to convert S1 to S2:

Operation 1: Delete d at position 3

Operation 2: Replace g at position 6 by c

Edit distance = 1 + 1 = 2

### Properties

Edit distance with non-negative cost satisfies the axioms of a metric giving rise to a metric space of strings, when the following conditions are met:

- Every edit operation has positive cost
- For every operation, there is an inverse operation with equal cost

Properties of unit-cost edit distances include:

- LCS distance is bounded above by the sum of lengths of a pair of strings
- LCS distance is an upper bound on Levenshtein distance
- For strings of the same length, Hamming distance is an upper bound on Levenshtein distance

Regardless of cost/weights, the following property holds of all edit distances:

- When a and b share a common prefix, this prefix has no effect on the distance

### Algorithms

Algorithms that can be used to compute edit distance are:

- Wagner Fischer algorithm
- Ukkonen algorithm
- Landau Myers and Schmidt algorithm

### Applications

Computational Biology

- Quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T

Natural Language Processing

- Correction of spelling mistakes
- Correct OCR errors

General computation

- Measure the similarity between two data points