18

編集：すごい！?大きな承認です。私はパターン構文の定義を台無しにし、正規表現fnmatchのように動作するはるかに難しい問題を提案した（そしておそらく解決した）ようです。.?もちろん、実際には.正規表現のように動作するはずです（0または1ではなく、1文字に正確に一致します）。つまり、私の最初の問題削減作業は、（今ではかなり退屈な）元の問題を解決するのに十分だったことを意味します。しかし、より難しい問題を解決することは、まだかなり興味深いものです。私はいつかそれを書くかもしれません。

プラス面として、これは、2way / SMOAニードル因数分解のようなものがこれらのパターンに適用できる可能性がはるかに高いことを意味します。これにより、当初の望ましいパフォーマンスよりも優れたパフォーマンスが得られる可能性がありO(n)ますO(n/m)。

質問のタイトルでmは、パターン/針nの長さ、それに一致する文字列の長さとします。

私が見た/使用したすべてのアルゴリズムは、バックトラッキングが原因で病理学的に悪いパフォーマンスとスタックオーバーフローの悪用の可能性があるか、動的メモリ割り当てが必要なため（たとえば、DFAアプローチの場合、または呼び出しでバックトラックを実行しないようにする場合）、この質問は私にとって興味深いものですスタック）、したがって、プログラムがfnmatch何らかのアクセス権を付与/拒否するために使用している場合にも危険な可能性のある障害ケースがあります。

正規表現のマッチングにはそのようなアルゴリズムは存在しないと私は信じていますが、ファイル名パターン言語は正規表現よりもはるかに単純です。私はすでに問題を単純化して、パターンが*文字を使用していないと想定できるようにしました。この修正された問題では、文字列全体を照合するのではなく、文字列内のパターンの出現を検索します（部分文字列など）。一致の問題）。言語をさらに単純化して?文字を削除すると、言語は固定文字列と角かっこ式の連結で構成され、これはO(mn)時間とO（1）空間で簡単に一致させることができ、おそらく次のように改善できます。O(n)2wayおよびSMOAサブストリング検索で使用される針分解技術をそのようなブラケットパターンに拡張できるかどうか。ただし、単純にそれぞれが文字を消費する?かどうかにかかわらず試行を必要とし、パターン内の文字の数がどこにあるか?という時間係数をもたらします。2^qq?

この問題がすでに解決されているかどうか、またはそれを解決するためのアイデアを持っている人はいますか？

注：O（1）スペースの定義では、Transdichotomous_modelを使用しています。

注2：このサイトには、私が参照した2wayおよびSMOAアルゴリズムの詳細があります：http ：//www-igm.univ-mlv.fr/~lecroq/string/index.html

4

5 に答える 5

2

re2（Googleの）Russ Coxによる正規表現エンジンを調べましたか？

これは、決定性有限オートマトンに基づく正規表現マッチングエンジンであり、非決定性有限オートマトンをシミュレートするためにバックトラッキングを使用する通常の実装（Perl、PCRE）とは異なります。具体的な設計目標の1つは、あなたが言及した壊滅的なバックトラッキング動作を排除することでした。

検索パターンの後方参照など、一部のPerl拡張機能は許可されていませんが、globマッチングには必要ありません。

O(mn)時間とメモリの制約を具体的に保証するかどうかはわかりませんO(1)が、Googleコード検索サービスが存在している間に実行するのに十分でした。

少なくとも、内部を見て、それがどのように機能するかを確認するのはクールなはずです。Russ Coxは、1、2、3について3re2つの記事を書いていますが、コードはオープンソースです。re2

于 2012-04-27T08:22:17.757 に答える
1

編集：すごい！?大きな承認です。パターン構文の定義を台無しにして、正規表現fnmatchのように動作するというはるかに難しい問題を解決したようです。.?もちろん、実際には.正規表現のように動作するはずです（0または1ではなく、1文字に正確に一致します）。つまり、私の最初の問題削減作業は、（今ではかなり退屈な）元の問題を解決するのに十分だったことを意味します。しかし、より難しい問題を解決することは、まだかなり興味深いものです。私はいつかそれを書くかもしれません。

より難しい問題に対する可能な解決策は以下のとおりです。

O(log q)私は、空間での解決策と思われるもの（qパターン内の疑問符の数、したがってq< m）と、不確実ですが、指数関数よりも優れているように見える時間を計算しました。

まず、問題の軽減について簡単に説明します。まず、それぞれでパターンを破り*ます。これは、（おそらく長さがゼロの）初期コンポーネントと最終コンポーネント、および両側に.が隣接する多数の内部コンポーネントとして分解されます*。これは、最初/最後のコンポーネントが一致するかどうかを判断したら、内部一致に次のアルゴリズムを適用できることを意味します。最後のコンポーネントから始めて、最新のオフセットで始まる文字列で一致を検索します。これにより、最も可能性の高い「干し草の山」の文字が以前のコンポーネントと自由に一致するようになります。それらがすべて必要でない場合でも、問題はありません。*介入するという事実により、後で必要な数だけ破棄できるため、「もっと使用する」ことを試みることは有益ではありません。?最後のコンポーネントの「マーク」またはそれ以前のコンポーネントの検出。この手順は、すべてのコンポーネントに対して繰り返すことができます。ここでは、fnmatch式の「繰り返し演算子」*が一致するものだけであるという事実を強く利用していることに注意してください。 0回以上の文字の出現。同じ削減は正規表現では機能しません。

