-
Notifications
You must be signed in to change notification settings - Fork 5
/
levenshtein.go
67 lines (63 loc) · 1.34 KB
/
levenshtein.go
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
package argparse
func decideMatch(target string, candidates []string) []string {
if len(candidates) <= 0 {
return []string{} // no match at all
}
ldArray := make([]int, len(candidates))
for i, c := range candidates {
ldArray[i] = levDistance(target, c)
}
match := min(ldArray...)
if match >= len(target) { // too many diff
return []string{}
}
matchCandidates := make(map[int][]string)
var matchKeys []int
for i, ld := range ldArray {
if ld == match {
wordL := len(candidates[i])
matchKeys = append(matchKeys, wordL)
matchCandidates[wordL] = append(matchCandidates[wordL], candidates[i])
}
}
return matchCandidates[min(matchKeys...)]
}
func levDistance(a, b string) int {
la := len(a)
lb := len(b)
matrix := make([][]int, la+1)
for i := range matrix {
matrix[i] = make([]int, lb+1)
}
for i := 0; i <= la; i += 1 {
matrix[i][0] = i
}
for i := 0; i <= lb; i += 1 {
matrix[0][i] = i
}
for i := 1; i <= la; i += 1 {
for j := 1; j <= lb; j += 1 {
cost := 1
if a[i-1] == b[j-1] {
cost = 0
}
matrix[i][j] = min(
matrix[i-1][j-1]+cost,
matrix[i][j-1]+1,
matrix[i-1][j]+1)
}
}
return matrix[la][lb]
}
func _min(a, b int) int {
if a < b {
return a
}
return b
}
func min(candidate ...int) int {
if len(candidate) == 1 {
return candidate[0]
}
return _min(candidate[0], min(candidate[1:]...))
}