1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
// Fuzzy searching allows for flexibly matching a string with partial input,
// useful for filtering data very quickly based on lightweight user input.
package fuzzy
import (
"unicode"
"unicode/utf8"
)
var noop = func(r rune) rune { return r }
// Match returns true if source matches target 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
// approximation. The method will return true only if each character in the
// source can be found in the target and occurs after the preceding matches.
func Match(source, target string) bool {
return match(source, target, noop)
}
// MatchFold is a case-insensitive version of Match.
func MatchFold(source, target string) bool {
return match(source, target, unicode.ToLower)
}
func match(source, target string, fn func(rune) rune) bool {
lenDiff := len(target) - len(source)
if lenDiff < 0 {
return false
}
if lenDiff == 0 && source == target {
return true
}
Outer:
for _, r1 := range source {
for i, r2 := range target {
if fn(r1) == fn(r2) {
target = target[i+utf8.RuneLen(r2):]
continue Outer
}
}
return false
}
return true
}
// Find will return a list of strings in targets that fuzzy matches source.
func Find(source string, targets []string) []string {
return find(source, targets, noop)
}
// FindFold is a case-insensitive version of Find.
func FindFold(source string, targets []string) []string {
return find(source, targets, unicode.ToLower)
}
func find(source string, targets []string, fn func(rune) rune) []string {
var matches []string
for _, target := range targets {
if match(source, target, fn) {
matches = append(matches, target)
}
}
return matches
}
// RankMatch is similar to Match except it will measure the Levenshtein
// distance between the source and the target and return its result. If there
// was no match, it will return -1.
// Given the requirements of match, RankMatch only needs to perform a subset of
// the Levenshtein calculation, only deletions need be considered, required
// additions and substitutions would fail the match test.
func RankMatch(source, target string) int {
return rank(source, target, noop)
}
// RankMatchFold is a case-insensitive version of RankMatch.
func RankMatchFold(source, target string) int {
return rank(source, target, unicode.ToLower)
}
func rank(source, target string, fn func(rune) rune) int {
lenDiff := len(target) - len(source)
if lenDiff < 0 {
return -1
}
if lenDiff == 0 && source == target {
return 0
}
runeDiff := 0
Outer:
for _, r1 := range source {
for i, r2 := range target {
if fn(r1) == fn(r2) {
target = target[i+utf8.RuneLen(r2):]
continue Outer
} else {
runeDiff++
}
}
return -1
}
// Count up remaining char
for len(target) > 0 {
target = target[utf8.RuneLen(rune(target[0])):]
runeDiff++
}
return runeDiff
}
// RankFind is similar to Find, except it will also rank all matches using
// Levenshtein distance.
func RankFind(source string, targets []string) Ranks {
var r Ranks
for index, target := range targets {
if match(source, target, noop) {
distance := LevenshteinDistance(source, target)
r = append(r, Rank{source, target, distance, index})
}
}
return r
}
// RankFindFold is a case-insensitive version of RankFind.
func RankFindFold(source string, targets []string) Ranks {
var r Ranks
for index, target := range targets {
if match(source, target, unicode.ToLower) {
distance := LevenshteinDistance(source, target)
r = append(r, Rank{source, target, distance, index})
}
}
return r
}
type Rank struct {
// Source is used as the source for matching.
Source string
// Target is the word matched against.
Target string
// Distance is the Levenshtein distance between Source and Target.
Distance int
// Location of Target in original list
Index int
}
type Ranks []Rank
func (r Ranks) Len() int {
return len(r)
}
func (r Ranks) Swap(i, j int) {
r[i], r[j] = r[j], r[i]
}
func (r Ranks) Less(i, j int) bool {
return r[i].Distance < r[j].Distance
}
|
