Расстояние Левенштейна 09.03.2013 #

Поскольку скоро придётся сравнивать много всяких последовательностей, запилил я расстояние Левенштейна на Clojure (эксперимента ради).

Возьмём реализацию в лоб:

(defn levenshtein-distance
  [seq1 seq2]
  (cond
   (empty? seq1) (count seq2)
   (empty? seq2) (count seq1)
   :else (min
          (+ (if (= (first seq1) (first seq2)) 0 1)
             (#'levenshtein-distance (rest seq1) (rest seq2)))
          (inc (#'levenshtein-distance (rest seq1) seq2))
          (inc (#'levenshtein-distance seq1 (rest seq2))))))

Всё очень плохо:

(time (levenshtein-distance (shuffle (range 10))
                            (shuffle (range 10))))
"Elapsed time: 2566.345769 msecs"
9

Делаем хорошо следующим образом. В clojure.core есть отличная функция memoize, которая возвращает мемоизированную версию заданной функции.

Замутим мемоизацию для функции levenstein-distance:

(defn memo-levenshtein-distance
  [seq1 seq2]
  (cond
   (empty? seq1) (count seq2)
   (empty? seq2) (count seq1)
   :else (min
          (+ (if (= (first seq1) (first seq2)) 0 1)
             (#'memo-levenshtein-distance (rest seq1)
                                          (rest seq2)))
          (inc (#'memo-levenshtein-distance (rest seq1)
                                            seq2))
          (inc (#'memo-levenshtein-distance seq1
                                            (rest seq2))))))

(def memo-levenshtein-distance (memoize memo-levenshtein-distance))

Проверим насколько стало хорошо:

(let [seq1 (shuffle (range 10))
      seq2 (shuffle (range 10))]
  (map #(time (% seq1 seq2))
       [levenshtein-distance
        memo-levenshtein-distance]))
 ("Elapsed time: 2560.824951 msecs"
 "Elapsed time: 1.265487 msecs"
 9
 9)

Радуемся.