課題

入力に対して、文字列集合の中から最も似ている文字列を返したい。

例

["gmail", "googlemap", "googledrive", "dockerhub", "github"]という集合がある。

"mail" と入力されると "gmail" が返ってきて、"docker" と入力されると "dockerhub" が返ってくるという風にしたい。

解決策

編集距離というものがある。ある文字列から別の文字列に変換する際に挿入・削除・置換を何度行うかというものである。ある文字とある文字列の最小編集距離をレーベンシュタイン距離と言う。集合の中からレーベンシュタイン距離が最小の単語を選ぶことは、最も類似している単語を選ぶことになる。

mailからgmailは、gを先頭に追加するのでレーベンシュタイン距離 1 となる。 mailからgooglemapは、lを削除、iをpに置換、先頭にgoogleを挿入でレーベンシュタイン距離 8 となる。 mailはgooglemapよりgmailに似ていることになる。

Goのライブラリ

レーベンシュタイン距離の計算は動的計画法を用いることで実装できる。長さ n と長さ m の文字列間の距離を求めるには(n + 1)×(m + 1) の二次元行列が使われ計算量O(mn)と効率よく計算できる。

実装は他記事にお任せして今回はライブラリを使う。

github.com

func main() {
    // 挿入・削除・置換それぞれに重みをつけることができる
    myOptions := levenshtein.Options{
        InsCost: 1,
        DelCost: 1,
        SubCost: 1, // DefaultOptionsでは2
        Matches: levenshtein.IdenticalRunes,
    }
    source := "mail"
    target := "googlemap"
    distance := levenshtein.DistanceForStrings([]rune(source), []rune(target), myOptions)
    fmt.Printf("Distance between %s and %s computed as %d\n", source, target, distance)
}

// Output
// Distance between mail and googlemap computed as 8

類似検索例

ユーザーの入力した単語から類似している単語を検索する際に書いた。ユーザーの入力は、実際の本当の名前より短くなることが多いので、DelCost を小さくすることで適合する結果が返ることが多かった。

// sourcesの中から、targetに最も類似している単語を返す関数
// target, sources共に事前に小文字化、空白除去等の前処理をしておく
func getSimilarWord(target string, sources []string) string {
    // レーベンシュタイン距離を計算する際の重みづけ
    // 削除の際の距離を小さくしている
    myOptions := levenshtein.Options{
        InsCost: 10,
        DelCost: 1,
        SubCost: 10,
        Matches: levenshtein.IdenticalRunes,
    }

    // それぞれの距離を計算し格納する
    distances := make([]int, len(sources))
    for i := 0; i < len(sources); i++ {
        distances[i] = levenshtein.DistanceForStrings([]rune(sources[i]), []rune(target), myOptions)
    }

    // 距離が最小のもののインデックスを取得する
    minIdx := 0
    minDistance := 1000000 // 十分大きな数
    for i := 0; i < len(distances); i++ {
        if distances[i] <= minDistance {
            minDistance = distances[i]
            minIdx = i
        }
    }
    return sources[minIdx]
}