A library to calculate a metric indicating the string distance between two strings.
This library was extracted from the Elm implementation of mailcheck http://package.elm-lang.org/packages/rluiten/mailcheck/latest.
The lcs
and lcsLimit
functions are more general and support more than just
Char as list elements.
sift3Distance : String.String -> String.String -> Basics.Float
Calculate sift3 string distance between candidate strings.
sift3Distance "" "abc" == 3.0
sift3Distance "ab" "" == 2.0
sift3Distance "abc" "abc" == 0
sift3Distance "abc" "ab" == 0.5
lcs : List.List a -> List.List a -> List.List a
Longest Common Subsequence
This is a simple implementation and would benefit from memoization if performance is a problem. It does not limit look ahead which can be very costly see lcsLimit for a limited look ahead version.
Warning this gets very slow very quickly with increases in list lengths even 17 character lists can cause things to bog down.
This implementation is based on [[http://rosettacode.org/wiki/Longest_common_subsequence#Haskell](http://rosettacode.org/wiki/Longest_common_subsequence#Haskell)](http://rosettacode.org/wiki/Longest_common_subsequence#Haskell)
lcs ["a", "b", "c"] ["b", "c", "d"] == ["b", "c"]
lcsLimit : Basics.Int
-> List.List a
-> List.List a
-> List.List a
Return function which returns lcs with limited look ahead.
Warning maxLookAhead quickly makes the returned function costly stay below 8 if you want responsiveness.
lcsLimit 5 ["a", "b", "c"] ["b", "c", "d"] == ["b", "c"]