4

ワイルドカード文字列のセットに対して単一の文字列を一致させるソリューションを探しています。例えば

>>> match("ab", ["a*", "b*", "*", "c", "*b"])
["a*", "*", "*b"]

出力の順序は重要ではありません。

10^4 のワイルドカード文字列の順序で照合し、約 10^9 のマッチ コールを行います。これは、おそらく次のようにコードを書き直す必要があることを意味します。

>>> matcher = prepare(["a*", "b*", "*", "c", "*b"]
>>> for line in lines: yield matcher.match("ab")
["a*", "*", "*b"]

ワイルドカードを処理する Python でのトライ実装の作成を開始しましたが、これらのコーナー ケースを正しく処理する必要があります。それにもかかわらず、私は聞いてみたいと思っています。これをどのように解決しますか？これをより速く解決できるPythonライブラリはありますか?

これまでのいくつかの洞察:

  • 名前付き (Python, re) 正規表現は、1 つの一致しか返さないため、ここでは役に立ちません。
  • pyparsingは素晴らしいライブラリのように見えますが、ドキュメントがまばらであり、複数のパターンのマッチングをサポートしていないようです。
4

2 に答える 2

4

Aho-Corasickアルゴリズムの実装（または同様のもの）の助けを借りて、re2ライブラリFilteredRE2のクラスを使用できます。re2 ドキュメントから:

必須の部分文字列。文字列のリストのどれが大きなテキストの部分文字列として表示されるかを確認する効率的な方法があるとします (たとえば、Aho-Corasick アルゴリズムを実装した可能性があります)。ただし、ユーザーは正規表現検索も効率的に実行できるようにしたいと考えています。 . 多くの場合、正規表現には大きなリテラル文字列が含まれます。それらを特定できれば、それらを文字列サーチャーにフィードできます。次に、文字列サーチャーの結果を使用して、必要な正規表現検索のセットをフィルター処理できます。FilteredRE2 クラスは、この分析を実装します。正規表現のリストを指定すると、正規表現をたどってリテラル文字列を含むブール式を計算し、文字列のリストを返します。例えば、FilteredRE2 は、(hello|hi)world[az]+foo をブール式「(helloworld OR hiworld) AND foo」に変換し、これら 3 つの文字列を返します。複数の正規表現を指定すると、FilteredRE2 はそれぞれをブール式に変換し、関連するすべての文字列を返します。次に、どの文字列が存在するかを通知された後、FilteredRE2 は各式を評価して、存在する可能性のある正規表現のセットを識別できます。このフィルタリングにより、実際の正規表現検索の数を大幅に減らすことができます。FilteredRE2 は各式を評価して、存在する可能性のある正規表現のセットを識別できます。このフィルタリングにより、実際の正規表現検索の数を大幅に減らすことができます。FilteredRE2 は各式を評価して、存在する可能性のある正規表現のセットを識別できます。このフィルタリングにより、実際の正規表現検索の数を大幅に減らすことができます。

これらの分析の実現可能性は、入力の単純さに大きく依存します。1 つ目は DFA 形式を使用し、2 つ目は解析された正規表現 (Regexp*) を使用します。RE2 がその正規表現で非正規の機能を許可した場合、この種の分析はより複雑になります (おそらく不可能でさえあります)。

于 2012-10-22T05:09:49.293 に答える
3

Aho-Corasick アルゴリズムが機能するようです。esmreは、私が探していることをしているようです。私はこの質問からこの情報を得ました。

于 2012-10-15T22:21:44.553 に答える