Skip to content
Newer
Older
100644 19 lines (16 sloc) 639 Bytes
102770c @bitsai add imperative Levenshtein distance
authored
1 (ns levenshtein)
2
ba83731 @bitsai replace imperative Levenshtein with optimized version of pure functio…
authored
3 ;; Laurent Petit's code from below with small optimization
4 ;; https://gist.github.com/828413
5 (defn- new-row [prev-row row-elem t]
17bf70b @bitsai add (vec) so that empty s doesn't blow us up, reformat
authored
6 (reduce (fn [row [d-1 d e]]
7 (conj row (if (= row-elem e)
8 d-1
9 (inc (min (peek row) ;; use only binary min calls
10 (min d d-1))))))
11 [(inc (first prev-row))]
12 (map vector prev-row (next prev-row) t)))
ba83731 @bitsai replace imperative Levenshtein with optimized version of pure functio…
authored
13
14 (defn levenshtein [s t]
17bf70b @bitsai add (vec) so that empty s doesn't blow us up, reformat
authored
15 (peek (reduce (fn [prev-row s-elem]
16 (new-row prev-row s-elem t))
17 (vec (range (inc (count t))))
18 s)))
Something went wrong with that request. Please try again.