レーベンシュタイン距離

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

レーベンシュタイン距離(レーベンシュタインきょり)あるいは編集距離(へんしゅうきょり)は、二つの文字列がどの程度異なっているかを示す距離(距離空間を参照)である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。名称は、1965年にこれを考案したロシアの学者ウラジミール・レーベンシュタインにちなむ。

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

Bitapアルゴリズムが、レーベンシュタイン距離がある値以下のパターンを検出するアルゴリズムとして知られている。agrepという実装がある。

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

  1. kitten
  2. sitten (“k”を“s”に置換)
  3. sittin (“e”を“i”に置換)
  4. 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 ] )
   // 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 ]

参考文献[編集]

  1. ^ Daniel Jurafsky and James H.Martin: Speech and Laguage Processing, pp.74, Prentice Hall, 2009, ISBN 0-13-187321-0

外部リンク[編集]

  • 編集距離 挿入・削除をコスト1、置換をコスト2で文字列間の編集距離を計算して出力するソフト