一致するワイルドカード

コンピュータサイエンスでは、ワイルドカードのマッチングアルゴリズム（グロビングとも呼ばれる）は、ワイルドカード構文を含む可能性のあるテキスト文字列の比較に役立ちます。^[1]これらのアルゴリズムの一般的な用途には、Bourneシェル^[2]やMicrosoft Windowsコマンドライン^[3]などのコマンドラインインターフェイス、テキストエディターやファイルマネージャー、一部の検索エンジン^[4]やデータベースのインターフェイスなどがあります。^[5]ワイルドカードマッチングは、一般的な正規表現のマッチングと文字列のマッチングの問題のサブセットです。 ^[6]

ワイルドカード マッチャーは、ワイルドカード パターンp を入力文字列sに対してテストします。アンカーマッチを実行し、 p がs全体に一致する場合にのみ true を返します。

パターンは一般的な構文（グロブを参照）に基づいて作成できますが、WindowsプログラマーはネイティブCランタイムでサポートされている簡略化された構文のみを議論する傾向があります。^{[7] [8]}

• エスケープ文字が定義されていません
• ワイルドカード:?任意の文字の 1 つの出現と一致します。*任意の文字の任意の複数回 (0 を含む) の出現と一致します。

特に明記しない限り、この記事では主に Windows の問題の定式化について説明します。

ゼロベースのインデックスで表現すると、ワイルドカード マッチング問題は次のように再帰的に定義できます。

