0

キーがregexである要素の配列があります。指定された文字列 ( regexではない) が、キーregexの実行に基づいて一致する配列値をO(N)時間未満で返す高速アルゴリズムを考え出したいと思います。

現在、配列の線形スキャンを行っています。要素ごとに、posix regexec API を使用してそれぞれの正規表現を実行していますが、これは、一致する要素を見つけるために、配列全体を検索する必要があることを意味します。

配列がキーとして単純な文字列のみで構成されている場合、配列を保持してbsearchスタイルの APIを使用することもできましたが、正規表現ではそれほど簡単ではないようです。

ここで何か不足していますか？

例は次のとおりです

// this is mainly to be considered
// as pseudocode
typedef struct {
  regex_t  r;
  ... some other data
} value;

const char *key = "some/key";
value my_array[1024];
bool  my_matches[1024];
for(int i =0; i < 1024; ++i) {
  if(!regexec(&my_array[i].r, key, 0, 0, REG_EXTENDED))
    my_matches[i] = 1;
  else
    my_matches[i] = 0;
}

しかし、ご覧のとおり、上記は線形です。ありがとう

補遺:

上記のアルゴリズムと以下の回答で提案されているものを実行する単純な実行可能ファイルをまとめました。ここでは、大きな正規表現からサブ正規表現のバイナリツリーを構築し、それをナビゲートしてすべての一致を見つけます。
ソースコードはこちら (GPLv3): http://qpsnr.youlink.org/data/regex_search.cpp
コンパイル:g++ -O3 -o regex_search ./regex_search.cpp -lrt
および実行: ./regex_search "a/b"(または--helpオプションのフラグを使用)

興味深いことに (予想通りだと思いますが)、ツリー内を検索する場合、実行に必要な正規表現の数は少なくて済みますが、これらは比較ごとに実行するのがはるかに複雑であるため、最終的にかかる時間はベクトルの線形スキャンと釣り合いがとれます. 結果が印刷されてstd::cerrいるので、それらが同じであることがわかります。

長い文字列や多くのトークンを使用して実行する場合は、メモリの使用量に注意してください。Ctrl-Cシステムがクラッシュするのを防ぐために、ヒットする準備をしてください。

4

1 に答える 1

1

これは可能ですが、それを実現するには独自の正規表現ライブラリを作成する必要があると思います。

posix 正規表現を使用しているので、最新の正規表現ライブラリが実装する傾向がある計算機能のランダムなコレクションとは対照的に、実際に正規表現を使用するつもりであると想定します。正規表現はユニオン (および他の多くの操作) の下で閉じられるため、正規表現の配列から単一の正規表現を作成できます。

すべての正規表現は DFA (決定論的有限状態オートマトン) によって認識でき、DFA は、複雑さに関係なく、文字列の長さに線形の時間で文字列を認識 (または認識に失敗) します。DFA のセットを指定すると、すべての DFA の言語を認識するユニオン DFA を構築できます。さらに (DFA が文字列を受け入れることの意味を少し変更して)、 DFA は文字列と一致しました。

DFA に関するウィキペディアの記事と同じ用語を使用してみます。単一のアルファベット Σ を共有する一連の DFAがあるとします。したがって、次のようになります。M = {M1...Mn}

Mi = (Qi, Σ, δi, qi0, Fi) where Qi = {qij} for 0 ≤ j < |Qi|, and Qi ⊂ Fi.

ユニオン DFA を次のように構築します(はい、いいえ。それについて説明します)。M⋃ = (Q⋃, Σ, δ⋃, q⋃0)F

q⋃0 = <q10,...,qn0>

δ⋃(<q1j1,...,qnjn>, α) = <δ1(q1j1, α),... , δn(qnjn, α)>それぞれα ∈ Σ

Q⋃から開始して到達可能なすべての州で構成されます。δ⋃q⋃0

これは、遷移関数のサイズの積に比例する時間で標準的な閉鎖アルゴリズムを使用して計算できます。δi

文字列 α 1 ...α mでユニオン マッチを実行するには、通常の方法でユニオン DFA を実行します。開始記号から開始し、その遷移関数を各 α に順番に適用します。文字列の最後の記号を読み取ると、DFA は何らかの状態になります。その状態から、次のように文字列に一致するセットを抽出できます。<q1j1,...,qnjn>Mi{Mi | qiji ∈ Fi}

これが機能するためには、個々の DFA が完全である必要があります (つまり、すべてのシンボルのすべての状態からの遷移があります)。一部の DFA 構築アルゴリズムは、一部のシンボルでトランジションのない DFA を生成します (そのプレフィックスを持つ文字列が言語にないことを示します)。そのような DFA は、すべてのシンボルでそれ自体に遷移する、受け入れられない「シンク」状態で拡張する必要があります。

上記のアルゴリズムを実装するのに十分な DFA を公開する正規表現ライブラリは知りませんが、非正規の機能を実装しようとしない単純な正規表現ライブラリを作成するのはそれほど面倒ではありません。DFA ライブラリも見つかる場合があります。

正規表現から DFA を構築すると、式のサイズが指数関数的になる可能性がありますが、そのようなケースはまれです。(非決定論的な FA は線形時間で構築できますが、場合によっては、NFA のべき乗集合の構築には指数関数的な時間と空間が必要になります。ウィキペディアの記事を参照してください。)ただし、DFA が構築されると、ユニオン FA は次のようになります。 DFA のサイズの積に比例する時間で構築されます。

したがって、各正規表現を DFA に一度コンパイルし、DFA のセットを維持することで、正規表現のセットを動的に変更できるようにするのは簡単です。正規表現のセットが変更された場合、ユニオン DFA を再生成するだけで済みます。

すべてが役立つことを願っています。

于 2013-01-19T22:32:48.447 に答える