レーベンシュタイン距離 (rush/20/04/13)
文字列の類似度を測る方法の中にレーベンシュタイン距離というものがある。
レーベンシュタインは以下で定義される。
レーベンシュタイン距離(Levenshtein Distance)は，ある文字列と別の文字列の最小編集距離で表される距離である．
編集距離というのは、以下の操作に任意のコストを置くようになったもの
置換
削除
挿入
これらに任意のコストを割り振って、最短のコストで２つの文字列を一致させたときのコストがレーベンシュタイン距離である。
例えば
あいうおえとあいうえお は、１つ目の文字列に
パターン1
おを削除
おを挿入
パターン2
おをえに置換
えをおに置換
などの方法が考えられ、置換と挿入、削除操作のコストが等しく1ならパターン1もパターン2もコストは2になる。
実際に類似度として扱う時には、0から1の間の値で示してほしいので、標準化を行う。
標準化は以下で定式化される。
$ LD(s1,s2) = 最短編集距離/２つの文字列の長さの大きい方
特徴として
0に近いほど類似度が高い
動的計画法で実装されるらしい
スペルチェックやDNA解析の現場で類似度を計算するために用いられるらしい
機械学習の現場でもよく用いられるらしい
などなど、似た用途のものにジャロ・ウィンクラー距離がある。
参考文献