aobako.net
レーベンシュタイン距離 (LD)
October 12, 2020
編集距離ともいうらしい。編集 (挿入、削除、置換) を何回行うことで同一文字に変形できるか、その最短距回数を数値化したもの。距離が短ければその文字は似ているということなのかな?
アルゴリズムの疑似コードは wikipedia にある。
Go で書いてみるとこんな感じだろうか。
package main
import (
"fmt"
"flag"
)
func levenshtein_distance(s1, s2 string) int {
m := [][]int{}
for i := 0; i < len(s1) + 1; i++ {
inner := []int{}
for j := 0; j < len(s2) + 1; j++ {
inner = append(inner, j)
}
m = append(m, inner)
}
for i := 0; i < len(s1) + 1; i++ {
m[i][0] = i
}
for j := 0; j < len(s2) + 1; j++ {
m[0][j] = j
}
for i := 1; i < len(s1) + 1; i++ {
for j := 1; j < len(s2) + 1; j++ {
cost := 0
if s1[i - 1] != s2[j - 1] {
cost = 1
}
m[i][j] = min(m[i - 1][j] + 1, min(m[i][j - 1] + 1, m[i - 1][j - 1] + cost))
}
}
return m[len(s1)][len(s2)]
}
func min(a, b int) int {
if a >= b {
return b
}
return a
}
func main() {
flag.Parse()
fmt.Println(levenshtein_distance(flag.Arg(0), flag.Arg(1)))
}
$ go run levenshtein_distance.go kitten sitting
3
$ go run levenshtein_distance.go kitten
6
$ go run levenshtein_distance.go kitten aaaaaa
6