blob: 237923d3450ec462fa8f35e81203742249695b5b (
plain)
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
|
package fuzzy
// LevenshteinDistance measures the difference between two strings.
// The Levenshtein distance between two words is the minimum number of
// single-character edits (i.e. insertions, deletions or substitutions)
// required to change one word into the other.
//
// This implemention is optimized to use O(min(m,n)) space and is based on the
// optimized C version found here:
// http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#C
func LevenshteinDistance(s, t string) int {
r1, r2 := []rune(s), []rune(t)
column := make([]int, len(r1)+1)
for y := 1; y <= len(r1); y++ {
column[y] = y
}
for x := 1; x <= len(r2); x++ {
column[0] = x
for y, lastDiag := 1, x-1; y <= len(r1); y++ {
oldDiag := column[y]
cost := 0
if r1[y-1] != r2[x-1] {
cost = 1
}
column[y] = min(column[y]+1, column[y-1]+1, lastDiag+cost)
lastDiag = oldDiag
}
}
return column[len(r1)]
}
func min(a, b, c int) int {
if a < b && a < c {
return a
} else if b < c {
return b
}
return c
}
|
