近似文字列マッチング

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
「怒りの絵文字」のあいまいなMediawiki検索は、提案された結果として「andréemotions」を持っています

コンピュータサイエンスでは近似文字列マッチング(あいまい文字列検索と呼ばれることが多い)は、パターンにほぼ(正確にではなく)一致する文字列を見つける手法です 。近似文字列マッチングの問題は、通常、2つのサブ問題に分けられます。特定の文字列内で近似サブストリング一致を見つけることと、パターンに近似的に一致する辞書文字列を見つけることです。

概要

一致の近さは、文字列を完全一致に変換するために必要なプリミティブ操作の数で測定されます。この数値は、弦とパターンの間の編集距離と呼ばれます。通常の基本的な操作は次のとおりです。[1]

  • 挿入:cotco a t
  • 削除 co atcot
  • 置換co atcost _ _

これらの3つの操作は、文字が削除または挿入された場所にNULL文字(ここでは*で表されます)を追加することにより、置換の形式として一般化できます。

  • 挿入co * tcoa t
  • 削除 co atco * t
  • 置換 co atcost _ _

一部の近似マッチャーは、文字列内の2文字の位置が入れ替わる転置をプリミティブ演算として扱います。[2]

  • 移調 costcots _

近似マッチャーが異なれば、制約も異なります。一部のマッチャーは、単一のグローバルな重み付けされていないコスト、つまり、一致をパターンに変換するために必要なプリミティブ操作の総数を使用します。たとえば、パターンがコイルの場合、ホイルは1回の置換で、コイルは1回の挿入で、オイルは1回の削除で、子馬は2回の置換で異なります。すべての操作が単一のコスト単位としてカウントされ、制限が1に設定されている場合、フォイルコイル、およびオイルは一致としてカウントされますが、子馬はカウントされません。

他のマッチャーは各タイプの操作の数を個別に指定しますが、他のマッチャーは合計コストを設定しますが、異なる操作に異なる重みを割り当てることができます。一部のマッチャーでは、パターン内の個々のグループに制限と重みを個別に割り当てることができます。

問題の定式化とアルゴリズム

近似文字列マッチング問題の考えられる定義の1つは、次のとおりです。パターン文字列が与えられた場合およびテキスト文字列、部分文字列を検索しますTのすべてのサブストリングの中で、パターンPまでの編集距離が最小です

ブルートフォースアプローチは、TのすべてのサブストリングについてPまでの編集距離を計算し、最小距離のサブストリングを選択することです。ただし、このアルゴリズムの実行時間はOn 3  m)になります。

売り手によって提案されたより良い解決策[3]は、動的計画法に依存していますこれは、問題の代替定式化を使用します。テキストTの各位置jとパターンPの各位置iについて、パターンの最初のi文字間の最小編集距離を計算します。、および任意の部分文字列位置jで終了するT

テキストTの各位置j 、およびパターンPの各位置iについて、位置jで終わるTのすべての部分文字列を調べ、パターンPの最初のi文字までの編集距離が最小であるものを判別します。この最小距離をEi、  j)と書きます。すべてのijについてEi、  j )を計算した後、元の問題の解決策を簡単に見つけることができます。これは、Em、  j)は最小です(mはパターンPの長さです)。

Em、  j )の計算は、2つの文字列間の編集距離の計算と非常によく似ています。実際、Em、  j )にレーベンシュタイン距離計算アルゴリズムを使用できます。唯一の違いは、最初の行をゼロで初期化し、計算パスを保存する必要があることです。つまり、Ei  − 1、j)、E(ij  − 1)またはEi  − 1、j − 1) Ei、  j ) の計算

Ex、  y )値を含む配列で、最後の行の最小値を選択し、それをEx 2、  y 2)とし、計算パスを逆方向にたどって行番号0に戻ります。到達したフィールドがE(0、  y 1)の場合、T [ y 1  + 1] ...  T [ y 2 ]は、パターンPまでの編集距離が最小のTのサブストリングです

Ex、  y)配列の計算には、動的計画法アルゴリズムでOmn )時間がかかりますが、逆方向作業フェーズにはOn  +  m)時間がかかります。

もう1つの最近のアイデアは、相似結合です。マッチングデータベースが大規模なデータに関連している場合、動的計画法アルゴリズムを使用したOmn)時間は、限られた時間内では機能しません。したがって、文字列のすべてのペアの類似性を計算するのではなく、候補ペアの数を減らすという考え方です。広く使用されているアルゴリズムは、フィルター検証、ハッシュ、局所性鋭敏型ハッシュ(LSH)、試行、およびその他の欲張りおよび近似アルゴリズムに基づいています。それらのほとんどは、同時に計算するためのフレームワーク(Map-Reduceなど)に適合するように設計されています。

オンライン対オフライン

従来、近似文字列マッチングアルゴリズムは、オンラインとオフラインの2つのカテゴリに分類されていました。オンラインアルゴリズムを使用すると、検索前にパターンを処理できますが、テキストは処理できません。言い換えれば、オンライン技術はインデックスなしで検索を行います。オンライン近似マッチングの初期のアルゴリズムは、WagnerとFisher [4]およびSellers [5]によって提案されました。どちらのアルゴリズムも動的計画法に基づいています が、さまざまな問題を解決します。売り手のアルゴリズムはテキスト内の部分文字列をほぼ検索しますが、WagnerとFisherのアルゴリズムはレーベンシュタイン距離を計算します。これは辞書のあいまい検索にのみ適しています。

