近似文字列マッチング

コンピュータ サイエンスにおいて、近似文字列マッチング(口語ではファジー文字列検索と呼ばれることが多い) は、パターンに近似的に (正確にではなく)一致する文字列を検索する手法です 。近似文字列マッチングの問題は、通常、指定された文字列内の近似部分文字列一致の検索と、パターンに近似的に一致する辞書文字列の検索という 2 つのサブ問題に分けられます。

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

• 挿入: cot → co a t
• 削除: co a t → cot
• 置換: co a t → co s t

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

• 挿入: co * t → co a t
• 削除: co a t → co * t
• 置換: co a t → co s t

いくつかの近似マッチングでは、文字列内の2つの文字の位置を入れ替える転置を基本的な操作として扱います。^[1]

• 転置: co st → co ts

近似マッチャーによって、課される制約が異なります。マッチャーの中には、単一のグローバルな重み付けされていないコスト、つまり、一致をパターンに変換するために必要な基本操作の合計数を使用するものもあります。たとえば、パターンがcoilの場合、foil は1 つの置換、coils は1 つの挿入、oilは 1 つの削除、foal は2 つの置換が異なります。すべての操作が 1 つのコスト単位としてカウントされ、制限が 1 に設定されている場合、foil、coils、およびoil は一致としてカウントされますが、foal はカウントされません。

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

近似文字列マッチング問題の定義の 1 つは次のとおりです。パターン文字列とテキスト文字列が与えられた場合、T内のすべての部分文字列の中で、パターンPへの編集距離が最小となるT内の部分文字列を検索します。 ${\displaystyle P=p_{1}p_{2}...p_{m}}$${\displaystyle T=t_{1}t_{2}\dots t_{n}}$${\displaystyle T_{j',j}=t_{j'}\dots t_{j}}$

ブルートフォースアプローチは、T のすべての部分文字列について P への編集距離を計算し、距離が最小の部分文字列を選択することです。ただし、このアルゴリズムの実行時間はO ( n ³  m ) になります。

^{Sellers [2]}が提案したより良い解決策は、動的計画法に依存しています。これは、問題の別の定式化を使用します。テキストTの各位置jとパターンPの各位置iについて、パターンの最初のi文字と、位置jで終わるTの任意の部分文字列との間の最小編集距離を計算します。 ${\displaystyle P_{i}}$${\displaystyle T_{j',j}}$

テキストTの各位置jとパターンPの各位置iについて、位置jで終わるTのすべての部分文字列を調べ、パターンPの最初のi文字への編集距離が最小となる部分文字列を特定します。この最小距離をE ( i ,  j ) と書きます。すべてのiとjについてE ( i ,  j ) を計算すると、元の問題の解が簡単に見つかります。つまり、E ( m ,  j ) が最小となる部分文字列です ( mはパターンPの長さ)。

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

E ( x ,  y ) 値を含む配列で、最後の行の最小値( E ( x ₂ ,  y _{2 )} ) を選択し、計算パスを逆方向にたどって行番号 0 に戻ります。到達したフィールドがE (0,  y ₁ ) の場合、T [ y ₁  + 1] ...  T [ y _{2 ] は、パターン}Pへの編集距離が最小である T の部分文字列です。

動的計画法アルゴリズムでは、 E ( x ,  y )配列の計算にはO ( mn )時間がかかり、逆方向の作業フェーズにはO ( n  +  m )時間がかかります。

もう一つの最近のアイデアは類似性結合です。マッチング データベースが大規模なデータに関係する場合、動的プログラミング アルゴリズムを使用したO ( mn ) 時間は限られた時間内では機能しません。そのため、すべての文字列ペアの類似性を計算するのではなく、候補ペアの数を減らすというアイデアです。広く使用されているアルゴリズムは、フィルター検証、ハッシュ、局所性に敏感なハッシュ(LSH)、トライ、その他の貪欲アルゴリズムと近似アルゴリズムに基づいています。それらのほとんどは、並列計算を行うために何らかのフレームワーク (Map-Reduce など) に適合するように設計されています。

従来、近似文字列マッチングアルゴリズムは、オンラインとオフラインの2つのカテゴリに分類されます。オンラインアルゴリズムでは、検索前にパターンを処理できますが、テキストは処理できません。言い換えると、オンライン手法ではインデックスなしで検索を行います。オンライン近似マッチングの初期のアルゴリズムは、WagnerとFischer ^[3]とSellers ^{[2]によって提案されました。両方のアルゴリズムは}動的プログラミングに基づいています が、異なる問題を解決します。Sellersのアルゴリズムはテキスト内の部分文字列を近似的に検索しますが、WagnerとFischerのアルゴリズムはレーベンシュタイン距離を計算し、辞書のあいまい検索にのみ適しています。

オンライン検索技術は繰り返し改良されてきました。おそらく最も有名な改良は、比較的短いパターン文字列に非常に効率的なビットタップアルゴリズム（シフトORアルゴリズムやシフトANDアルゴリズムとも呼ばれます）です。ビットタップアルゴリズムは、 Unix検索ユーティリティ agrepの核心です。オンライン検索アルゴリズムのレビューは、G. Navarroによって行われました。^[4]

非常に高速なオンライン技術は存在するが、大規模データに対するそのパフォーマンスは好ましくない。テキストの前処理またはインデックス作成により、検索が劇的に高速化される。今日、さまざまなインデックス作成アルゴリズムが発表されている。その中には、サフィックスツリー、^[5]、 メトリックツリー^[6]、およびnグラム法[7 ^]がある。^[8] テキスト内の任意の部分文字列を見つけることができるインデックス作成技術の詳細な調査は、Navarroらによって行われている。^[7]辞書法（つまり、検索パターンにほぼ一致するすべての辞書の単語を見つけることができる方法）の計算調査は、Boytsovによって行われている。^[9]

近似マッチングの一般的な用途としては、スペルチェックが挙げられる。^[5]大量のDNAデータが利用可能になったことで、ヌクレオチド配列のマッチングは重要な用途となった。^{[1]近似マッチングは}スパムフィルタリングにも使用されている。^[5] レコードリンケージは、2つの異なるデータベースのレコードをマッチングさせる一般的な用途である。

文字列マッチングは、画像や音楽などのほとんどのバイナリ データには使用できません。これらのデータには、音響フィンガープリントなどの別のアルゴリズムが必要です。

一般的なコマンドラインツールfzfは、近似文字列検索をさまざまなコマンドラインアプリケーションに統合するためによく使用されます。^[10]

• フラミンゴプロジェクト
• 編集距離しきい値に基づく近似文字列マッチングの最近の進歩を活用した効率的な類似性クエリ処理プロジェクト。
• StringMetric プロジェクトは、文字列メトリックと音声アルゴリズムのScalaライブラリです。
• Naturalプロジェクトは、一般的な文字列メトリックの実装を含むJavaScriptの自然言語処理ライブラリです。