一致するワイルドカード

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

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

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

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

特に断りのない限り、この記事では主にWindowsにおける問題の定式化について論じる。

ワイルドカードのマッチングを行う初期のアルゴリズムは再帰に依存することが多かったが、この手法はパフォーマンス^{[ 10 ]}と信頼性^{[ 8 ]}の観点から批判された。これらの点を考慮すると、ワイルドカードのマッチングには非再帰アルゴリズムが好まれるようになった。

再帰アルゴリズムと非再帰アルゴリズムの両方において、パターンマッチング操作を実行するための戦略は多岐にわたり、以下に示す様々なアルゴリズムの例からもそれが明らかです。テストケース開発やパフォーマンス最適化の手法は、特に再帰アルゴリズムの批判者によって開発されたアルゴリズムにおいて、明らかに活用されています。

再帰処理は、マッチング対象となる接尾辞が複数存在する場合に一般的に発生します。これはバックトラッキング*の一種であり、一部の正規表現マッチングツールでも行われています。

• Rich Salzのwildmatアルゴリズム (sh に似た構文) ^{[ 14 ]}
• Filip のアルゴリズム^{[ 15 ]}および Vignesh Murugesan のアルゴリズム^{[ 16 ]}
• Martin Richterのアルゴリズム^{[ 9 ]}（Snippetsと同一で、7-zipアルゴリズムに関連している）^{[ 17 ]}
• Cライブラリのfnmatch実装（[...]マルチバイト文字セットのサポートを含む）：
  • Guido van Rossumの BSD libc fnmatch ^{[ 18 ]}はApple libc ^{[ 19 ]の一部でもある。}
  • Glibc fnmatch ^{[ 20 ]}

これらのアルゴリズムの一般的な形式は同じです。再帰処理では、アルゴリズムは入力を部分文字列に分割し、いずれかの部分文字列が肯定的な一致を返したときに一致が発生したとみなします。 の場合、 、、をdowild("*X", "abcX")貪欲に呼び出します。通常、機能のサポートなどの重要度の低い点と、マイナーながら非常に効果的な最適化などのより重要な点で異なります。それらのいくつかには、次のものがあります。dowild("X", "abcX")dowild("X", "bcX")dowild("X", "cX")dowild("X", "X")

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

Martin Richter のアルゴリズムは、全体的な操作は同等であるものの、このパターンの例外です。* の場合、問題の動的計画法の定式化に従って、いずれかのインデックスを増やすように再帰します。「ABORT」テクニックも適用可能です。^{[ 9 ]}典型的なパターン (Cantatore によるテスト) では、貪欲呼び出しの実装よりも遅くなります。^{[ 10 ]}

再帰アルゴリズムは一般的に理解しやすく、ABORT修正を加えることで、最悪の場合の計算量に関して許容できるパフォーマンスを発揮します。*を含まない文字列の場合、1対1の固定関係が存在するため、マッチングには文字列サイズに比例した時間がかかります。

再帰アルゴリズムの批判者によって、以下のような手法が開発されました。

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

以下は該当しません。

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

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

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

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