forked from antzucaro/matchr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dameraulevenshtein.go
50 lines (37 loc) · 1.1 KB
/
dameraulevenshtein.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
package matchr
func DamerauLevenshtein(s1 string, s2 string) (distance int) {
// index by code point, not byte
r1 := []rune(s1)
r2 := []rune(s2)
rows := len(r1) + 1
cols := len(r2) + 1
var i, j, d1, d2, d3, d_now, cost int
dist := make([]int, rows * cols)
for i = 0; i < rows; i++ {
dist[i * cols] = i
}
for j = 0; j < cols; j++ {
dist[j] = j
}
for i = 1; i < rows; i++ {
for j = 1; j < cols; j++ {
if (r1[i - 1] == r2[j - 1]) {
cost = 0
} else {
cost = 1
}
d1 = dist[((i - 1) * cols) + j] + 1
d2 = dist[(i * cols) + (j - 1)] + 1
d3 = dist[((i - 1) * cols) + (j - 1)] + cost
d_now = min(d1, min(d2, d3))
if i > 2 && j > 2 && r1[i - 1] == r2[j - 2] &&
r1[i - 2] == r2[j - 1] {
d1 = dist[((i - 2) * cols) + (j - 2)] + cost
d_now = min(d_now, d1)
}
dist[(i * cols) + j] = d_now
}
}
distance = dist[(cols * rows) - 1]
return
}