レーベンシュタイン距離
レーベンシュタイン距離（レーベンシュタインきょり）あるいは編集距離（へんしゅうきょり）は、情報理論において、二つの文字列がどの程度異なっているかを示す数値である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。
この用語は、1965年にこの距離の概念を考案したロシアの学者ウラジミール・レーベンシュタインにちなんで命名された。スペルチェッカー等において、二つの文字列がどの程度に類似しているかの決定が求められる場合、レーベンシュタイン距離の応用は有用である。
さらなる応用として注目を浴びつつあるのがバイオインフォマティクス分野での活用であり、DNA配列同士の類似性を判断するために応用されている。これはDNAが挿入・欠失・置換の3様式によって変化していくことの反映である。異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定するなどを実現している。
実際的な距離の求め方を例示すれば、“kitten”を“sitting”に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。
- kitten
- sitten （“k”を“s”に置換）
- sittin （“e”を“i”に置換）
- sitting （“g”を挿入して終了）
上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、“kitten”と“sitting”の間のレーベンシュタイン距離は5となる[1]。
レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。
アルゴリズム
レーベンシュタイン距離を計算するためには、一般的に動的計画法によるアルゴリズムが用いられている。長さ n と長さ m の文字列間の距離を求めるには (n + 1)×(m + 1) の二次元行列が使われ、計算時間はO(mn)と非常に効率がよい。
このアルゴリズムの要諦は、
- 1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる
- 長さ 0 の文字列と長さ x の文字列の距離は x である
の2点から帰納的に求めることができるという点である。
以下に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の 文字列 str2 間のレーベンシュタイン距離を求める擬似コードを示す。
int LevenshteinDistance ( char str1[ 1..lenStr1 ], char str2[ 1..lenStr2 ] ) テンプレート:Color declare int d[ 0..lenStr1, 0..lenStr2 ] テンプレート:Color declare int i1, i2, cost for i1 from 0 to lenStr1 d[ i1, 0 ] := i1 for i2 from 0 to lenStr2 d[ 0, i2 ] := i2 for i1 from 1 to lenStr1 for i2 from 1 to lenStr2 if str1[ i1 ] = str2[ i2 ] then cost := 0 else cost := 1 d[ i1, i2 ] = minimum( d[ i1 - 1, i2 ] + 1, テンプレート:Color d[ i1 , i2 - 1 ] + 1, テンプレート:Color d[ i1 - 1, i2 - 1 ] + cost テンプレート:Color ) return d[ lenStr1, lenStr2 ]
参考文献
- ↑ Daniel Jurafsky and James H.Martin: Speech and Laguage Processing, pp.74, Prentice Hall, 2009, ISBN 0-13-187321-0
外部リンク
- 編集距離 挿入・削除をコスト1、置換をコスト2で文字列間の編集距離を計算して出力するソフト
