8

本当に巨大な文字列セットで文字列/パターン マッチングを行うための効率的なデータ構造を探しています。トライ、サフィックスツリー、サフィックスアレイについて知りました。しかし、これまでのところ、C/C++ ですぐに使用できる実装を見つけることができませんでした (そして、自分で実装するのは難しく、エラーが発生しやすいようです)。しかし、Suffix-Arrays が本当に探しているものであるかどうかはまだわかりません... libdivsufsort と esaxx を試しましたが、ニーズに合わせてそれらを使用する方法を見つけることができませんでした:

ユーザー入力に一致するように、定義済みの文字列セットをワイルドカード (または正規表現) と共に使用したいと考えています。事前定義された文字列の膨大なリストを取得しました

"とは *？" 「XYZとは？」"いくら *？" ...

今、私は最も一致する文字列を見つけたいと思っています (もしあれば、それはまったく一致します)。つまり、ユーザー入力: >XYZ とは? 「WHAT IS XYZ?」を見つける必要があります。「WHAT IS *?」ではなく、「WHAT IS SOMETHING?」"WHAT IS *?" を見つける必要があります。(* は任意の文字数のワイルドカードであると仮定します)。

構造の構築は時間的に重要ではありません (また、構造はスペース効率が非常に高い必要はありません) が、検索に時間がかかりすぎないようにする必要があります。どうすれば簡単にできますか？フレームワーク/ライブラリまたはコード例は大歓迎です

ありがとう

4

9 に答える 9

3

実行時にパターンを更新する必要がないというコメントを考えると、実行時の構造がまったく必要かどうかはわかりません。

re2cまたはragelを使用して、パターンマッチングを行うコードにパターンをコンパイルすることをお勧めします。

于 2012-11-19T00:27:02.460 に答える
3

flexを見たいと思うかもしれません。マニュアルから：

flex はスキャナーを生成するためのツールです。スキャナーは、テキスト内の字句パターンを認識するプログラムです。flex プログラムは、指定された入力ファイル、またはファイル名が指定されていない場合はその標準入力を読み取り、生成するスキャナーの記述を取得します。記述は、ルールと呼ばれる正規表現と C コードのペアの形式です。flex は、ルーチン yylex() を定義する C ソース ファイル (デフォルトでは lex.yy.c) を出力として生成します。このファイルをコンパイルし、flex ランタイム ライブラリとリンクして、実行可能ファイルを生成できます。実行可能ファイルが実行されると、正規表現の出現について入力が分析されます。それが見つかると、対応する C コードが実行されます。

これも：

flex の主な設計目標は、高性能スキャナーを生成することです。大規模なルール セットを適切に処理できるように最適化されています。

たとえば、このスキャナーは投稿の 3 つのパターンに一致します。

%%
"WHAT IS XYZ?"      puts("matched WHAT-IS-XYZ");
"WHAT IS ".*"?"     puts("matched WHAT-IS");
"HOW MUCH ".*"?"    puts("matched HOW-MUCH");

Flex は、離散有限オートマトン (DFA) を生成することによって機能します。DFA は、各入力文字を 1 回だけ調べます。ワイルドカードに一致する場合でも、バックトラックはありません。実行時間は O(N) で、N は入力文字数です。(より多くのパターンはより大きな DFA テーブルを生成し、より多くのキャッシュ ミスを引き起こすため、より多くのパターンには何らかのペナルティがあります。しかし、それは私が考えることができるすべてのマッチング システムに当てはまります。)

ただし、パターンを正しく一致させるには、適切な順序でパターンをリストする必要があります。Flex は、問題があるかどうかを通知する場合があります。たとえば、上記のスキャナーで WHAT-IS-XYZ および WHAT-IS パターンの順序を逆にすると、flex は次のように表示します。

:; flex matcher.l
matcher.l:3: warning, rule cannot be matched

flex の要件を満たすことができれば、flex は非常に高速なスキャナーを提供するはずです。

于 2012-11-22T09:10:10.557 に答える
2

