| Safe Haskell | Safe |
|---|---|
| Language | Haskell98 |
Options.Applicative.Help.Levenshtein
Synopsis
- editDistance :: Eq a => [a] -> [a] -> Int
Documentation
editDistance :: Eq a => [a] -> [a] -> Int Source #
Calculate the Damerau-Levenshtein edit distance between two lists (strings).
This is modified from https://wiki.haskell.org/Edit_distance and is originally from Lloyd Allison's paper "Lazy Dynamic-Programming can be Eager"
It's been changed though from Levenshtein to Damerau-Levenshtein, which treats transposition of adjacent characters as one change instead of two.
Complexity O(|a|*(1 + editDistance a b))