Current implementation assumes that strings are indexed by characters, this assumption

Fixed by <a class="issue-link js-issue-link" data-error-text="Failed to load title" da

Consider implementing support of multi-byte character sets about fuzzysearch HOT 4 CLOSED

lithammer commented on August 27, 2024

Consider implementing support of multi-byte character sets

from fuzzysearch.

Comments (4)

lithammer commented on August 27, 2024

Do you have any good cyrillic strings I can add to the tests? Preferably a negative, positive and equal match.

from fuzzysearch.

artyom commented on August 27, 2024

Please see this diff — it should introduce 2 failing tests — with 2 and 3-byte wide characters:

diff --git i/fuzzy/fuzzy_test.go w/fuzzy/fuzzy_test.go
index 11d946c..08e86a7 100644
--- i/fuzzy/fuzzy_test.go
+++ w/fuzzy/fuzzy_test.go
@@ -19,6 +19,10 @@ var fuzzyTests = []struct {
    {"art", "cartwheel", true, 6},
    {"eeel", "cartwheel", false, -1},
    {"dog", "cartwheel", false, -1},
+   {"ёлка", "ёлочка", true, 2},
+   {"ветер", "ёлочка", false, -1},
+   {"**", "中华人民共和国", true, 5},
+   {"日本", "中华人民共和国", false, -1},
 }

 func TestFuzzyMatch(t *testing.T) {

from fuzzysearch.

lithammer commented on August 27, 2024

Thanks, that will surely help. Seems like I'm gonna have to tweak the LevenshteinDistance function as well.

This is what I have so far at least, TestFuzzyMatch now passes with your additional tests:

diff --git a/fuzzy/fuzzy.go b/fuzzy/fuzzy.go
index 2751121..666311c 100644
--- a/fuzzy/fuzzy.go
+++ b/fuzzy/fuzzy.go
@@ -1,5 +1,7 @@
 package fuzzy

+import "unicode/utf8"
+
 // Match returns true if needle matches haystack using a fuzzy-searching
 // algorithm. Note that it doesn't implement Levenshtein distance (see
 // RankMatch instead), but rather a simplified version where there's no
@@ -16,12 +18,11 @@ func Match(needle, haystack string) bool {
        if nlen == hlen {
                return needle == haystack
        }
-
 Outer:
-       for i, j := 0, 0; i < nlen; i++ {
-               for j < hlen {
-                       j++
-                       if needle[i] == haystack[j-1] {
+       for _, r1 := range needle {
+               for i, r2 := range haystack {
+                       if r1 == r2 {
+                               haystack = haystack[i+utf8.RuneLen(r2):]
                                continue Outer
                        }
                }