;;; levenshtein.el --- Edit distance between two strings. ;; Copyright (C) 2003, 2005 Aaron S. Hawley, Art Taylor ;; Author: Aaron S. Hawley <ashawley at uvm dot edu>, ;; Art Taylor ;; Keywords: lisp ;; This file is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation; either version 2, or (at your option) ;; any later version. ;; This file is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with GNU Emacs; see the file COPYING. If not, write to ;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, ;; Boston, MA 02111-1307, USA. ;;; Commentary: ;; See: http://wikipedia.org/wiki/Levenshtein_distance ;;; History: ;; Written by Art Taylor on 15 March 2003 in Washington, DC, USA and ;; released under the zlib license. Rewritten by Aaron Hawley on 12 ;; July 2005 in Burlington, VT, USA and released under the GNU GPL. ;; Posted to the EmacsWiki on 12 July 2005. ;;; Code: (defun levenshtein-distance (str1 str2) "Return the edit distance between strings STR1 and STR2." (if (not (stringp str1)) (error "Argument was not a string: %s" str1)) (if (not (stringp str2)) (error "Argument was not a string: %s" str2)) (let* ((make-table ;; Multi-dimensional array object. (function (lambda (columns rows init) (make-vector rows (make-vector columns init))))) (tref ;; Table access method. (function (lambda (table x y) (aref (aref table y) x)))) (tset ;; Table write method. (function (lambda (table x y object) (let ((row (copy-sequence (aref table y)))) (aset row x object) (aset table y row) object)))) ;; End table code. (length-str1 (length str1)) (length-str2 (length str2)) ;; d is a table with lenStr2+1 rows and lenStr2+1 columns (d (funcall make-table (1+ length-str1) (1+ length-str2) 0))) ;; Initialize to zero. ;; i and j are used to iterate over str1 and str2 (let ((i 0) (j 0)) (while (<= i length-str1) ;; for i from 0 to lenStr1 (funcall tset d i 0 i) ;; d[i, 0] := i (setq i (1+ i))) ;; i++ (while (<= j length-str2) ;; for j from 0 to lenStr2 (funcall tset d 0 j j) ;; d[0, j] := j (setq j (1+ j)))) ;; j++ (let ((i 1)) (while (<= i length-str1) ;; for i from 1 to lenStr1 (let ((j 1)) (while (<= j length-str2) ;; for j from 1 to lenStr2 (let* ((cost ;; if str[i] = str[j] then cost:= 0 else cost := 1 (if (equal (aref str1 (1- i)) (aref str2 (1- j))) 0 1)) ;; d[i-1, j] + 1 // deletion (deletion (1+ (funcall tref d (1- i) j))) ;; d[i, j-1] + 1 // insertion (insertion (1+ (funcall tref d i (1- j)))) ;; d[i-j,j-1] + cost // substitution (substitution (+ (funcall tref d (1- i) (1- j)) cost))) (funcall tset d i j ;; d[i,j] := minimum( (min insertion deletion substitution))) (setq j (1+ j)))) ;; j++ (setq i (1+ i)))) ;; i++ ;; return d[lenStr1, lenStr2] (funcall tref d length-str1 length-str2))) (provide 'levenshtein) ;;; levenshtein.el ends here