1
我试图实现真正高效的Clojure函数来计算Damerau-Levenshtein distance。我决定使用this algorithm（附带的源代码应该是C++）来计算Levenshtein距离并添加一些行以使其适用于DLD。Damerau-Levenshtein距离的高效实现
以下是我在的Common Lisp（我希望它可以帮助）创建：（？函数式）
(defun damerau-levenshtein (x y)
(declare (type string x y)
#.*std-opts*)
(let* ((x-len (length x))
(y-len (length y))
(v0 (apply #'vector (mapa-b #'identity 0 y-len)))
(v1 (make-array (1+ y-len) :element-type 'integer))
(v* (make-array (1+ y-len) :element-type 'integer)))
(do ((i 0 (1+ i)))
((= i x-len) (aref v0 y-len))
(setf (aref v1 0) (1+ i))
(do ((j 0 (1+ j)))
((= j y-len))
(let* ((x-i (char x i))
(y-j (char y j))
(cost (if (char-equal x-i y-j) 0 1)))
(setf (aref v1 (1+ j)) (min (1+ (aref v1 j))
(1+ (aref v0 (1+ j)))
(+ (aref v0 j) cost)))
(when (and (plusp i) (plusp j))
(let ((x-i-1 (char x (1- i)))
(y-j-1 (char y (1- j)))
(val (+ (aref v* (1- j)) cost)))
(when (and (char-equal x-i y-j-1)
(char-equal x-i-1 y-j)
(< val (aref v1 (1+ j))))
(setf (aref v1 (1+ j)) val))))))
(rotatef v* v0 v1))))
现在，我怕我不能把它翻译成真正有效和地道的Clojure代码。我非常感谢任何建议，我认为它对未来的许多读者也可能非常有用。
P.S.我发现this implementation，但如果它是有效的，我怀疑它使用一些过时的contrib功能（deep-merge-with和bool-to-binary）：
(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)))