4

ワイルドカードを含む多数の単語とフレーズ (辞書または辞書) があります。これらの単語とフレーズのすべてのインスタンスを、はるかに小さい文字列 (現時点では最大 150 文字) 内で見つける必要があります。

最初は、操作を逆に実行したかったのです。これは、短い文字列の各単語がレキシコン内に存在するかどうかを確認することです。レキシコンは、ハッシュ テーブルとして実装できます。問題は、私のレキシコンのこれらの値の一部が単一の単語ではなく、多くがワイルドカード (substri* など) であることです。

Rabin-Karp アルゴリズムを使用することを考えていますが、これが最良の選択であるかどうかはわかりません。

この操作を実行するための効率的なアルゴリズムまたは方法は何ですか?

サンプルデータ:

辞書には何百もの単語が含まれており、拡張される可能性があります。これらの単語は、ワイルドカード文字 (アスタリスク) で終わる場合があります。いくつかのランダムな例を次に示します。

  • 良い
  • 悪い
  • 解放された*
  • 不注意*
  • 大きな損失

（この時点で）分析しているテキストは、短い非公式の（文法的に）英語のステートメントです。テキストの代表的な例 (この時点でも) は、Twitter のツイートです。これらは、およそ 140 文字に制限されています。例えば：

Just got the Google nexus without a contract. Hands down its the best phone 
I've ever had and the only thing that could've followed my N900.

このテキストに対して非常に単純な感情分析を行っていることに注意してください。私たちの感情分析技術は私の関心事ではありません。既存のソリューションを「リアルタイム」処理システムに移行しているだけで、いくつかの最適化を実行する必要があります。

4

7 に答える 7

6

これは、単一の文字列内の文字列の大規模なセットのすべての一致を見つけるように特別に設計されたAho-Corasick 文字列一致アルゴリズムの優れた使用例だと思います。これは 2 つのフェーズで実行されます。最初のフェーズでは、一致するオートマトンが作成されます (事前に実行でき、線形時間のみが必要です)。2 つ目のフェーズでは、オートマトンを使用してすべての一致を検索します (線形時間のみが必要です)。 、および一致の総数に比例する時間)。このアルゴリズムは、ワイルドカード検索もサポートするように適合させることができます。

お役に立てれば！

于 2013-04-04T16:50:08.783 に答える
3

私が捨てたかった答えの 1 つは、Boyer-Moore探索アルゴリズムでした。grepが使用するアルゴリズムです。grep はおそらく、利用可能な最速の検索ツールの 1 つです。さらに、GNU Parallelのようなものを使用して grep を並行して実行できるため、アルゴリズムを実際に高速化できます。

さらに、ここに興味深い記事があります。

于 2013-04-04T18:37:20.850 に答える
2