それが邪魔にならないように、私は単一のコンポーネントを効率的に一致させる方法を探し始めました。の時間係数を許可しているnので、文字列内のすべての可能な位置で試行を開始し、失敗した場合はあきらめて次の位置に移動しても問題ありません。これが私たちが取る一般的な手順です（ボイヤームーアのようなトリックはまだありません。おそらく後で持ち込むことができます）。

特定のコンポーネント（*リテラル文字、特定のセットの1文字に完全に一致する角かっこ、およびを?含む）の場合、一致する可能性のある最小および最大の長さの文字列があります。最小値は、すべての?文字を省略して角かっこ式を1文字として数える場合の長さであり、最大値は、文字を含める場合の長さです?。各位置で、パターンコンポーネントが一致する可能性のあるそれぞれの長さを試します。q+1これは、私たちが試験を行うことを意味します。以下の説明では、長さが固定されたままであると仮定します（これは、導入されようとしている再帰の外側の最も外側のループです）。これにより、この時点でパターンと比較する文字列からの長さ（文字数）も修正されます。

これが楽しい部分です。使用される/使用されない文字のすべての可能な組み合わせを繰り返したくあり?ません。イテレータは大きすぎて保存できません。だから私はごまかします。パターンコンポーネントを2つの「半分」Lとに分割します。それぞれに文字Rの半分が含まれています。次に、使用される文字数のすべての可能性（0から上記で固定された長さに基づいて使用される合計数まで）?を単純に繰り返し、使用される文字数も決定されます。これにより、照合しようとしている文字列が、patternおよびpatternと照合される部分に分割されます。?L?RLR

文字を含むパターンコンポーネントが特定の固定長文字列と一致するかどうかをチェックする問題を、文字を含むパターンコンポーネントが特定の小さい固定長文字列と一致q ?するかどうかをチェックする2つのインスタンスに減らしました。q/2 ?再帰を適用します。また、各ステップで関係する文字数が半分になるため?、再帰のレベル数はによって制限されlog qます。

于 2012-04-27T23:17:33.483 に答える
0

両方の文字列のハッシュを作成して、これらを比較できます。ハッシュ計算はO（m）で行われ、検索はO（m + n）で行われます。

このようなものを使用して、s[i]が文字である文字列のハッシュを計算できます。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

あなたが言ったように、これはファイル名のマッチングのためであり、文字列にワイルドカードがある場合はこれを使用できません。幸運を！

于 2012-04-27T07:37:19.357 に答える
0

これは不可能だと思います。

防弾の議論を提供することはできませんが、私の直感では?、アルゴリズムが何らかの意味で2つすべてを説明する必要がある場合、q = Theta（m）文字を含むパターンをいつでも構築できます。 ^qの可能性。これには、現在見ている可能性のどれを追跡するためにO（q）= O（m）スペースが必要になります。たとえば、NFAアルゴリズムはこのスペースを使用して、現在の状態のセットを追跡します。強引なバックトラッキングアプローチでは、スペースをスタックとして使用します（そして、負傷に侮辱を加えるために、スペースのO（q）に加えてO（2 ^ q）時間を使用します）。

于 2012-04-27T12:09:14.070 に答える
0

OK、これが私が問題を解決した方法です。

  1. パターンの最初の部分から最初の部分までを*文字列と照合してみてください。これが失敗した場合は、救済してください。成功した場合は、パターンと文字列の両方のこの最初の部分を破棄します。私たちはそれらで終わりました。（そして、を打つ前にパターンの終わりを打った*場合、文字列の終わりにも到達した場合は一致します。）

  2. パターンの最後までスキップします（最後の後のすべて。*パターンがで終わる場合は長さがゼロのパターンである可能性があります*）。それに一致するために必要な文字数を数え、文字列の末尾からその数の文字を調べます。それらが一致しない場合は、完了です。それらが一致する場合は、パターンと文字列のこのコンポーネントを破棄します。

  3. これで、（おそらく空の）サブパターンのシーケンスが残ります。これらのサブパターンはすべて、両側に*'sが隣接しています。文字列の残りの部分で順番に検索し、それぞれの最初の一致を取得して、一致するまで文字列の先頭を破棄してみます。この方法で各コンポーネントに一致するものが見つかった場合、パターン全体に一致するものがあります。コンポーネント検索が失敗すると、パターン全体が一致しなくなります。

このアルゴリズムには再帰がなく、文字列/パターンに有限数のオフセットしか格納されないため、二分法を超えたモデルではO（1）空間になります。ステップ1は時間的にO（m）、ステップ2は時間的にO（n + m）（または、入力文字列の長さがすでにわかっていると仮定するとO（m）ですが、C文字列と仮定します）、そしてステップ3は（単純な検索アルゴリズムを使用して）O（nm）です。したがって、アルゴリズム全体は時間的にO（nm）です。ステップ3をO（n）に改善することは可能かもしれませんが、私はまだ試していません。

最後に、元のより難しい問題はおそらく解決するのにまだ役立つことに注意してください。これは、複数文字の照合要素を考慮していなかったためです。正規表現などを実装するほとんどの人は、正しく処理するのが醜く、システムロケールとインターフェイスして取得するために必要な情報を取得するための標準APIがないため、無視する傾向があります。彼ら。しかし、そうは言っても、ここに例chがあります。複数文字の照合要素であるとします。次に[c[.ch.]]、1文字または2文字を消費する可能性があります。O(log m)そして、元の回答で説明したより高度なアルゴリズムが必要になりました。これにはスペースが必要であり、おそらく時間よりもいくらか時間が必要だと思いますO(nm)（推測しています）O(n²m)せいぜい）。現時点では、複数文字の照合要素のサポートを実装することに興味はありませんが、それは素晴らしい未解決の問題を残します...

于 2012-05-02T04:16:02.927 に答える