Skip to content

Damerau-Levenshtein distance

Type of Edit distance which takes into account only insert, delete, substitute and transpose operations. Extension of Levenshtein distance.

Algorithms

Algorithm	Time complexity	Space complexity
Extension of Wagner-Fischer¹	$O(mn)$	$O(mn)$
Space-improved version of Wagner-Fischer¹	$O(mn)$	$O(m)$

Metric

Bard prooved that Damerau-Levenshtein is true metric. See Bard, Gregory. (2006). Spelling-Error Tolerant, Order-Independent Pass-Phrases via the Damerau-Levenshtein String-Edit Distance Metric. IACR Cryptology ePrint Archive. 2006. 364.

string2string: A Modern Python Library for String-to-String Algorithms ↩ ↩²