/
similar-sort.go
68 lines (56 loc) · 1.28 KB
/
similar-sort.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
68
package main
import "bufio"
import "fmt"
import "os"
import "sort"
import "strings"
import "unicode/utf8"
func main() {
target := strings.Join(os.Args[1:], " ")
s := bufio.NewScanner(os.Stdin)
var lines []WithDistance
for s.Scan() {
lines = append(lines, WithDistance{s.Text(), Levenshtein(target, s.Text())})
}
sort.Slice(lines, func(i, j int) bool {
return lines[i].distance < lines[j].distance
})
for _, line := range lines {
fmt.Println(line.text)
}
}
type WithDistance struct {
text string
distance int
}
// https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Go
// made available under CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0/
func Levenshtein(a, b string) int {
f := make([]int, utf8.RuneCountInString(b)+1)
for j := range f {
f[j] = j
}
for _, ca := range a {
j := 1
fj1 := f[0] // fj1 is the value of f[j - 1] in last iteration
f[0]++
for _, cb := range b {
mn := min(f[j]+1, f[j-1]+1) // delete & insert
if cb != ca {
mn = min(mn, fj1+1) // change
} else {
mn = min(mn, fj1) // matched
}
fj1, f[j] = f[j], mn // save f[j] to fj1(j is about to increase), update f[j] to mn
j++
}
}
return f[len(f)-1]
}
func min(a, b int) int {
if a <= b {
return a
} else {
return b
}
}