テキスト内のすべての単語を辞書と照合するという、元のアイデアを引き続き使用することができます。ただし、効率的に実行するには、辞書にインデックスを付けて、ルックアップを非常に高速にする必要があります。情報検索システムで使用されるトリックは、いわゆるパーミュータームインデックス( http://nlp.stanford.edu/IR-book/html/htmledition/permuterm-indexes-1.html ) を保存することです。

基本的にあなたがしたいことは、単語のすべての可能な順列を辞書に保存することです（例：家の場合）：

house$
ouse$h
use$ho
...
e$hous

このインデックスを使用して、ワイルドカード クエリをすばやくチェックできます。たとえば、ho*e がある場合、permuterm インデックスで で始まる用語をe$ho調べると、house と一致するものがすぐに見つかります。

通常、検索自体は対数検索戦略 (二分検索または B ツリー) を使用して実行されるため、通常は非常に高速です。

于 2013-04-04T18:22:48.690 に答える
2

パターンが完全な単語である限り、or一致させたくありませんstorage。スペースと句読点はマッチ アンカーです。簡単な方法は、レキシコンをスキャナー ジェネレーターの入力に変換し (たとえば、 flexを使用できます)、スキャナーを生成し、それを入力に対して実行することです。

スキャナー ジェネレーターは、入力内のトークンの出現を識別するように設計されており、各トークンの種類は正規表現で記述されています。Flex および同様のプログラムは、スキャナーを迅速に作成します。Flex はデフォルトで最大 8k のルール (あなたの場合はレキシコン エントリ) を処理しますが、これは拡張できます。生成されたスキャナーは線形時間で実行され、実際には非常に高速です。

内部的には、トークンの正規表現は標準の「クリーネの定理」パイプラインで変換されます。最初に NFA に変換され、次に DFA に変換されます。次に、DFA は独自の最小形式に変換されます。これは HLL テーブルにエンコードされ、テーブルを参照してスキャナーを実装するラッパー内で発行されます。これが flex の機能ですが、他の戦略も可能です。たとえば、DFA はgoto、コードの実行時に DFA の状態が命令ポインターによって暗黙的に表されるコードに変換できます。

space-as-anchors の警告の理由は、Flex のようなプログラムによって作成されたスキャナーは通常、重複する一致を識別 できないためです。たとえば、 とのstrangers両方に一致することはありません。strangersrange

あなたが与えたレキシコンの例と一致するフレックススキャナーは次のとおりです。

%option noyywrap
%%
"good"                    { return 1; }
"bad"                     { return 2; }
"freed"[[:alpha:]]*       { return 3; }
"careless"[[:alpha:]]*    { return 4; }
"great"[[:space:]]+"loss" { return 5; }
.                         { /* match anything else except newline */ }
"\n"                      { /* match newline */ }
<<EOF>>                   { return -1; }
%%
int main(int argc, char *argv[])
{
  yyin = argc > 1 ? fopen(argv[1], "r") : stdin;
  for (;;) {
    int found = yylex();
    if (found < 0) return 0;
    printf("matched pattern %d with '%s'\n", found, yytext);
  }
}

そしてそれを実行するには：

$ flex -i foo.l
$ gcc lex.yy.c
$ ./a.out
Good men can only lose freedom to bad
matched pattern 1 with 'Good'
matched pattern 3 with 'freedom'
matched pattern 2 with 'bad'
through carelessness or apathy.
matched pattern 4 with 'carelessness'
于 2013-04-06T16:57:42.163 に答える
1

これはアルゴリズムの質問に正確に答えるものではありませんが、re2ライブラリを調べてください。Python、Ruby、およびその他のさまざまなプログラミング言語には、優れたインターフェイスがあります。私の経験では、それは盲目的に高速であり、コード内の非常によく似たボトルネックをほとんど大騒ぎせずに取り除き、実質的に余分なコードを追加する必要はありませんでした。

唯一の複雑さは、重複するパターンに伴います。パターンを単語境界で開始する場合は、辞書を、 の各グループが のプレフィックスを持つr_1, r_2, ..., r_k形式の正規表現のセットに分割できる必要があります。一致する場合は一致する必要があるため、評価を短絡できます。\b(foobar|baz baz\S*|...)r_{i+1}r_ir_{i+1}r_i

高度に最適化された C でアルゴリズムを実装していない限り、このアプローチは、このスレッドの他の場所にある (アルゴリズム的に優れた) 回答よりも高速になると思います。

于 2013-04-05T07:13:30.310 に答える
0

これをはっきりさせてください。大量のクエリ セットと1 つの小さな文字列があり、その文字列内のすべてのクエリのインスタンスを検索したいとします。

その場合、検索時間ができるだけ短くなるように、その小さなドキュメントに狂ったようにインデックスを付けることをお勧めします。地獄。そのドキュメント サイズでは、(ワイルドカードに一致させるためなどに) 小さなミューテーションを行うことも検討し、それらにもインデックスを付けます。

于 2013-03-28T19:48:46.373 に答える
-1

私は非常によく似た仕事をしていました。これが私がそれを解決した方法です、パフォーマンスは信じられないほどです http://www.foibg.com/ijita/vol17/ijita17-2-p03.pdf

于 2015-03-18T08:05:03.497 に答える