${\displaystyle {\begin{aligned}m_{00}&=(p_{0}=t_{0})\\m_{0j}&=(p_{j-1}={\text{'*'}})\land m_{0,j-1}\\m_{i0}&={\text{false}}\\m_{ij}&={\begin{cases}m_{i-1,j-1}&{\text{for}}\;p_{i-1}=t_{j-1}\lor p_{i-1}={\text{'?'}}\\m_{i,j-1}\lor m_{i-1,j}&{\text{for}}\;p_{i-1}={\text{'*'}}\\{\text{false}}&{\text{for}}\;p_{i-1}\neq t_{j-1}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq |p|、1\leq j\leq |t|.\end{aligned}}}$

ここで、m _{ij は}パターンpをi文字目とj文字目で切り捨てられたテキストtと照合した結果である。これは、リヒターのアルゴリズムとカンタトーレのコレクションにあるスニペットアルゴリズムで使用される定式化である。^{[9] [10]この説明は}レーベンシュタイン距離に似ている。

コンピュータ サイエンスにおける直接関連する問題には次のものがあります。

• ドントケアやギャップを含むパターンマッチング、?定義されたものと同等のもののみを含むアンカーなしの文字列検索。^{[11] [12]}
• ワイルドカードを使用したパターンマッチングは、両方のワイルドカードと同等のものが定義されたアンカーなしの文字列検索です。柔軟なワイルドカードを使用したパターンマッチングのバリアントで長さの制限が指定されていない限り、実行時間は指数関数的に長くなります。^[13]

ワイルドカードをマッチングする初期のアルゴリズムは、しばしば再帰に依存していましたが、この手法はパフォーマンス^[10]と信頼性^[8]の観点から批判されました。これらの考慮事項に照らして、ワイルドカードをマッチングする非再帰アルゴリズムが支持されるようになりました。

再帰アルゴリズムと非再帰アルゴリズムの両方において、パターン マッチング操作を実行するための戦略は大きく異なります。これは、以下に示すさまざまなアルゴリズムの例からも明らかです。テスト ケースの開発とパフォーマンスの最適化手法は、特定のアルゴリズム、特に再帰アルゴリズムの批評家によって開発されたアルゴリズムに明らかに影響を及ぼしています。

再帰は、通常、一致させるべき接尾辞がさらにある場合にマッチング時に発生します。これはバックトラック*の一種で、一部の正規表現マッチャーでも実行されます。

• Rich Salzのwildmatアルゴリズム (sh に似た構文) ^[14]
• Filip のアルゴリズム^[15]および Vignesh Murugesan のアルゴリズム^[16]
• マーティン・リヒターのアルゴリズム^[9]（スニペットと同一で、7-zipアルゴリズムに関連）^[17]
• C ライブラリfnmatch実装 ([...]マルチバイト文字セットをサポート):
  • Guido van RossumのBSD libc fnmatch ^[18] 、 Apple libc ^{[19]の一部でもある}
  • glibc fnmatch ^[20]

これらのアルゴリズムの一般的な形式は同じです。再帰では、アルゴリズムは入力を部分文字列に分割し、部分文字列の 1 つが正の一致を返す場合に一致が発生したと見なします。 の場合、貪欲に、、および をdowild("*X", "abcX")呼び出します。通常、機能のサポートなどの重要度の低い点と、小さいが非常に効果的な最適化などのより重要な要素が異なります。その一部を以下に示します。 dowild("X", "abcX")dowild("X", "bcX")dowild("X", "cX")dowild("X", "X")

• 過剰再帰に対する ABORT シグナル (Lars Mathiesen 1991)。残りの文字列 (パターンとテキスト) 全体を単純に再帰し*、サブ文字列の 1 つが確実に正の一致を返すようにするのは正しいのですが、テキストに多数の一致があるのを拒否するため、実行時間は指数関数的に増加します*。Lars Mathiesen は、戻り値を一致、不一致、ABORT (アスタリスク再帰では一致がまったくない) の 3 つのクラスに変更しました。テキストが早く消費されすぎた場合、または別のアスタリスク一致が失敗した場合に ABORT 値が返され、アスタリスクの数に対して線形のパフォーマンスが保証されます。(全体の複雑さは、一致するために残っている文字数の 2 乗になります。) ^[14] Git/Rsync の wildmatch ABORT も無効な入力をカバーします。^[21]新しい INN uwildmat も同じことを行います。^[22]
• 再帰におけるアスタリスクの進歩。このワイルドマッチの調整は比較的軽微です。これは、再帰が「*X」を「abcX」に一致させたい場合に当てはまります。アスタリスクの後に「X」のようなリテラルが続く場合、長さが同じ最後の比較のみが一致を生み出す可能性があることは明らかです。^[21]これは、2000年のuwildmat ^[22]で以前に見られ、より暗黙的にvan Rossumのfnmatchで見られますFNM_PATHNAME。

Martin Richter のアルゴリズムはこのパターンの例外ですが、全体的な操作は同等です。 * では、問題の動的プログラミング定式化に従って、いずれかのインデックスの増加に再帰します。「ABORT」テクニックも適用できます。 ^[9]一般的なパターンでは (Cantatore によってテストされたように)、貪欲呼び出し実装よりも遅くなります。^[10]

再帰アルゴリズムは一般に理解しやすく、ABORT の変更により、最悪の場合の複雑さの点でも許容できるパフォーマンスを発揮します。 * のない文字列では、1 対 1 の関係が固定されているため、一致には線形から文字列サイズまでの時間がかかります。

再帰アルゴリズムの批評家によって、次のものが開発されました。

• IBMが使用しているカーク・J・クラウスのワイルドカードマッチングアルゴリズム^{[8] [23]}
• アレッサンドロ・カンタトーレのワイルドカードマッチングアルゴリズム集^[10]
• Dogan Kurtの反復マッチャーと低速のNFAマッチャー。^[17]
• サイラーの誤ったアルゴリズム（失敗MATCH("da*da*da*", "daaadabadmanda")）^[24]

以下はそうではありません:

• ジャック・ハンディの誤ったアルゴリズム^[25]（失敗MATCH("*?", "xx")）

上記の反復関数は、パターン/テキストポインタの古いセットを保存し、一致が失敗した場合にそれに戻ることでバックトラッキングを実装します。Kurtによると、必要なのは1つの成功した一致だけなので、保存する必要があるセットは1つだけです。^[17]

さらに、ワイルドカードマッチングの問題は、単純なテキスト置換アプローチを使用して正規表現マッチングに変換できます。 Thompson の構築などの非再帰的な正規表現マッチャーは、後方参照のサポートがないため実際にはあまり使用されていませんが、ワイルドカードマッチングは一般に、同様の豊富な機能セットを備えていません。 (実際、上記のアルゴリズムの多くは、と のみをサポートしています。) Thompson NFA の Russ Cox 実装は、そのような用途に簡単に変更できます。^[26] Gustavo Navarro のBDMベースの nrgrep アルゴリズムは、効率的なサフィックスに重点を置いた、より合理化された実装を提供します。^[27]正規表現 § 実装も参照してください。 ?*

• パターンマッチング
• パターン計算
• Glob（プログラミング）
• ワイルドカード文字
• アルゴリズムのリスト