三分探索木を試しましたか？C++ の実装は次のとおりです: http://code.google.com/p/ternary-search-tree/

三分木を構築するのがどれほど遅いかという経験はありませんが、検索が非常に高速であることは知っています。

[編集]

partialMatchSearch でツリー内のワイルドカードを一致させる場合: (免責事項: これは単なる提案であり、まったくテストされていません)

ツリーに * 記号を追加し、partialMatchSearch 関数の先頭に次のような if-clause を追加できます。

  if ( ( *key != 0 ) && tree->splitChar == '*' )
  {
     this->partialMatchSearch( tree, key+1 );
  }

言い換えれば、同じノードで、文字列を次の文字に設定して、partialMatchSearch を再帰的に呼び出すだけです。

于 2012-11-20T08:21:25.240 に答える
2

CritBitツリーをチェックしてください：

本当に必要な場合は、C++ で簡単に使用できるソース コードの例を示します。

すべての一致を見つけるには、関数を使用しますcritbit0_allprefixed

例えば

// Find all strings that start with, or are equal to, "WHAT IS"`
critbit0_allprefixed(tree, "WHAT IS", SomeCallback);`

SomeCallback試合ごとに呼ばれます。

于 2012-11-13T17:06:35.790 に答える
2

これは、非常に大量のパターンがある場合にうまく機能すると私が信じている解決策です。たった 10k ではやり過ぎかもしれませんし、それを実装することは比較的多くの作業を意味しますが、それでも興味があるかもしれません。

基本的な考え方は、パターンのサブストリングをパターン ID にマップする逆索引を作成することです。まず、各パターンに ID を取得します。

1: what is *
2: where is *
3: do * need to
etc.

次に、転置インデックスを作成します。最も単純なケースでは、パターンをトークンに分割し、各トークンをそれが出現するパターン ID のリストにマップします。トークンとして何を定義するかは柔軟に決めることができますが、1 つの方法は、空白で区切られたすべての単語が1トークンです。だからここにインデックスがあります：

what  -> 1
is    -> 1,2
where -> 2
do    -> 3
need  -> 3
to    -> 3

次に、ユーザーから入力文字列を取得したら、それをトークンに分割し、インデックスで検索します。インデックスから取得したすべてのパターン ID を結合します。例：

INPUT: what is something?

TOKENS:
   what      -> 1
   is        -> 1,2
   something -> n/a

各トークンのパターン ID を取得し、各 ID の頻度をカウントする一時データ構造 (ハッシュなど) に配置します (例: a std::unordered_map<id_type,std::size_t>)。

次に、これを頻度で並べ替えて、ルール 1 が 2 回検出され、ルール 2 が 1 回検出されたことを確認します。

次に、見つけたルールを頻度の順に入力テキストに適用します。ここでは、正規表現ライブラリなどを使用して一致を生成します。最も頻度の高いルールは、入力テキストと共通するトークンが最も多いため、一致する可能性が高くなります。

このアプローチの全体的な利点は、すべてのルールを入力に適用する必要はなく、入力と共通するトークンが少なくとも 1 つあるルールのみを適用する必要があることです。それらのルールの中でも、各ルールのトークン数の順に適用します。入力と共有し、一致するルールを見つけたら、おそらく残りの一致手順を中断できます (または、各ケースですべての一致ルールが必要かどうか、または非常に適切な一致の 1 つだけが必要かどうかによって異なります)。 ）。

改善上記は、トークンに基づいてルールの事前選択を実行します。代わりに、次のようにすべてのルールを連結できます。

what is *||where is *||do * need to||...

次に、この連結された文字列のサフィックス配列を作成します。

次に、指定された入力文字列をサフィックス配列と照合して、1 つのトークンよりも小さい一致や複数のトークンにまたがる一致を含む、すべての部分文字列一致を識別します。*上記の例では、ワイルドカード記号とがサフィックス配列に含まれていると想定してい$ますが、もちろん、入力文字列のどの部分もそれらに一致することはありません。それらをサフィックス配列から除外するか、ダミー文字に置き換えることができます。

一致を判断したら、それらを長さで並べ替えます。また、連結された文字列内の一致位置をルール ID にマップする必要があります。これは、連結された文字列に対するルールの開始位置の配列を維持することによって容易に可能になります。インデックス付きビット ベクトルに基づく高度に最適化された方法もあります (必要に応じて詳しく説明します)。

一致するルール ID を取得したら、逆インデックスの場合と同じことを行います。標準の正規表現一致 (または類似のもの) を使用して、一致ルールを適用します。

繰り返しますが、このアプローチは比較的複雑であり、非常に大量のルールがあり、トークンベース (または部分文字列ベース) のルックアップによって候補ルールの数が大幅に削減される可能性がある場合にのみ意味があります。あなたが与えたルールの例から、この場合は後者を想定していますが、扱っているルールの数 (10k のオーダー) がこのアプローチを正当化するかどうかはわかりません。ルールの総数が 10 万または数百万の場合は、より理にかなっている可能性があります。

于 2012-11-22T15:38:50.467 に答える
0

私はカーニハンとパイクのアドバイスを受けて、合理的なアルゴリズムを選び、それを総当たり攻撃します。

すべての例で「最長のプレフィックス」を探しています。これは、接尾辞木ではなく単純なトライを示唆しています。保存する必要のある文字列は最大1万個であるため、ネストされたSTLマップを使用して、最大で数時間でchar-trieを実装できるはずです。

メモリがタイトであるか、パフォーマンスが本当に重要でない限り、これは問題ないはずです。

于 2012-11-22T06:07:17.790 に答える
0

スペースが問題にならない場合は、私の頭の上から次のことを行うことができます。

現在のレベルが文字列 so へのインデックスであるツリーのこの時点で、可能な文字の子を持つツリーを作成します。ツリーの最初のレベルは、文字列内のインデックス レベル 0 または配列インデックス 0 です。

各レベルは文字列のインデックスになるため、ルート ノードはインデックス 0 になり、その子はインデックス 1 になります。各ノードには、文字列のこの時点で可能な文字数に等しい N 個の子が含まれます。

したがって、ルートに可能なセット [ "a"、"b"、"c" ] があり、3 つの子を持つとします。次に、文字列「ab」に一致する可能性のあるものを見つけたいとします。「a」のルートを持つ子に再帰し、そこから移動します。

リーフ ノードに到達する前に文字列の末尾に到達した場合、可能な文字列のリストは、現在のノードのすべての子のサブツリー全体になります。

それが理にかなっていることを願っていますが、それは一種のハフマン ツリーのように見えますが、各葉は潜在的な文字列から選択できます。

于 2012-11-13T16:52:40.717 に答える
0

これはあなたが尋ねている質問ではありません。あなたは調理済みのものが欲しかった。しかし...

これはどのくらい複雑にする必要がありますか? あなたが求めていることをやろうとしているのであれば、もう少しスペースを集中的に使用しますが、時間はあまりかかりません。

私は、アルファベットのインデックス 0 を持つツリーから始めます (そしてそうしました)。

次に、各子ノードは単語 (辞書) になります。

次に、その各子ノードは潜在的な文字列セグメントの一致になります。たとえば、「round」が「square」に直接続くことはほとんどないことがわかっています。「四角い穴に丸いペグを入れる」と言うかもしれませんが、「丸い」の次は「ペグ」です。したがって、"round" に一致するセグメントは、"round peg"、"round cup"、"round ball" になります。記事は文にとって何の意味もないので（通常）、記事を取り消します。上記の段落は、「各子ノードは単語です」と解釈されます。

ただし、高度な B ツリーでさえ、それほど多くのデータがあると遅くなる可能性があるため、ヒューリスティックを追加します。非常に大きなデータ セットを検索すると、速度が 1 分以上に低下するのを見てきました。

これは、データベースを実際に使用したくないと仮定した場合です。ASM でコーディングする場合を除き、データベースはおそらく最も高速です。

于 2012-11-22T12:32:09.050 に答える