1.2.3-SNAPSHOT permalink Arrow_down_16x16

damerau-levenshtein-distance

incanter.stats

  • (damerau-levenshtein-distance a b)

0 Examples top

Log in to add / edit an example.

See Also top

Log in to add a see also.

Plus_12x12 Minus_12x12 Source incanter/stats.clj:3232 top

(defn damerau-levenshtein-distance
  [a b]
  (let [m (count a)
        n (count b)
        init (apply deep-merge-with (fn [a b] b)
                    (concat 
                     ;;deletion
                     (for [i (range 0 (+ 1 m))]
                       {i {0 i}})
                     ;;insertion
                     (for [j (range 0 (+ 1 n))]
                       {0 {j j}})))
        table (reduce
               (fn [d [i j]]
                 (deep-merge-with 
                  (fn [a b] b) 
                  d 
                  (let [cost (bool-to-binary (not (= (nth a (- i 1))
                                          (nth b (- j 1)))))
                        x
                          (min 
                           (+ ((d (- i 1)) 
                               j) 1) ;;deletion
                           (+ ((d i) 
                               (- j 1)) 1) ;;insertion
                           (+ ((d (- i 1)) 
                               (- j 1)) cost)) ;;substitution))
                      
                        val (if (and (> i 1)
                               (> j 1)
                               (= (nth a (- i 1))
                                  (nth b (- j 2)))
                               (= (nth a (- i 2))
                                  (nth b (- j 1))))
                        (min x (+ ((d (- i 2)) 
                                   (- j 2)) ;;transposition
                                  cost))
                        x)]
                    {i {j val}})))
               init
               (for [j (range 1 (+ 1 n))
                     i (range 1 (+ 1 m))] [i j]))]

    ((table m) n)))
Vars in incanter.stats/damerau-levenshtein-distance: defn let
Used in 0 other vars

Comments top

No comments for damerau-levenshtein-distance. Log in to add a comment.