Re: [PATCH] add 'string-distance' to calculate Levenshtein distance

[chen bin <chenbin.sh@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1220 bytes --]

Hi, Eli,
As you suggested, I re-write the code using 'FETCH_STRING_CHAR_ADVANCE'.

I did some peformance test.

My original wide character array solution is two time fast as current solution.

But I understand now we avoid repeated memory allocation for wide
character array. So the generic performance looks OK to me.

I also implemented the byte comparing version. It's 4 times as fast. And I do
need use it to compare file path in my package 'counsel-etags'.

That's the major reason why I started this task

The fille path couldn't contain any funny characters (emoji). so
it'sperfectly fine
to use byte comparing version.

Regards,
Chen

On Tue, Apr 17, 2018 at 12:37 PM, Eli Zaretskii <eliz@gnu.org> wrote:
>> From: chen bin <chenbin.sh@gmail.com>
>> Date: Tue, 17 Apr 2018 11:32:23 +1000
>>
>> I  intentionally avoid cc `emacs-devel` in my previous mail  because I
>> feel `culture/race` is sensitive thing.
>
> Please don't.  There's no sensitivity about this stuff on emacs-devel,
> in my long experience with Emacs development.
>
>> I will study your mail and figure out a better solution.
>
> Thanks.  Feel free to ask more questions, and sorry again for my
> stupid typo mistake.
>



-- 
help me, help you.

[-- Attachment #2: 0001-add-api-string-distance.patch --]
[-- Type: text/x-patch, Size: 4751 bytes --]

From e785b766cf412c5d6b0c2d8a3f6e575675390c83 Mon Sep 17 00:00:00 2001
From: Chen Bin <chenbin.sh@gmail.com>
Date: Sun, 15 Apr 2018 02:20:29 +1000
Subject: [PATCH] add api string-distance

---
 etc/NEWS                |  2 ++
 src/fns.c               | 61 +++++++++++++++++++++++++++++++++++++++++++++++++
 test/lisp/subr-tests.el | 18 +++++++++++++++
 3 files changed, 81 insertions(+)

diff --git a/etc/NEWS b/etc/NEWS
index 5aa92e2991..3cce2c48c7 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -490,6 +490,8 @@ x-lost-selection-hooks, x-sent-selection-hooks
 +++
 ** New function assoc-delete-all.
 
+** New function string-distance to calculate Levenshtein distance between two strings.
+
 ** 'print-quoted' now defaults to t, so if you want to see
 (quote x) instead of 'x you will have to bind it to nil where applicable.
 
diff --git a/src/fns.c b/src/fns.c
index 94b9d984f0..ce779b2a79 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -153,6 +153,66 @@ If STRING is multibyte, this may be greater than the length of STRING.  */)
   return make_number (SBYTES (string));
 }
 
+DEFUN ("string-distance", Fstring_distance, Sstring_distance, 2, 3, 0,
+       doc: /* Return Levenshtein distance between STRING1 and STRING2.
+If BYTECOMPARE is nil, we compare character of strings.
+If BYTECOMPARE is t, we compare byte of strings.
+Comparing by byte is faster and non-ascii characters has weighted distance.
+Case is significant, but text properties are ignored. */)
+  (Lisp_Object string1, Lisp_Object string2, Lisp_Object bytecompare)
+{
+  CHECK_STRING (string1);
+  CHECK_STRING (string2);
+
+  bool use_bytecompare = !NILP(bytecompare);
+  ptrdiff_t len1 = SCHARS (string1);
+  ptrdiff_t len2 = SCHARS (string2);
+  ptrdiff_t x, y, lastdiag, olddiag;
+
+  USE_SAFE_ALLOCA;
+  ptrdiff_t *column = SAFE_ALLOCA ((len1 + 1) * sizeof (ptrdiff_t));
+  for (y = 1; y <= len1; y++)
+    column[y] = y;
+
+  if (use_bytecompare)
+    {
+      char *s1 = SSDATA (string1);
+      char *s2 = SSDATA (string2);
+
+      for (x = 1; x <= len2; x++)
+        {
+          column[0] = x;
+          for (y = 1, lastdiag = x - 1; y <= len1; y++)
+            {
+              olddiag = column[y];
+              column[y] = min (min (column[y] + 1, column[y-1] + 1), lastdiag + (s1[y-1] == s2[x-1]? 0 : 1));
+              lastdiag = olddiag;
+            }
+        }
+    }
+  else
+    {
+      int c1, c2;
+      ptrdiff_t i1, i1_byte, i2, i2_byte;
+      i2 = i2_byte = 0;
+      for (x = 1; x <= len2; x++)
+        {
+          column[0] = x;
+          FETCH_STRING_CHAR_ADVANCE (c2, string2, i2, i2_byte);
+          i1 = i1_byte = 0;
+          for (y = 1, lastdiag = x - 1; y <= len1; y++)
+            {
+              olddiag = column[y];
+              FETCH_STRING_CHAR_ADVANCE (c1, string1, i1, i1_byte);
+              column[y] = min (min (column[y] + 1, column[y-1] + 1), lastdiag + (c1 == c2? 0 : 1));
+              lastdiag = olddiag;
+            }
+        }
+    }
+  SAFE_FREE ();
+  return make_number (column[len1]);
+}
+
 DEFUN ("string-equal", Fstring_equal, Sstring_equal, 2, 2, 0,
        doc: /* Return t if two strings have identical contents.
 Case is significant, but text properties are ignored.
@@ -5226,6 +5286,7 @@ this variable.  */);
   defsubr (&Slength);
   defsubr (&Ssafe_length);
   defsubr (&Sstring_bytes);
+  defsubr (&Sstring_distance);
   defsubr (&Sstring_equal);
   defsubr (&Scompare_strings);
   defsubr (&Sstring_lessp);
diff --git a/test/lisp/subr-tests.el b/test/lisp/subr-tests.el
index 52b61d9fb9..1310f5b2a5 100644
--- a/test/lisp/subr-tests.el
+++ b/test/lisp/subr-tests.el
@@ -281,6 +281,24 @@ subr-test--frames-1
   (should (equal (string-match-p "\\`[[:blank:]]\\'" "\u3000") 0))
   (should-not (string-match-p "\\`[[:blank:]]\\'" "\N{LINE SEPARATOR}")))
 
+(ert-deftest subr-tests--string-distance ()
+  "Test `string-distance' behavior."
+  ;; ASCII characters are always fine
+  (should (equal 1 (string-distance "heelo" "hello")))
+  (should (equal 2 (string-distance "aeelo" "hello")))
+  (should (equal 0 (string-distance "ab" "ab" t)))
+  (should (equal 1 (string-distance "ab" "abc" t)))
+
+  ;; string containing hanzi character, compare by byte
+  (should (equal 6 (string-distance "ab" "ab我她" t)))
+  (should (equal 3 (string-distance "ab" "a我b" t)))
+  (should (equal 3 (string-distance "我" "她" t))
+
+  ;; string containing hanzi character, compare by character
+  (should (equal 2 (string-distance "ab" "ab我她")))
+  (should (equal 1 (string-distance "ab" "a我b")))
+  (should (equal 1 (string-distance "我" "她"))))
+
 (ert-deftest subr-tests--dolist--wrong-number-of-args ()
   "Test that `dolist' doesn't accept wrong types or length of SPEC,
 cf. Bug#25477."
-- 
2.16.3