ダメラウ・レーベンシュタイン距離

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

情報理論コンピューターサイエンスではダメラウ・レーベンシュタイン距離(フレデリックJ.ダメラウウラジミールI.レベンシュテイン[1] [2] [3]にちなんで名付けられました)は、 2つのシーケンス間の編集距離を測定するための文字列メトリックです。非公式には、2つの単語間のダメラウ・レーベンシュタイン距離は、1つの単語を別の単語に変更するために必要な操作(1つの文字の挿入、削除、置換、または2つの隣接する文字の 転置で構成される)の最小数です。

ダメラウ・レーベンシュタイン距離は、3つの古典的な単一文字編集操作(挿入、削除、および置換)に加えて、許容される操作の中に転置を含めることにより、古典的なレーベンシュタイン距離とは異なります。[4] [2]

彼の独創的な論文[5]で、Damerauは、情報検索システムのスペルミスの調査で、80%以上が4つのタイプのうちの1つの単一のエラーの結果であると述べました。Damerauの論文は、多くても1回の編集操作で修正できるスペルミスのみを考慮していました。当初の動機は、スペルチェッカーなどのアプリケーションを改善するために人間のスペルミス間の距離を測定することでしたが、ダメラウ・レーベンシュタイン距離は、タンパク質配列間の変動を測定するための生物学での使用も見られました。[6]

定義

2本の弦の間のダメラウ・レーベンシュタイン距離を表現するには、 機能が定義され、その値は-文字列の記号プレフィックス(最初のサブ文字列)-の記号プレフィックス

制限付き距離関数は、再帰的に次のように定義されます。 [7] :A:11 

どこ0に等しいインジケーター関数ですそれ以外の場合は1に等しくなります。

各再帰呼び出しは、ダメラウ・レーベンシュタイン距離でカバーされるケースの1つと一致します。

  • 削除(aからbへ)に対応し、
  • 挿入(aからb)に対応し、
  • それぞれの記号が同じであるかどうかに応じて、一致または不一致に対応します。
  • 2つの連続するシンボル間の転置に対応します。

次に、 abの間のダメラウレーベンシュタイン距離は、完全な文字列の関数値によって与えられます。、 どこ文字列aの長さを示しbの長さです。

アルゴリズム

ここでは、2つのアルゴリズムを示します。1つ目は[8]単純なもので、最適な文字列位置合わせ距離または制限付き編集距離として知られているものを計算します[7]。2つ目は[9]隣接する転置を伴うダメラウ・レーベンシュタイン距離を計算します。転置を追加すると、かなり複雑になります。2つのアルゴリズムの違いは、最適な文字列整列アルゴリズムが、サブストリングが2回以上編集されないという条件下で文字列を等しくするために必要な編集操作の数を計算するのに対し、2番目のアルゴリズムにはそのような制限がないことです。

たとえば、CAABCの間の編集距離を考えてみましょう。ダメラウ・レーベンシュタイン距離LD(CA、  ABC)= 2 ( CAACABC)であるが、最適な文字列整列距離OSA(CA、  ABC)= 3(操作CAACを使用すると使用できないため)ACABCは、サブストリングを複数回編集する必要があるためです。これはOSAでは許可されていないため、最短の操作シーケンスはCAAAB →です。ABC最適な文字列の位置合わせ距離の場合、三角不等式は成り立たないことに注意してください:OSA(CA、  AC)+ OSA(AC、  ABC)<OSA(CA、  ABC)、したがって、これは真のメトリックではありません。

最適な文字列の位置合わせ距離

最適な文字列の位置合わせ距離は、レーベンシュタイン距離を計算するWagner–Fischer 動的計画法アルゴリズムの単純な拡張を使用して計算できます擬似コード

