レーベンシュタイン距離のソースを表示

<!-- 英語版ウィキペディア"Levenshtein distance" 18:42, 2 Apr 2005 の版より抄訳 --> 
'''レーベンシュタイン距離'''（レーベンシュタインきょり、{{lang-en-short|Levenshtein distance}}）は、二つの[[文字列]]がどの程度異なっているかを示す[[距離空間|距離]]の一種である。'''編集距離'''（へんしゅうきょり、{{lang-en-short|edit distance}}）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される{{sfn|Gusfield|1997|loc={{google books quote|id=Ofw5w1yuD8kC|page=216|Definition}}}}。名称は、1965年にこれを考案したロシアの学者[[ウラジーミル・レーベンシュタイン]] ({{lang-ru-short|Влади́мир Левенште́йн}}) にちなむ。

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

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

#「<code style="speak:spell-out">kitten</code>」
#「<code style="speak:spell-out">sitten</code>」（「<code style="speak:spell-out">k</code>」を「<code style="speak:spell-out">s</code>」に置換）
#「<code style="speak:spell-out">sittin</code>」（「<code style="speak:spell-out">e</code>」を「<code style="speak:spell-out">i</code>」に置換）
#「<code style="speak:spell-out">sitting</code>」（「<code style="speak:spell-out">g</code>」を挿入して終了）

上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、「<code style="speak:spell-out">kitten</code>」と「<code style="speak:spell-out">sitting</code>」の間のレーベンシュタイン距離は5となる<ref>Daniel Jurafsky and James H.Martin: ''Speech and Laguage Processing'', pp.74, Prentice Hall, 2009, ISBN 0-13-187321-0</ref>。

== アルゴリズム ==
{{see also|wikibooks:Algorithm Implementation/Strings/Levenshtein distance}}
レーベンシュタイン距離を計算する際は、一般的に[[動的計画法]]による[[アルゴリズム]]が用いられる。長さ <math>n</math> と長さ <math>m</math> の文字列間の距離を求めるには <math>(n+1)(m+1)</math> の二次元行列が使われ、計算時間は <math>O(mn)</math> と非常に効率がよい。

このアルゴリズムの要諦は、
*1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる
*長さ <math>0</math> の文字列と長さ <math>L</math> の文字列の距離は <math>L</math> である
の2点から帰納的に求めることができるという点である。

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

 '''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]]という実装がある。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book |last1=Gusfield |first1=Dan |year=1997 |title=Algorithms on strings, trees, and sequences |url={{google books|Ofw5w1yuD8kC|plainurl=yes}} |publisher=Cambridge University Press |isbn=0-521-58519-8 |mr=1460730 |zbl=0934.68103 |ref=harv }}

== 関連項目 ==
* [[ダメラウ・レーベンシュタイン距離]]
* [[ユークリッド距離]]
* [[ハミング距離]]
* [[距離空間]]
* [[最長共通部分列問題]]

{{DEFAULTSORT:れえへんしゆたいんきより}}
{{Computer-stub}}
[[Category:離散数学]]
[[Category:距離空間]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]