regex - 複数の正規表現に対して 1 つの文字列を効率的にクエリする

Question

10,000 の正規表現と 1 つの文字列があり、文字列がそれらのいずれかに一致するかどうかを調べて、すべての一致を取得したいとします。それを行う簡単な方法は、すべての正規表現に対して文字列を 1 つずつクエリすることです。それを行うためのより速く、より効率的な方法はありますか?

編集: DFA の (lex) に置き換えてみました。ここでの問題は、1 つのパターンしか得られないことです。文字列「hello」とパターン「[H|h]ello」および「.{0,20}ello」がある場合、DFA はそれらの 1 つだけに一致しますが、両方ともヒットするようにします。

Answer 1

これがレクサーの動作方法です。

正規表現は、単一の非決定性オートマトン（NFA）に変換され、決定性オートマトン（DFA）に変換される可能性があります。

結果のオートマトンは、すべての正規表現を一度に一致させようとし、そのうちの1つで成功します。

ここで役立つツールはたくさんあります。それらは「レクサージェネレーター」と呼ばれ、ほとんどの言語で機能するソリューションがあります。

どの言語を使用しているのかはわかりません。Cプログラマーの場合は、re2cツールを確認することをお勧めします。もちろん、従来の（f）lexは常にオプションです。

Answer 2

私が一度取り組んだ製品でこれをしなければなりませんでした。答えは、すべての正規表現をまとめて決定性有限状態マシン（決定性有限オートマトンまたはDFAとも呼ばれます）にコンパイルすることでした。DFAは、文字列上を1文字ずつ歩くことができ、式の1つが一致するたびに「一致」イベントを発生させます。

利点は、実行速度が速く（各文字が1回だけ比較される）、式を追加しても速度が低下しないことです。

欠点は、オートマトン用に巨大なデータテーブルが必要であり、サポートされていない正規表現の種類が多いことです（たとえば、後方参照）。

私たちが使用したものは、当時の当社のC ++テンプレートナットによって手作業でコーディングされていたため、残念ながら、私はあなたに向けるFOSSソリューションを持っていません。しかし、「 DFA 」を使用して正規表現または正規表現をグーグルで検索すると、正しい方向を示すものが見つかります。

Answer 3

私は過去に同様の問題に遭遇しました。akdom が提案したものと同様のソリューションを使用しました。

通常、私の正規表現には、一致するすべての文字列に含まれる必要がある部分文字列が含まれていたので、幸運でした。単純なパーサーを使用してこれらの部分文字列を抽出し、Aho-Corasick アルゴリズムを使用して FSA にインデックスを付けることができました。次に、インデックスを使用して、特定の文字列と自明に一致しないすべての正規表現をすばやく削除し、確認する正規表現をいくつか残しました。

Python/C モジュールとして LGPL の下でコードをリリースしました。Google コード ホスティングの esmre を参照してください。

Answer 4

Martin Sulzmannこの分野でかなりの仕事をしてきました。彼はHackageDB プロジェクトをここで簡単に説明しています。これは、部分的な導関数を使用するもので、これに合わせて作成されているようです。

使用されている言語は Haskell であるため、非関数型言語への翻訳が必要な場合は非常に困難です (他の多くの FP 言語への翻訳は依然として非常に難しいと思います)。

コードは、一連のオートマトンに変換してからそれらを結合することに基づいているのではなく、正規表現自体の記号操作に基づいています。

また、コードは非常に実験的なものであり、Martin はもはや教授ではなく、「有給の雇用」(1) にあるため、関心がないか、支援や情報を提供できない可能性があります。

---

1. これは冗談です。私は教授が好きです。頭のいい人が働こうとしないほど、給料をもらえる可能性が高くなります。

Answer 5

10,000 regexen eh？ EricWendelinによる階層の提案は良い考えのようです。これらのregexenの巨大さを木の構造のようなものに減らすことを考えましたか？

簡単な例として、番号を必要とするすべての正規表現は、そのようなものをチェックする1つの正規表現から分岐する可能性があります。すべての正規表現は、別の分岐に1つを必要としません。このようにして、10,000ですべての比較を行う代わりに、実際の比較の数をツリーに沿ったパスまで減らすことができます。

これには、提供されたregexenをジャンルに分解する必要があります。各ジャンルには、失敗した場合に除外する共有テストがあります。このようにして、理論的には実際の比較の数を劇的に減らすことができます。

実行時にこれを行う必要がある場合は、指定された正規表現を解析して、事前定義されたジャンル（最も実行しやすい）またはその時点で生成された比較ジャンル（実行しにくい）に「ファイル」することができます。

