Editing Edit distance (section)

== Types of edit distance ==

Different types of edit distance allow different sets of string operations. For instance:
{| class="wikitable"
|+ Algorithms and the operations allowed
|-
!Algorithm
!Insertions
!Deletions
!Substitutions
![[Transposition (mathematics)|Transposition]]
|-
|[[Levenshtein distance|Levenshtein Distance]] 
|✓
|✓
|✓
|
|-
|[[longest common subsequence|Longest Common Subsequence]] (LCS) 
|✓
|✓
|
|
|-
|[[Hamming distance|Hamming Distance]]
|
|
|✓
|
|-
|[[Damerau–Levenshtein distance|Damerau–Levenshtein Distance]]
|✓
|✓
|✓
|✓
|-
|[[Jaro distance]] 
|
|
|
|✓
|}
Some edit distances are defined as a parameterizable metric calculated with a specific set of allowed edit operations, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA [[sequence alignment]] algorithms such as the [[Smith–Waterman algorithm]], which make an operation's cost depend on where it is applied.