performance - Damerau-Levenshtein 距离的高效实现

Question

我正在尝试实现真正高效的 Clojure 函数来计算 Damerau-Levenshtein distance 。我决定使用this algorithm (所附源代码应为 C++)用于计算 Levenshtein 距离并添加一些行以使其适用于 DLD。

这是我在 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 代码(函数式风格？)。我真的很感激任何建议，我认为它对许多 future 的读者也可能非常有用。

附注我找到了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)))

Answer 1

我最近不得不在 clojure 中编写一个高效的 levenshtein 距离函数来计算真实文本和 ocr 引擎结果之间的编辑。递归实现的性能不足以快速计算两个整页之间的编辑距离，因此我的实现使用动态编程。它没有使用 java 2d 数组，而是使用 core.matrix 来处理矩阵内容。为damerau-levenshtein 添加转置内容应该不难。

(defn lev [str1 str2]
  (let [mat (new-matrix :ndarray (inc (count str1)) (inc (count str2)))
        len1 (count str1) len2 (count str2)]
   (mset! mat 0 0 0)
   (dotimes [i lein1]
     (mset! mat (inc i) 0 (inc i)))
   (dotimes [j len2]
     (mset! mat 0 (inc j) (inc j)))
   (dotimes [dj len2]
     (dotimes [di len1]
       (let [j (inc dj) i (inc di)]
         (mset! mat i j
              (cond
                (= (.charAt ^String str1 di) (.charAt ^String str2 dj))
                (mget mat di dj)
                :else
                (min (inc (mget mat di j)) (inc (mget mat i dj))
                    (inc (mget mat di dj))))))))
   (mget mat len1 len2))))

希望这有帮助