Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Calculate levenshtein distance between two sequences.
(defn levenshtein
"Calculate levenshtein distance between two sequences."
{:test #(are [d s1 s2] (= d (levenshtein s1 s2))
0 "soup" "soup"
3 "kitten" "sitting"
3 "sitting" "kitten"
0 [1 2 3] [1 2 3]
1 [1 2 3] [1 2 3 4])}
[s1 s2]
(((reduce (fn [d [i j]]
(assoc d (inc j)
(assoc (d (inc j)) (inc i)
(list (+ (if (= (nth s1 i)
(nth s2 j)) 0 1) ((d j) i))
(inc ((d (inc j)) i))
(inc ((d j) (inc i)))))))))
(merge {0 (let [s (range (inc (count s1)))]
(zipmap s s))}
(let [s (range 1 (inc (count s2)))]
(zipmap s (map (fn [i] {0 i}) s))))
(for [i (range 0 (count s1)) j (range 0 (count s2))] [i j]))
(count s2))
(count s1)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment