レーベンシュタイン距離

情報理論、言語学、コンピュータ科学において、レーベンシュタイン距離は、2 つのシーケンス間の違いを測定するための文字列距離です。2 つの単語間のレーベンシュタイン距離は、一方の単語をもう一方の単語に変更するために必要な、1 文字の編集 (挿入、削除、または置換) の最小数です。これは、1965 年にこの距離を定義したソビエトの数学者ウラジーミル・レーベンシュタインにちなんで名付けられました。 ^{[ 1 ]}

レーベンシュタイン距離は編集距離とも呼ばれるが、この用語はより広い範囲の距離尺度を指す場合もある。^{[ 2 ]： 32}これはペアワイズ文字列アライメントと密接に関連している。

2本の弦間のレーベンシュタイン距離${\displaystyle a,b}$（長さ）${\displaystyle |a|}$そして${\displaystyle |b|}$それぞれ)は次のように与えられる${\displaystyle \operatorname {lev} (a,b)}$どこ

${\displaystyle \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ otherwise}}\end{cases}}}$

どこで${\displaystyle \operatorname {tail} }$ある文字列の${\displaystyle x}$最初の文字を除くすべての文字の文字列です${\displaystyle x}$（つまり）$\displaystyle \operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}}$）、 そして${\displaystyle \operatorname {head} (x)}$は最初の文字です${\displaystyle x}$（つまり）$\displaystyle \operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}}$) 表記法${\displaystyle x[n]}$または${\displaystyle x_{n}}$は、${\displaystyle n}$文字列の 番目の文字${\displaystyle x}$0から数えて 、したがって${\displaystyle \operatorname {head} (x)=x_{0}=x[0]}$。

最小値の最初の要素は削除に対応します（${\displaystyle a}$に${\displaystyle b}$）、2番目は挿入、3番目は交換です。

この定義は、素朴な再帰的実装に直接対応しています。

特別なケースがない式は次のとおりです。 ${\displaystyle {\begin{aligned}\operatorname {lev} (a,b)&=|a|+|b|-f(a,b)\\f(a,b)&=\max {\begin{cases}0\\1+f{\big (}\operatorname {tail} (a),b{\big )}\\1+f{\big (}a,\operatorname {tail} (b){\big )}\\1+{\big [}\operatorname {head} (a)=\operatorname {head} (b){\big ]}+f{\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\end{cases}}\end{aligned}}}$

近似文字列マッチングでは、少数の差異が予想される状況において、多数の長いテキストの中から短い文字列の一致を見つけることが目的です。短い文字列は、例えば辞書から取得できます。この場合、一方の文字列は通常短く、もう一方は任意の長さです。この手法は、スペルチェッカー、光学文字認識の修正システム、翻訳メモリに基づく自然言語翻訳支援ソフトウェアなど、幅広い用途があります。

レーベンシュタイン距離は、より長い2つの文字列間でも計算できますが、計算コストは​​2つの文字列の長さの積にほぼ比例するため、実用的ではありません。したがって、レコードリンケージなどのアプリケーションであいまい文字列検索を支援するために使用する場合は、比較速度を向上させるために、比較対象の文字列は通常短くなります。

言語学では、レーベンシュタイン距離は言語的距離、つまり2つの言語が互いにどれだけ異なっているかを定量化する指標として使用されます。^{[ 3 ]}これは相互理解可能性と関連しています。言語的距離が大きいほど相互理解可能性は低くなり、言語的距離が小さいほど相互理解可能性は高くなります。

レーベンシュタイン距離は、音声聴力検査などのさまざまな用途において、音声識別テスト中のリスナーのパフォーマンスを定量化するために使用できます。この文脈では、レーベンシュタイン距離は、リスナーに提示された刺激と識別された音素のシーケンス間の距離を定量化するために計算されます。音素置換に関連するコストは、固定されている場合と、置換された 2 つの音素間で異なる音韻的特徴の数に依存する場合があります。^{[ 4 ]}

バイオインフォマティクスでは、レーベンシュタイン距離や類似のアルゴリズムは、DNAやタンパク質などの生物学的配列間の違いを測定します。アルゴリズムの編集は、遺伝子変異、すなわちヌクレオチド（DNA）またはアミノ酸（タンパク質）の挿入、欠失、または置換に対応します。2つの配列間の距離が小さいほど、進化的または機能的な関係が近いことを示します。^{[ 5 ]}

編集距離には他にも一般的な指標があり、それらは異なる一連の許容編集操作を使用して計算されます。例えば、次のとおりです。

• ダメラウ・レーベンシュタイン距離は、挿入、削除、置換に加えて、隣接する2つの文字の転置を可能にする。
• 最長共通部分配列（LCS）距離では、挿入と削除のみが可能であり、置換は不可能である。
• ハミング距離は置換のみを許容するため、同じ長さの文字列にのみ適用されます。
• Jaro距離は転置のみを許容する。

編集距離は通常、特定の許容編集操作セットを用いて計算されるパラメータ化可能な指標として定義され、各操作にはコスト（場合によっては無限大）が割り当てられます。これは、Smith-WatermanアルゴリズムなどのDNA配列アライメントアルゴリズムによってさらに一般化され、操作のコストはそれが適用される場所によって変化します。

• Black, Paul E. 編 (2008年8月14日)、「レーベンシュタイン距離」、アルゴリズムとデータ構造の辞典[オンライン]、米国国立標準技術研究所、 2016年11月2日取得
• Rosettaコードによるレーベンシュタイン距離の実装