Function: apheleia--edit-distance-table

apheleia--edit-distance-table is a natively compiled function defined in apheleia-dp.el.

Signature

(apheleia--edit-distance-table S1 S2)

Documentation

Align strings S1 and S2 for minimum edit distance.

Return the dynamic programming table as a hash table which maps cons of integers (I1 . I2) to the edit distance between the first I1 characters of S1 and the first I2 characters of S2.

Source Code

;; Defined in /nix/store/lwcwryzabcmvjcwwzzs65jrwf7p7d7cs-emacs-packages-deps/share/emacs/site-lisp/elpa/apheleia-20260915.1628/apheleia-dp.el
(cl-defun apheleia--edit-distance-table (s1 s2)
  "Align strings S1 and S2 for minimum edit distance.
Return the dynamic programming table as a hash table which maps
cons of integers (I1 . I2) to the edit distance between the first
I1 characters of S1 and the first I2 characters of S2."
  (let ((table (make-hash-table :test #'equal)))
    (dotimes (i1 (1+ (length s1)))
      (puthash (cons i1 0) i1 table))
    (dotimes (i2 (1+ (length s2)))
      (puthash (cons 0 i2) i2 table))
    (dotimes (i1 (length s1))
      ;; Iterate from 1 to length+1.
      (cl-incf i1)
      (dotimes (i2 (length s2))
        (cl-incf i2)
        (let ((ins (1+ (gethash (cons i1 (1- i2)) table)))
              (del (1+ (gethash (cons (1- i1) i2) table)))
              (sub (gethash (cons (1- i1) (1- i2)) table)))
          (unless (= (aref s1 (1- i1)) (aref s2 (1- i2)))
            (cl-incf sub))
          (puthash (cons i1 i2) (min ins del sub) table))))
    table))