-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
levenshtein.go
46 lines (40 loc) · 889 Bytes
/
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
// Simplest forms of Levenshtein Distance Calculation Functions
// this is case-sensitive
package howlongtobeat
func lowest(a, b, c int) int {
if a < b {
if a < c {
return a
}
} else {
if b < c {
return b
}
}
return c
}
func levenshtein(str1, str2 []rune) (int, float64) {
str1len := len(str1)
str2len := len(str2)
distance := make([]int, str1len+1)
for i := 1; i <= str1len; i++ {
distance[i] = i
}
for j := 1; j <= str2len; j++ {
distance[0] = j
lastkey := j - 1
for i := 1; i <= str1len; i++ {
oldkey := distance[i]
var incr int
if str1[i-1] != str2[j-1] {
incr = 1
}
distance[i] = lowest(distance[i]+1, distance[i-1]+1, lastkey+incr)
lastkey = oldkey
}
}
levdistance := distance[str1len]
var similarity float64
similarity = (float64(str2len) - float64(levdistance)) / float64(str2len)
return levdistance, similarity
}