レーベンシュタイン距離 (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