「hello」を「[H|h]ello」および「。{0,20}ello」と比較する例は、このソリューションでは実際には役に立ちません。これが役立つ可能性のある単純なケースは次のとおりです。文字列のどこかに「ello」が存在し、テスト文字列が「さようなら」である場合にのみtrueを返す1000個のテストがある場合。「ello」で1つのテストを実行するだけで、それを必要とする1000のテストが機能しないことがわかります。このため、これらを実行する必要はありません。

Answer 6

特定の正規表現が別の正規表現と比較して「相加的」であったかどうかを判断する方法が必要になります。ある種の正規表現「階層」を作成すると、特定のブランチのすべての正規表現が一致しなかったと判断できます。

Answer 7

「10,000 の正規表現」の観点から考えている場合は、プロセスをシフトする必要があります。何もなければ、「10,000 のターゲット文字列に一致する」という観点から考えてください。次に、Aho-Corasick マシンのような「大量のターゲット文字列」の状況に対処するために構築された非正規表現メソッドを探します。ただし、率直に言って、10,000 のターゲット文字列は、文字列の一致というよりもデータベース ルックアップのように聞こえるため、どのマシンを使用するかよりも、プロセスのかなり早い段階で何かが軌道に乗っていないように見えます。

Answer 8

あなたはおそらく20のグループでそれらを組み合わせることができます。

(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)

各正規表現にゼロ（または少なくとも同じ数）のキャプチャグループがある限り、何がキャプチャされたかを調べて、どのパターンが一致したかを確認できます。

regex1が一致した場合、キャプチャグループ1は一致したテキストになります。そうでない場合は、undefined/ None// null..になります。

Answer 9

実際の正規表現（正式な言語理論からの正規言語に対応するものであり、Perlのような非正規表現ではないもの）を使用している場合、正規言語は結合の下で閉じられているため、幸運です。ほとんどの正規表現言語では、パイプ（|）は和集合です。したがって、次のように文字列（必要な正規表現を表す）を作成できるはずです。

(r1)|(r2)|(r3)|...|(r10000)

ここで、括弧はグループ化のためのものであり、一致するものではありません。この正規表現に一致するものはすべて、元の正規表現の少なくとも1つに一致します。

Answer 10

それは本物のパーサーの仕事だと思います。中点は、Parsing Expression Grammar（PEG）の場合があります。これは、パターンマッチングの高レベルの抽象化であり、1つの機能は、単一のパターンではなく、文法全体を定義できることです。文法をバイトコードにコンパイルし、それを専用のVMで実行することで機能する、いくつかの高性能な実装があります。

免責事項：私が知っているのはLuaのライブラリであるLPEGだけであり、基本的な概念を理解するのは（私にとって）簡単ではありませんでした。

Answer 11

「インサイドアウト」の正規表現エンジンを作成することをお勧めします。「ターゲット」が正規表現で、「用語」が文字列であるエンジンです。

ただし、それぞれを繰り返し試すソリューションははるかに簡単になるようです。

Answer 12

正規表現をハイブリッド DFA/ Bucchi オートマトンにコンパイルし、BA が受け入れ状態になるたびに、どの正規表現ルールが「ヒット」したかをフラグします。

Bucchi はこれには少しやり過ぎですが、DFA の動作方法を変更することでうまくいく可能性があります。

Answer 13

簡単に言えば、そうです、これを行う方法があり、それはコンピュータサイエンスによく知られており、それが何であるかを思い出せないということだと思います。

簡単に言うと、正規表現インタープリターは、一緒に|したときに、これらすべてをすでに効率的に処理していることに気付くかもしれません。あるいは、そうするものを見つけるかもしれません。そうでない場合は、文字列照合と検索アルゴリズムをグーグルで検索する時が来ました。

Answer 14

それらを 1 つの大きな正規表現に結合してみてください。

Answer 15

私はRagelを離れるアクションで使用します。

action hello {...}
action ello {...}
action ello2 {...}
main := /[Hh]ello/  % hello |
        /.+ello/ % ello |
        any{0,20} "ello"  % ello2 ;

文字列「hello」は、ブロック内のコードを呼び出しaction hello、次にaction elloブロック内、最後にブロック内でコードを呼び出しaction ello2ます。

それらの正規表現はかなり制限されており、代わりに機械語が優先されます。例の中括弧は、より一般的な言語でのみ機能します。

Answer 16

それを行う最速の方法は次のようなものです（コードはC＃です）：

public static List<Regex> FindAllMatches(string s, List<Regex> regexes)
{
    List<Regex> matches = new List<Regex>();
    foreach (Regex r in regexes)
    {
        if (r.IsMatch(string))
        {
            matches.Add(r);
        }
    }
    return matches;
}

ああ、あなたは最速のコードを意味しましたか? それならわからない……。