> For the complete documentation index, see [llms.txt](https://deemolover.gitbook.io/log-os/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://deemolover.gitbook.io/log-os/theory/language-processing/chapter-2-re-text-norm-edit-dist./2.5-minimum-edit-distance.md).

# 2.5 Minimum Edit Distance

Edit distance measures similarity between strings.

**DEF** given a set of string editing operations, **minimum edit distance** between two strings is defined as the minimum number of operations needed to transform one string into another.

* Common operations include insertion(insert a character), deletion(delete a character), substitution(replace a character with another).
* **DEF** Minimum edit distance can be represented by an **alignment**. This is an alignment between `INTENTION` and `EXECUTION`:

  ```
  I N T E * N T I O N
  | | | | | | | | | |
  * E X E C U T I O N
  ```

  * Every character is mapped either to a character in the other string, or a null character.
  * Mappings may not cross.
* Operations can be assigned costs. **Levenshtein distance** ( ref: \[1] ) assumes every operation has a cost of 1 except the substitution of a letter for itself(E-E in the case above), which has a zero cost.
* **ALGO** Minimum edit distance problem can be solved through dynamic programming. DP equation:
  * ```
    D[i,j] = min(
        D[i-1,j]+delete_cost(source[i]),
        D[i,j-1]+insert_cost(target[j]),
        D[i-1,j-1]+substitute_cost(source[i],target[j])
    )
    ```
  * The algorithm gives minimum cost of transferring string `source` into string `target`. `D[i,j]` represents the optimal cost of transferring an `i`-character long prefix of `source` into a `j`-character-long prefix of `target`.
  * `substitute_cost` is zero when `source[i] == target[j]`.
* **Viterbi** algorithm is a probabilistic extension of minimum edit distance.

## Reference

\[1] Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 10(8), 707–710. Original in Doklady Akademii Nauk SSSR 163(4): 845–848 (1965).