オンライン検索技術は繰り返し改善されてきました。おそらく最も有名な改善点は、比較的短いパターン文字列に対して非常に効率的なbitapアルゴリズム(shift-orおよびshift-andアルゴリズムとも呼ばれます)です。 Bitapアルゴリズムは、Unix検索ユーティリティ agrepの心臓部です。オンライン検索アルゴリズムのレビューは、G。Navarroによって行われました。[6]

非常に高速なオンライン技術が存在しますが、大規模なデータでのパフォーマンスは許容できません。テキストの前処理または索引付けにより、検索が劇的に高速化されます。今日、さまざまな索引付けアルゴリズムが提示されています。その中には、接尾辞木[7]メトリックツリー[8]、およびn-gramメソッドがあります。[9] [10] テキスト内の任意の部分文字列を見つけることができる索引付け手法の詳細な調査は、Navarro etal。によって提供されています。[11]辞書メソッド(つまり、検索パターンにほぼ一致するすべての辞書単語を検索できるメソッド)の計算調査は、Boytsov [12]によって提供されています。

アプリケーション

近似一致の一般的なアプリケーションには、スペルチェックが含まれます。[13]大量のDNAデータが利用できるようになったことで、ヌクレオチド配列のマッチングが重要なアプリケーションになりました。[14]近似一致は、スパムフィルタリングでも使用されます。[15] レコードリンケージは、2つの異なるデータベースからのレコードが照合される一般的なアプリケーションです。

文字列照合は、画像や音楽など、ほとんどのバイナリデータには使用できません。それらには、音響指紋などのさまざまなアルゴリズムが必要です

も参照してください

参考文献

  • ^ Baeza-Yates、R。; Navarro、G。(1996年6月)。「近似文字列マッチングのためのより高速なアルゴリズム」。ダンヒルチスバーグでは; ジーンマイヤーズ(編)。コンビナトリアルパターンマッチング(CPM'96)、LNCS1075カリフォルニア州アーバイン。pp。1–23。CiteSeerX10.1.1.42.1593  _
  • ^ Baeza-Yates、R。; Navarro、G。「辞書での高速近似文字列マッチング」(PDF)Proc。SPIRE'98IEEECSプレス。pp。14–22。
  • ^ Boytsov、Leonid(2011)。「近似辞書検索のための索引付け方法:比較分析」。Journal of ExperimentalAlgorithmics16(1):1–91。土井 10.1145 /1963190.1963191S2CID15635688 _ 
  • ^ コルメン、トーマス; Leiserson、Rivest(2001)。アルゴリズム入門(第2版)。MITプレス。pp。364–7。ISBN 978-0-262-03293-3
  • ^ ガリル、ツヴィ; アポストリコ、アルベルト(1997)。パターンマッチングアルゴリズムオックスフォード[オックスフォードシャー]:オックスフォード大学出版局。ISBN 978-0-19-511367-9
  • ^ ガスフィールド、ダン(1997)。文字列、ツリー、およびシーケンスのアルゴリズム:コンピューターサイエンスと計算生物学英国ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-58519-4
  • ^ Myers、G。(1999年5月)。「動的計画法に基づく近似文字列マッチングのための高速ビットベクトルアルゴリズム」(PDF)ACMのジャーナル46(3):395–415。土井 10.1145 /316542.316550S2CID1158099 _  
  • ^ Navarro、ゴンザロ(2001)。「文字列マッチングを概算するためのガイド付きツアー」。ACMコンピューティング調査33(1):31–88。CiteSeerX10.1.1.96.7225 _ 土井 10.1145 /375360.375365S2CID207551224 _  
  • ^ Navarro、ゴンザロ; Baeza-Yates、リカルド; Sutinen、Erkki; Tarhio、Jorma(2001)。「近似文字列マッチングのためのインデックス作成方法」(PDF)IEEEデータエンジニアリング速報24(4):19–27。
  • ^ 売り手、ピーターH.(1980)。「進化的距離の理論と計算:パターン認識」。Journal ofAlgorithms1(4):359–73。土井 10.1016 / 0196-6774(80)90016-4
  • ^ スキーナ、スティーブ(1998)。アルゴリズム設計マニュアル(第1版)。スプリンガー。ISBN 978-0-387-94860-7
  • ^ Ukkonen、E。(1985)。「近似文字列マッチングのアルゴリズム」情報と管理64(1–3):100–18。土井 10.1016 / S0019-9958(85)80046-2
  • ^ ワーグナー、R。; フィッシャー、M。(1974)。「文字列間の修正の問題」。ACMのジャーナル21:168–73。土井 10.1145 /321796.321811S2CID13381535 _ 
  • ^ ゾーベル、ジャスティン; ダート、フィリップ(1995)。「大きな辞書でおおよその一致を見つける」。ソフトウェア:実践と経験25(3):331–345。CiteSeerX10.1.1.14.3856 _ 土井 10.1002 /spe.4380250307S2CID6776819 _  

外部リンク