レーベンシュタイン距離

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

情報理論言語学、およびコンピュータサイエンスではレーベンシュタイン距離2つのシーケンス間の差を測定するための文字列メトリックです。非公式には、2つの単語間のレーベンシュタイン距離は、1つの単語を別の単語に変更するために必要な1文字の編集(挿入、削除、または置換)の最小数です。これは、1965年にこの距離を考慮したソビエトの数学者ウラジミールレベンシュテインにちなんで名付けられました。 [1]

レーベンシュタイン距離は、編集距離と呼ばれることもありますが、その用語は、編集距離総称される距離メトリックのより大きなファミリを表す場合もあります[2] :32 これはペアワイズ文字列の配置と密接に関連しています

定義

2つの弦の間のレーベンシュタイン距離(長さのそれぞれ)によって与えられますどこ

どこいくつかの文字列のの最初の文字を除くすべての文字列です、 とそれは文字列のth文字0から数えます

最小の最初の要素は削除に対応することに注意してください(から)、2番目は挿入、3番目は交換です。

この定義は、単純な再帰的実装に直接対応します

置換のコストを1として、削除または挿入のコストを0.5として使用して、2つの単語の距離マトリックスを編集します。

たとえば、「子猫」と「座っている」の間のレーベンシュタイン距離は3です。これは、次の3つの編集が一方を他方に変更し、3回未満の編集でそれを行う方法がないためです。

  1. kイッテン→シッテン(「k」の代わりに「s」を使用)
  2. sitt en →sitti n(「 e」の代わりに「i」を使用)
  3. sittin→sitting (末尾に「g」を挿入)

上限と下限

レーベンシュタイン距離には、いくつかの単純な上限と下限があります。これらには以下が含まれます:

  • それは少なくとも2つの弦のサイズの違いです。
  • それはせいぜい長い方の弦の長さです。
  • 文字列が等しい場合に限り、ゼロになります。
  • 文字列のサイズが同じである場合、ハミング距離はレーベンシュタイン距離の上限になります。ハミング距離は、2つの文字列の対応する記号が異なる位置の数です。
  • 2つのストリング間のレーベンシュタイン距離は、3番目のストリングからのレーベンシュタイン距離の合計以下です(三角不等式)。

同じ長さの2つの弦の間のレーベンシュタイン距離がハミング距離よりも厳密に短い例は、「欠陥」と「芝生」のペアによって与えられます。ここで、レーベンシュタイン距離は2に等しくなります(前から「f」を削除し、最後に「n」を挿入します)。ハミング距離4です。

アプリケーション

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

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

言語学では、レーベンシュタイン距離は、言語間距離、つまり2つの言語が互いにどの程度異なるかを定量化するためのメトリックとして使用されます。[3]相互理解可能性に関連しています。言語間距離が長いほど相互理解可能性は低く、言語間距離が低いほど相互理解可能性は高くなります。

他の編集距離メトリックとの関係

編集距離の一般的な測定値は他にもあります。これらは、許容される編集操作の異なるセットを使用して計算されます。例えば、

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

計算

再帰的

これは単純ですが、非効率的で再帰的なHaskelllDistanceの関数の実装であり、 2つの文字列stをそれらの長さとともに受け取り、それらの間のレーベンシュタイン距離を返します。

lDistance  ::  Eq  a  =>  [ a ]  ->  [ a ]  ->  Int 
lDistance  []  t  =  length  t  - sが空の場合、距離は
tlDistanceの文字数です s  []  =  length  s-  tが空の場合、距離はsの
文字数ですlDistance  a   s '  b   t'  = 
  if  a  ==  b 
    then  lDistance  s ' t'- 最初の文字が同じ場合は無視できます
    else1 +最小
      -
        それ以外の場合は、3つの可能なアクションすべてを試して、最適なアクションを選択します[ lDistance a s ' t' -文字が挿入されます( b挿入)lDistance s ' b t ' -文字が削除されます(削除されます)lDistance s't'-文字が置き換えられます(aがbに置き換えられます)]  
                
                 
               
          

この実装は、同じ部分文字列のレーベンシュタイン距離を何度も再計算するため、非常に非効率的です。

