[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] add 'string-distance' to calculate Levenshtein distance
From: |
Chen Bin |
Subject: |
Re: [PATCH] add 'string-distance' to calculate Levenshtein distance |
Date: |
Sun, 15 Apr 2018 17:15:49 +1000 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) |
I attached patch for latest code.
As required, now by default we compare the string by character. So
it can handle multibyte character correctly.
'string-distance' has third optional parameter 'bytecompare' which
use byte comparing instead of default character comparing.
I did read this thread carefully and I did know different algorithms
exist to calculate string distance.
But I feel only my code is the right solution to our original problem.
Our original problem is to provide a faster C solution to calculate
*Levenshtein distance*.
It will replace 3rd party Lisp solution like 'org-babel-edit-distance'.
As 'org-babel-edit-distance' documented, it will "Return the edit
(levenshtein) distance between strings S1 S2". So the problem here is to
calculate *Levenshtein distance*.
Other algorithms have their own definition of "string distance" so they
are not for *Levenshtein distance*.
Here is link of "Comparison of String Distance Algorithms":
https://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/
>From 657ee7f92e5bfd6f5138e9d0b030bd80ff963b16 Mon Sep 17 00:00:00 2001
From: Chen Bin <address@hidden>
Date: Sun, 15 Apr 2018 02:20:29 +1000
Subject: [PATCH] add api string-distance
---
etc/NEWS | 2 ++
src/fns.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
test/lisp/subr-tests.el | 18 ++++++++++++++++++
3 files changed, 69 insertions(+)
diff --git a/etc/NEWS b/etc/NEWS
index 0c4daee9ac..7c9f3feaa7 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -484,6 +484,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..ce1e5be1ed 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -153,6 +153,54 @@ 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.
+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);
+ bool same;
+ char *s1 = SSDATA (string1);
+ char *s2 = SSDATA (string2);
+
+ ptrdiff_t len1 = use_bytecompare? SBYTES (string1) : SCHARS (string1);
+ ptrdiff_t len2 = use_bytecompare? SBYTES (string2) : SCHARS (string2);
+ ptrdiff_t x, y, lastdiag, olddiag;
+ unsigned short *ws1 = 0; /* 16 bit unicode character */
+ unsigned short *ws2 = 0; /* 16 bit unicode character */
+ if(!use_bytecompare)
+ {
+ /* convert utf-8 byte stream to 16 bit unicode array */
+ string1 = code_convert_string_norecord (string1, Qutf_16le, 1);
+ ws1 = (unsigned short *) SDATA (string1);
+ string2 = code_convert_string_norecord (string2, Qutf_16le, 1);
+ ws2 = (unsigned short *) SDATA (string2);
+ }
+
+ USE_SAFE_ALLOCA;
+ ptrdiff_t *column = SAFE_ALLOCA ((len1 + 1) * sizeof (ptrdiff_t));
+ for (y = 1; y <= len1; y++)
+ column[y] = y;
+ for (x = 1; x <= len2; x++)
+ {
+ column[0] = x;
+ for (y = 1, lastdiag = x - 1; y <= len1; y++)
+ {
+ olddiag = column[y];
+ same = use_bytecompare? (s1[y-1] == s2[x-1]) : (ws1[y-1] ==
ws2[x-1]);
+ column[y] = min (min (column[y] + 1, column[y-1] + 1), lastdiag +
(same? 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 +5274,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
>>>>> "Eli" == Eli Zaretskii <address@hidden> writes:
>> From: Chen Bin <address@hidden> Cc: address@hidden
>> Date: Sun, 15 Apr 2018 02:40:18 +1000
>>
>> Correct me if I'm wrong.
>>
>> I read cod eand found definion of Lisp_String: struct GCALIGNED
>> Lisp_String { ptrdiff_t size; ptrdiff_t size_byte; INTERVAL
>> intervals; /* Text properties in this string. */ unsigned char
>> *data; };
>>
>> I understand string text is encoded in UTF8 format and is stored
>> in 'Lisp_String::data'. There is actually no difference between
>> unibyte and multibyte text since UTF8 is compatible with ASCII
>> and we only deal with 'data' field.
Eli> No, that's incorrect. The difference does exist, it just all
Eli> but disappear for unibyte strings encoded in UTF-8. But if you
Eli> encode a string in some other encoding, like Latin-1, you will
Eli> see a very different stream of bytes.
>> I attached the latest patch.
Eli> Thanks.
>> + ;; string containing unicode character (Hanzi) + (should (equal
>> 6 (string-distance "ab" "ab我她"))) + (should (equal 3
>> (string-distance "我" "她"))))
Eli> Should the distance be measured in bytes or in characters? I
Eli> think it's the latter, in which case the implementation should
Eli> work in characters, not bytes.
--
Best Regards,
Chen Bin
--
Help me, help you
- [PATCH] add 'string-distance' to calculate Levenshtein distance, Chen Bin, 2018/04/13
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/14
- Message not available
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/14
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Chen Bin, 2018/04/14
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/14
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance,
Chen Bin <=
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/15
- Message not available
- Message not available
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/16
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/17
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/18
- Message not available
- Message not available
- Message not available
- Message not available
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/17
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/19
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/19
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/20
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/20
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/21