レーベンシュタイン距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』

レーベンシュタイン距離（レーベンシュタインきょり）あるいは編集距離（へんしゅうきょり）は、情報理論において、二つの文字列がどの程度異なっているかを示す数値である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。

この用語は、1965年にこの距離の概念を考案したロシアの学者ウラジミール・レーベンシュタインにちなんで命名された。スペルチェッカー等において、二つの文字列がどの程度に類似しているかの決定が求められる場合、レーベンシュタイン距離の応用は有用である。

さらなる応用として注目を浴びつつあるのがバイオインフォマティクス分野での活用であり、DNA配列同士の類似性を判断するために応用されている。これはDNAが挿入・欠失・置換の3様式によって変化していくことの反映である。異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定するなどを実現している。

実際的な距離の求め方を例示すれば、“kitten”を“sitting”に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。

kitten
sitten （“k”を“s”に置換）
sittin （“e”を“i”に置換）
sitting （“g”を挿入して終了）

レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。

[編集] アルゴリズム

レーベンシュタイン距離を計算するためには、一般的に動的計画法によるアルゴリズムが用いられている。長さ 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 ] )
   // lenStr1 + 1 行 lenStr2 + 1 列のテーブル d を用意する
   declare int d[ 0..lenStr1, 0..lenStr2 ]
   // str1 と str2 を数え上げる変数 i1 と i2 を用意する
   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,     // 文字の挿入
                                    d[ i1    , i2 - 1 ] + 1,     // 文字の削除
                                    d[ i1 - 1, i2 - 1 ] + cost   // 文字の置換
                                     )
 
   return d[ lenStr1, lenStr2 ]