より効率的な方法では、同じ距離の計算が繰り返されることはありません。たとえば、すべての可能なプレフィックスのレーベンシュタイン距離が配列に格納される場合があります、 どこ最後の間の距離です文字列sと最後の文字文字列の文字tテーブルは、行0から一度に1行ずつ簡単に作成できます。テーブル全体が作成されると、必要な距離が最後の行と列のテーブルにあり、のすべての文字sとすべての文字の間の距離を表します。の文字t

完全な行列で反復

(注:このセクションでは、0ベースの文字列ではなく1ベースの文字列を使用します。)

レーベンシュタイン距離の計算は、最初の文字列のすべてのプレフィックスと2番目の文字列のすべてのプレフィックスの間のレーベンシュタイン距離を保持する行列を予約すると、動的計画法で行列の値を計算できるという観察に基づいています。したがって、最後に計算された値として、2つの完全な文字列間の距離を見つけます。

ボトムアップ動的計画法の例であるこのアルゴリズムは、1974年記事Robert A.WagnerとMichaelJ.Fischerによる文字列から文字列への修正問題でさまざまな形で説明されています。[4]

これは、長さmのs長さnのtの2つの文字列を取り、それらの間のレーベンシュタイン距離を返す 関数の簡単な擬似コード実装です。LevenshteinDistance

function  LevenshteinDistance char  s [ 1 .. m ]  char  t [ 1 .. n ])
  //すべてのiとjについて、d [i、j]は
  // sの最初のi文字間のレーベンシュタイン距離を保持します
  tの最初のj文字はintd [ 0 .. m 0 ..n ]を宣言し ます  
 
   dの 要素  ゼロに設定します  
 
  
  //ソースプレフィックスは、// iのすべての文字1からmドロップ
  することで空の文字列に変換できますd [ i 0 ] := i     
       
 
  //空のソースプレフィックスからターゲットプレフィックスに到達できます// 
  1からnまでのjのすべての文字挿入します
  d [ 0 j ] := j     
       
 
  for  j  from  1  to  n 
    for  i  from  1  to  m 
      if  s [ i ]  =  t [ j ] 
        substitutionCost  :=  0 
      else 
        substitutionCost  :=  1

      d [ i  j ]  := 最小d [ i - 1  j ]  +  1                    //削除
                         d [ i  j - 1 ]  +  1                    //挿入
                         d [ i - 1  j - 1 ]  +  substitutionCost   //置換
 
   d [ m  n ]を返します

結果の行列の2つの例(タグ付きの数値にカーソルを合わせると、その数値を取得するために実行された操作が表示されます):

アルゴリズム全体で維持される不変条件は、最初のセグメント最小限操作を使用するように変換できることです。最後に、配列の右下の要素に答えが含まれています。 s[1..i]t[1..j]d[i, j]

2つの行列行で反復

編集された入力文字列を再構築したくない場合は、テーブルの2つの行(前の行と計算中の現在の行)のみが構築に必要であることがわかります。

レーベンシュタイン距離は、次のアルゴリズムを使用して繰り返し計算できます。[5]

function  LevenshteinDistance char  s [ 0 .. m --1 ] char t [ 0 .. n --1 ] : //整数距離の2つの作業ベクトルを作成declare int v0 [ n + 1 ] describe int v1 [ n + 1 ]  
    
        
        

    // v0(距離の前の行)を初期化します
    //この行はA [0] [i]です。空のsからtまでの距離を編集します。
    //その距離は、tを作成するためにsに追加する文字数です。
    0からnまで iの場合 v0 [ i ] = i   
          

    for  i  0から m - 1 //前の行v0からv1(現在の行距離)を計算します    
        

        
        // v1の最初の要素はA [i + 1] [0]です//編集距離は空のtv1 [ 0 ] = i + 1に一致するようにsから(i + 1)文字を削除します
            

        //数式を使用して
        jの残りの行 0からn - 1まで入力します:// A [i + 1] [j + 1]のコストを計算しますdeletedCost := v0 [ j + 1 ] + 1 insertCost : = v1 [ j ] + 1 if s [ i ] = t [ j ] substitutionCost := v0 [ j ] else substitutionCost :=      
            
                  
                
               
                  
            
                  v0 [ j ]  +  1

            v1 [ j  +  1 ]  := 最小deleteCost  insertionCost  substitutionCost 

        //次の反復のためにv1(現在の行)をv0(前の行)にコピーします// v1のデータは常に無効になるため、コピーなしのスワップは
        v1とv0をより効率的にスワップできます
        //最後のスワップの後、v1の結果現在v0にありますreturnv0 [ n ]   
    
     


