レーベンシュタイン距離

レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される^[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。

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

例

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

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

上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、「kitten」と「sitting」の間のレーベンシュタイン距離は5となる^[2]。

アルゴリズム

→「wikibooks:Algorithm Implementation/Strings/Levenshtein distance」も参照

レーベンシュタイン距離を計算する際は、一般的に動的計画法によるアルゴリズムが用いられる。長さ $n$ と長さ $m$ の文字列間の距離を求めるには $(n+1)(m+1)$ の二次元行列が使われ、計算時間は $O(mn)$ と非常に効率がよい。

このアルゴリズムの要諦は、

1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる
長さ $0$ の文字列と長さ $L$ の文字列の距離は $L$ である

の2点から帰納的に求めることができるという点である。

以下に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の文字列 str2 間のレーベンシュタイン距離を求める擬似コードを示す。このコードにおいて d[i1,i2] には、str1 の i1 文字目までの文字列と str2 の i2 文字目までの文字列の間のレーベンシュタイン距離が格納される。

function LevenshteinDistance (Character str1 [1 to lenStr1], Character str2 [1 to lenStr2]) return Integer is
begin
   (* lenStr1+1 行 lenStr2+1 列のテーブル d を用意する *)
   variable Integer d [0 to lenStr1, 0 to lenStr2] ;
   
   for Integer i1 := 0 to lenStr1 do let d[i1,0] := i1 ;
   for Integer i2 := 0 to lenStr2 do let d[0,i2] := i2 ;
 
   for Integer i1 := 1 to lenStr1 do
       for Integer i2 := 1 to lenStr2 do
           begin
           constant Integer cost := if str1[i1] == str2[i2] then 0 else 1 ;
           let d[i1,i2] := minimum
             (
             d [i1-1, i2  ] + 1,     (* 文字の削除 *)
             d [i1  , i2-1] + 1,     (* 文字の挿入 *)
             d [i1-1, i2-1] + cost   (* 文字の置換 *)
             )
           end ;
   
   return d [lenStr1, lenStr2]
end

応用

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

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

脚注

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

参考文献

Gusfield, Dan (1997). Algorithms on strings, trees, and sequences. Cambridge University Press. ISBN 0-521-58519-8. MR1460730. Zbl 0934.68103

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[FOOTNOTEGusfield1997Definition-1] Gusfield 1997, Definition.

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

[1]

[2]

例

アルゴリズム

応用

脚注

関連項目

参考文献