正規表現のコレクションを効率的に検索する

Question

正規表現の数量が不明（ゼロ以上、数千万未満）の場合、指定した文字列に一致する正規表現を効率的に検索する方法は何ですか？

どのような種類の容器、アルゴリズム、データ構造を使用する必要がありますか？私がすべての正規表現のマッチをしたいのであれば、唯一のマッチする正規表現を見つけたい場合、これは違うのですか？それらはちょうど一致したどれくらいを知りたがっていると異なっていますか？

別の言い方をすると、ユーザに任意の文字列を入力させて、正規表現のコンテナがあるとします。どのようにしてコンテナを設計しても、自分が選んだ方法で検索することができます。そのコレクションのユーザー入力と一致するすべての正規表現のリストが必要な場合はどうすればよいですか？マッチがいくつあるのか知りたいのですが？試合の一意性を保証したければどうなりますか？

Answer 1

正規表現で文字列を一致させる前に事前計算を行うことができれば、すべての正規化文字列をDFAに変換することができます。

参照：https://en.wikipedia.org/wiki/Deterministic_finite_automaton

このアプローチは、非常に多くの場合、パーサとコンパイラに字句解析（トークン化）のために使用されています。 DFAのメリットは、どれくらいの正規表現を入れても、どれほど複雑であっても、同じスピード（速い）であることです。

これは簡単ではありませんが、周辺にはツールがあります。 Javaで作業している場合、私はあなたが使用できるオープンソースプロジェクトを持っています：http://mtimmerm.github.io/dfalex/。あなたの他の質問に答えるために、あなたが望むならば、これと一致するすべての正規表現の集合を得ることができます。

あなたはそれを自分で行う方法に興味があるなら、プロセスは一般的に（トンプソンの建設（https://en.wikipedia.org/wiki/Thompson%27s_construction）を使用して、NFA（https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton）にあなたの正規表現を変換した後、サブセットの建設を使用してDFAにNFAの変換で構成されていhttps://en.wikipedia.org/wiki/Powerset_construction）、通常はHopcroftのアルゴリズムでDFAを最小化します（https://en.wikipedia.org/wiki/DFA_minimization）

最適化とフィネスのための余地がたくさんあります。

Good Luck！

P.S.私はいくつか注意する必要があります：1）あなたは一般的に逆参照を持つ正規表現からDFAを作ることはできません。 2）理論上、DFAが指数関数的に大きくなる可能性があります。これは偶然によって起こることはほとんどありませんが、あなたの正規表現が潜在的に悪意のある人々によって入力された場合、その可能性について何かしなければなりません。

Answer 2

A PHP例：

<?php 
$regex_array = array(
    "/regex_1/" => 0, 
    "/regex_2/" => 0, 
    "/regex_3/" => 0 // and so on and so forth 
); 

$strings_array = array(
    "input_string_1", 
    "input_string_2", 
    "input_string_3" // and so on and so forth 
); 

foreach ($regex_array as $key => $value) 
    foreach ($strings_array as $current_string) 
    if (preg_match($key, $current_string)) 
     $regex_array[$key]++; 
?> 

Hereのrunnigコード。

Answer 3

私は数日で誰もそれを打つことができない限り、答えとして自分の答えを記しません。

---

これまでのところ私が価値があった唯一のアイデアは、正規表現を追加するときに正規表現をコンテナ内の2つのファイルのいずれかに入れることです。

1つのパイルには、ワイルドカード、文字クラス、または従来の文字列から逸脱するものを含むすべての正規表現があります。私はこれをRegexPileと呼びます。

他のファイルには、文字列であるか、または文字列に変換可能なすべての正規表現が入ります。文字列が一致しやすく、アルゴリズムがよく理解されているので、このパイルが配列され、並べ替えられ、並べ替えられ、バイナリ検索で文字列を見つけることは簡単です。私はこれをSortedStringArrayと呼びます。

単純に、私は直線的にRegexPileを検索し、SortedStringArrayのバイナリ検索を行うことができます。これは、少なくとも私が時間や空間の点ではほとんど比較やコストをスキップすることができますが、あまり実際の最適化もしません。

これは計算上似ていますが、このようなことをすれば、各正規表現（または小さな正規表現グループ）ごとにスレッドを起動すると思います。RegexPile私の考えは正規表現がそれを行うことができるので、任意の正規表現は無限の量を取ることができるということです。その後、スレッドが長すぎる場合は、タイムアウトに基づいて失敗し、すべてのスレッドを早期に終了できます。最初の文字がチェックされると、ほとんどのスレッドが消えてしまうということを意味する最初の文字で大半が失敗すると私は考えています。安価なコピーオンライトスレッドでは、ほとんどのシステムが今日提供していますが、このスレッド生成は十分に安価でなければならず、多くのスレッドが終了する前に閉じる必要があり、かなり類似しているスレッドのみがいつでも残っています。次に、別のスレッドでSortedStringArrayのバイナリを行います。