Hirschbergのアルゴリズムは、この方法を分割統治法と組み合わせています。同じ漸近的な時間と空間の境界で、編集距離だけでなく、最適な編集シーケンスを計算できます。[6]

Automata

Levenshtein automataは、文字列の編集距離が特定の文字列からの特定の定数よりも小さいかどうかを効率的に判断します。[7]

近似

長さnの2つのストリング間のレーベンシュタイン距離は、1倍以内 に概算できます。

ここで、ε > 0は、時間On 1 + εで調整される自由パラメーターです。[8]

計算の複雑さ

長さnの2つのストリングのレーベンシュタイン距離は、強い指数時間仮説が偽でない限り、ゼロより大きい任意のεの時間On 2 −εで計算できないことが示されています。[9]

も参照してください

参考文献

  1. ^ Â。И。Левенштейн(1965)。Двоичныекодысисправлениемвыпадений、вставокизамещенийсимволов[削除、挿入、および取り消しを修正できるバイナリコード]。ДокладыАкадемииНаукСССР(ロシア語)。163(4):845–848。英語で次のように表示されます:Levenshtein、Vladimir I.(1966年2月)。「削除、挿入、および取り消しを修正できるバイナリコード」。ソビエト物理学Doklady10(8):707–710。Bibcode1966SPhD ... 10..707L
  2. ^ Navarro、ゴンザロ(2001)。「文字列マッチングを概算するためのガイド付きツアー」(PDF)ACMコンピューティング調査33(1):31–88。CiteSeerX10.1.1.452.6317_ 土井10.1145 /375360.375365S2CID207551224_   
  3. ^ Jan D. ten Thije; Ludger Zeevaert(2007年1月1日)、受容的多言語主義:言語分析、言語ポリシー、および教訓的概念、John Benjamins Publishing Company、ISBN 978-90-272-1926-8了解度が言語間距離に反比例すると仮定すると...内容語同族語の割合(直接または同義語を介して)...語彙の関連性...文法の関連性{{citation}}: CS1 maint: date and year (link)
  4. ^ ワグナー、ロバートA。; Fischer、Michael J.(1974)、「The String-to-String Correction Problem」、Journal of the ACM21(1):168–173、doi10.1145 / 321796.321811S2CID 13381535 
  5. ^ Hjelmqvist、Sten(2012年3月26日)、高速でメモリ効率の高いレーベンシュタインアルゴリズム
  6. ^ Hirschberg、DS(1975)。「最大共通サブシーケンスを計算するための線形空間アルゴリズム」(PDF)ACMのコミュニケーション(投稿原稿)。18(6):341–343。CiteSeerX10.1.1.348.4774_ 土井10.1145 /360825.360861MR0375829_ S2CID207694727_    
  7. ^ Schulz、Klaus U。; ミホフ、ストヤン(2002)。「Levenshtein-Automataによる高速文字列修正」。文書分析と認識の国際ジャーナル5(1):67–85。CiteSeerX10.1.1.16.652_ 土井10.1007 / s10032-002-0082-8S2CID207046453_  
  8. ^ アンドニ、アレクサンドル; クラウトゲーマー、ロバート; Onak、Krzysztof(2010)。編集距離と非対称クエリの複雑さの多対数近似IEEE症状。コンピュータサイエンスの基礎(FOCS)。arXiv1005.4033Bibcode2010arXiv1005.4033ACiteSeerX10.1.1.208.2079_ 
  9. ^ Backurs、Arturs; Indyk、Piotr(2015)。編集距離は、非常に準二次的な時間では計算できません(SETHがfalseでない限り)コンピューティング理論に関するシンポジウム(STOC)に関する第47回年次ACM。arXiv1412.0348Bibcode2014arXiv1412.0348B

外部リンク