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

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

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

Hi, Eli,

Attached is latest patch. It will use byte compare aglorithm if both
strings are not multi-byte strings.

Regards,
Chen

On Fri, Apr 20, 2018 at 12:55 AM, chen bin <chenbin.sh@gmail.com> wrote:
> Hi, Eli,
> I attached the new patch.
>
> A software project usually contains nomal directory and file names.
> Linux kernel source, for example.
>
> My package `counsel-etags` will use byte compare version.
>
> Regards,
> Chen
>
> On Thu, Apr 19, 2018 at 6:05 PM, Eli Zaretskii <eliz@gnu.org> wrote:
>>> From: chen bin <chenbin.sh@gmail.com>
>>> Date: Tue, 17 Apr 2018 22:31:20 +1000
>>> Cc: emacs-devel@gnu.org
>>>
>>> As you suggested, I re-write the code using 'FETCH_STRING_CHAR_ADVANCE'.
>>
>> Thanks.
>>
>>> 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'.
>>
>> File names are just strings for this purpose, and they can potentially
>> include any non-zero characters.  So I don't see why they are special.
>>
>>> The fille path couldn't contain any funny characters (emoji). so
>>> it'sperfectly fine
>>> to use byte comparing version.
>>
>> File names can very well include emoji and other "funny" characters,
>> Emacs supports that on all modern systems (including even MS-Windows).
>>
>>> 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.
>>
>> This long line should be filled using the fill-column setting we use
>> in NEWS.  Even better, make the header a short summary, like
>>
>>   ** New function 'string-distance'
>>
>> and then describe its functionality in a separate sentence that starts
>> immediately below that header.
>>
>>> +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.
>>
>> Please lose the "we" part, it's inappropriate in documentation,
>> because it describes what Emacs does.
>>
>>> +Comparing by byte is faster and non-ascii characters has weighted distance.
>>
>> I would delete this sentence, it is IMO confusing more than anything
>> else.  (And I still think the bytewise comparison is not needed.)
>>
>>> +  bool use_bytecompare = !NILP(bytecompare);
>>                                 ^^
>> Space between these 2 characters.
>>
>>> +  else
>>> +    {
>>> +      int c1, c2;
>>> +      ptrdiff_t i1, i1_byte, i2, i2_byte;
>>> +      i2 = i2_byte = 0;
>>> +      for (x = 1; x <= len2; x++)
>>
>> Please move the initialization of i2 and i2_byte into the for-loop
>> initializer (suing the comma operator).
>>
>>> +          i1 = i1_byte = 0;
>>> +          for (y = 1, lastdiag = x - 1; y <= len1; y++)
>>
>> Likewise here with i1 and i1_byte.
>>
>> Thanks.
>
>
>
> --
> help me, help you.



-- 
help me, help you.

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

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

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

diff --git a/etc/NEWS b/etc/NEWS
index 5aa92e2991..4efb7e983e 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -490,6 +490,9 @@ 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..6e851c8555 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -153,6 +153,67 @@ 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, compare character of strings.
+If BYTECOMPARE is t, compare byte of strings.
+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_byte_compare = !NILP (bytecompare)
+    || (!STRING_MULTIBYTE (string1) && !STRING_MULTIBYTE (string2));
+  ptrdiff_t len1 = use_byte_compare? SBYTES (string1) : SCHARS (string1);
+  ptrdiff_t len2 = use_byte_compare? SBYTES (string2) : 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_byte_compare)
+    {
+      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 = 0, 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 +5287,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