アルゴリズムOSA-距離
    入力されます:文字列a [1..length(a)]、b [1..length(b)]
    出力:距離、整数
    
    d [0..length(a)、0..length(b)]を整数の2次元配列、次元length(a)+1、length(b)+1
     //dがゼロであることに注意してください-インデックスが付けられ、aとbは1つのインデックスが付けられます。
    
    for i:= 0からlength(a まで 
        d [i、0]:= i
    jの場合:= 0からlength(b)まで 
        d [0、j]:= j
    
    for i:= 1からlength(a)まで do 
        for j:= 1からlength(b)まで do 
            if a [i] = b [j] then
                コスト:= 0
            そうしないと
                コスト:= 1
            d [i、j]:= minimum(d [i-1、j] + 1、      //削除
                               d [i、j-1] + 1、      //挿入
                               d [i-1、j-1]+コスト)   //
             i>1かつj>1かつa[i]=b[j-1]かつa[i-1]=b[j]の場合の置換
                d [i、j]:= minimum(d [i、j]、
                                   d [i-2、j-2] + 1)   //転置
    return d [length(a)、length(b)]

レーベンシュタイン距離のアルゴリズムとの違いは、1回の繰り返しの追加です。

i>1かつj>1かつa[i]= b [j-1]かつa[i-1]= b [j]の場合、
    d [i、j]:= minimum(d [i、j]、
                       d [i-2、j-2] + 1)   //転置

隣接する転置との距離

次のアルゴリズムは、隣接する転置を使用して、真のダメラウ・レーベンシュタイン距離を計算します。このアルゴリズムでは、追加のパラメーターとしてアルファベットΣのサイズが必要であるため、配列のすべてのエントリは[0、|Σ|)[7] :A:93に なります。

アルゴリズムDL-距離
    入力されます:文字列a [1..length(a)]、b [1..length(b)]
    出力:距離、整数
    
    da:=|Σ|の新しい配列 整数
    for i:=1から|Σ| 包括 
        da [i]:= 0
    
    d [-1..length(a)、-1..length(b)]を整数の2次元配列、次元length(a)+2、length(b)+2
     //dが-1で始まるインデックス、a、b、daは1つのインデックスです。
    
    maxdist:=長さ(a)+長さ(b)
    d [-1、-1]:= maxdist
    for i:= 0からlength(a まで 
        d [i、-1]:= maxdist
        d [i、0]:= i
    jの場合:= 0からlength(b)まで 
        d [-1、j]:= maxdist
        d [0、j]:= j
    
    for i:= 1からlength(a まで 
        db:= 0
        jの場合:= 1からlength(b)まで 
            k:= da [b [j]]
            ℓ:= db
            a [i] = b [j]の場合
                コスト:= 0
                db:= j
            そうしないと
                コスト:= 1
            d [i、j]:= minimum(d [i-1、j-1] +コスト、   //置換
                               d [i、j-1] + 1、      //挿入
                               d [i-1、j] + 1 、      //削除
                               d [k-1、ℓ-1] +(i-k-1)+ 1 +(j-ℓ-1))//転置
        da [a [i]]:= i
    d [length(a)、length(b)]を
返します

無制限のダメラウ・レーベンシュタイン距離を計算するための適切なアルゴリズムを考案するために、一度転置された文字が後で変更されることのない、編集操作の最適なシーケンスが常に存在することに注意してください。(これは、転置のコストがかかる限り保持されます、、は、少なくとも挿入と削除のコストの平均です。[9])したがって、部分文字列を複数回変更する2つの対称的な方法のみを考慮する必要があります。(1)文字を転置してそれらの間に任意の数の文字を挿入するか、(2)文字のシーケンスを削除して文字を転置します。削除後に隣接するようになります。このアイデアの簡単な実装は、3次の複雑さのアルゴリズムを提供します。、ここで、MNは文字列の長さです。LowranceとWagnerのアイデアを使用して、[9]この素朴なアルゴリズムを改善して次のようにすることができます。最悪の場合、これは上記の擬似コードが行うことです。

転置を処理するようにbitapアルゴリズムを変更できるのは興味深いことです。このような適応の例については、 [1]の情報検索セクションを参照してください。

アプリケーション

ダメラウ・レーベンシュタイン距離は、自然言語処理において重要な役割を果たします自然言語では、文字列が短く、エラー(スペルミス)の数が2を超えることはめったにありません。このような状況では、制限された編集距離と実際の編集距離が異なることはほとんどありません。Oommen and Loke [8]は、一般化された転置を導入することにより、制限された編集距離の制限を緩和しましたそれでも、制限された編集距離は通常、三角不等式を満たさないため、メトリックツリーでは使用できないことを覚えておく必要があります

DNA

DNAは頻繁に挿入、削除、置換、および転置を受け、これらの各操作はほぼ同じタイムスケールで行われるため、ダメラウ・レーベンシュタイン距離はDNAの2本の鎖間の変動の適切な測定基準ですDNA、タンパク質、およびその他のバイオインフォマティクス関連のアライメントタスクでより一般的なのは、 Needleman-WunschアルゴリズムSmith-Watermanアルゴリズムなどの密接に関連するアルゴリズムの使用です

不正検出

このアルゴリズムは、ベンダー名など、任意の単語セットで使用できます。エントリーは本質的に手動で行われるため、誤ったベンダーにエントリーするリスクがあります。詐欺師の従業員は、「Rich Heir EstateServices」などの1つの実際のベンダーと、偽のベンダー「RichHierStateServices」を入力する場合があります。次に、詐欺師は偽の銀行口座を作成し、会社に実際のベンダーと偽のベンダーへの小切手をルーティングさせます。ダメラウ・レーベンシュタインアルゴリズムは、転置およびドロップされた文字を検出し、不正検査士にアイテムの注意を促します。

輸出管理

米国政府は、統合スクリーニングリストAPIでダメラウレーベンシュタイン距離を使用しています。[10]

も参照してください

参照

  1. ^ ブリル、エリック; ムーア、ロバートC.(2000)。ノイズの多いチャネルスペル修正の改善されたエラーモデル (PDF)計算言語学会第38回年次総会の議事録。pp。286–293。土井10.3115/1075218.10752552012年12月21日にオリジナル (PDF)からアーカイブされました
  2. ^ a b Bard、Gregory V.(2007)、「ダメラウ・レーベンシュタイン文字列編集距離計量によるスペルエラー耐性、順序に依存しないパスフレーズ」、ACSWフロンティアに関する第5回オーストラリアシンポジウムの議事録:2007、バララット、オーストラリア、2007年1月30日から2月2日、情報技術の研究と実践における会議、vol。68、オーストラリア、ダーリングハースト:Australian Computer Society、Inc.、pp。117–124、ISBN 978-1-920682-49-1
  3. ^ 李; etal。(2006)。クエリのスペル修正のための分布類似性ベースのモデルの調査(PDF)計算言語学に関する第21回国際会議および計算言語学会の第44回年次総会の議事録。pp。1025-1032。土井10.3115/1220175.12203042010年4月1日にオリジナル(PDF)からアーカイブされました
  4. ^ Levenshtein、Vladimir I.(1966年2月)、「削除、挿入、および反転を修正できるバイナリコード」、Soviet Physics Doklady10(8):707–710、Bibcode1966SPhD ... 10..707L
  5. ^ Damerau、Fred J.(1964年3月)、「コンピューターによるスペルミスの検出と訂正の手法」、Communications of the ACM7(3):171–176、doi10.1145 / 363958.363994S2CID 7713345 
  6. ^ 使用される方法: Majorek、Karolina A .; Dunin-Horkawicz、Stanisław; etal。(2013)、「RNase Hのようなスーパーファミリー:新しいメンバー、比較構造解析および進化的分類」、Nucleic Acids Research42(7):4160–4179、doi10.1093 / nar / gkt1414PMC 3985635PMID 24464998  
  7. ^ a b c Boytsov、Leonid(2011年5月)。「おおよその辞書検索のための索引付け方法」。Journal ofExperimentalAlgorithmics161。doi10.1145/1963190.1963191S2CID15635688_ 
  8. ^ a b Oommen、BJ; Loke、RKS(1997)。「置換、挿入、削除、および一般化された転置を伴う文字列のパターン認識」。パターン認識30(5):789–800。Bibcode1997PatRe..30..789OCiteSeerX10.1.1.50.1459_ 土井10.1016 / S0031-3203(96)00101-X 
  9. ^ a b c Lowrance、Roy; ワグナー、ロバートA.(1975年4月)、「文字列から文字列への修正問題の拡張」、J ACM22(2):177–183、doi10.1145 / 321879.321880S2CID 18892193 
  10. ^ 「統合されたスクリーニングリストAPI」Trade.gov開発者ポータル米国商務省国際貿易局。2019-10-30にオリジナルからアーカイブされました。

さらに読む