From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Nicolas Richard" Subject: [patch] Incorrect result of org-babel-edit-distance Date: Thu, 06 Dec 2012 16:46:40 +0100 Message-ID: <877govfajj.fsf@yahoo.fr> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Return-path: Received: from eggs.gnu.org ([208.118.235.92]:40402) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Tgdf1-00074t-WA for emacs-orgmode@gnu.org; Thu, 06 Dec 2012 10:46:57 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Tgdes-0007JT-8q for emacs-orgmode@gnu.org; Thu, 06 Dec 2012 10:46:51 -0500 Received: from plane.gmane.org ([80.91.229.3]:57521) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Tgdes-0007JI-2C for emacs-orgmode@gnu.org; Thu, 06 Dec 2012 10:46:42 -0500 Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1Tgdf2-0008Ok-0y for emacs-orgmode@gnu.org; Thu, 06 Dec 2012 16:46:52 +0100 Received: from geodiff-mac3.ulb.ac.be ([164.15.131.113]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 06 Dec 2012 16:46:51 +0100 Received: from theonewiththeevillook by geodiff-mac3.ulb.ac.be with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 06 Dec 2012 16:46:51 +0100 List-Id: "General discussions about Org-mode." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org Sender: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org To: emacs-orgmode@gnu.org --=-=-= Content-Type: text/plain Hello, (org-babel-edit-distance "foo" "ffoo") returns 0, whereas 1 seems appropriate. I don't know much about computing the levenshtein distance, but it seems that part of the algorithm (which i found explained on fr.wikipedia) is missing from the code. Please find a patch below trying to address the issue. -- Nico. --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0001-ob-Fix-org-babel-edit-distance-for-insertion-deletio.patch >From 448cecaf3d6618274719fc6fa96f278b7202b784 Mon Sep 17 00:00:00 2001 From: "nrichard (geodiff-mac3)" Date: Thu, 6 Dec 2012 16:38:44 +0100 Subject: [PATCH] ob: Fix org-babel-edit-distance for insertion/deletion * lisp/ob.el (org-babel-edit-distance): When insertion or deletion are needed, make sure the distance is incremented. In addition, the now obsolete mmin function was removed. --- lisp/ob.el | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) diff --git a/lisp/ob.el b/lisp/ob.el index c030a7f..0aba523 100644 --- a/lisp/ob.el +++ b/lisp/ob.el @@ -629,16 +629,19 @@ arguments and pop open the results in a preview buffer." (l2 (length s2)) (dist (vconcat (mapcar (lambda (_) (make-vector (1+ l2) nil)) (number-sequence 1 (1+ l1))))) - (in (lambda (i j) (aref (aref dist i) j))) - (mmin (lambda (&rest lst) (apply #'min (remove nil lst))))) + (in (lambda (i j) (aref (aref dist i) j)))) (setf (aref (aref dist 0) 0) 0) + (dolist (j (number-sequence 1 l2)) + (setf (aref (aref dist 0) j) j)) (dolist (i (number-sequence 1 l1)) + (setf (aref (aref dist i) 0) i) (dolist (j (number-sequence 1 l2)) (setf (aref (aref dist i) j) - (+ (if (equal (aref s1 (1- i)) (aref s2 (1- j))) 0 1) - (funcall mmin (funcall in (1- i) j) - (funcall in i (1- j)) - (funcall in (1- i) (1- j))))))) + (min + (1+ (funcall in (1- i) j)) + (1+ (funcall in i (1- j))) + (+ (if (equal (aref s1 (1- i)) (aref s2 (1- j))) 0 1) + (funcall in (1- i) (1- j))))))) (funcall in l1 l2))) (defun org-babel-combine-header-arg-lists (original &rest others) -- 1.8.0 --=-=-=--