3

キーワードのデータベースは常に増え続けています。受信テキスト入力 (記事、フィードなど) を解析し、テキストに含まれるデータベースのキーワードを見つける必要があります。キーワードのデータベースは、テキストよりもはるかに大きいです。

データベースは絶えず成長しているため (ユーザーは監視対象のキーワードをどんどん追加しています)、入力されたテキストを単語に分割し、それらをデータベースと比較するのが最善の方法であると考えています。私の主なジレンマは、この比較スキームを実装することです (このプロジェクトでは PHP と MySQL を使用します)。

最も単純な実装は、キーワード テーブルに対して単純な SELECT クエリを作成し、見つかったすべてのキーワードをリストする巨大な IN 句を作成することです。

SELECT user_id,keyword FROM keywords WHERE keyword IN ('keyword1','keyword2',...,'keywordN');

もう 1 つの方法は、メモリ内にハッシュ テーブルを作成し (memcache などを使用)、同じ方法でそれをチェックすることです。

この種の検索の経験があり、これをより適切に実装する方法について提案がある人はいますか? 私はまだこれらのアプローチを試していません。現時点ではアイデアを集めているところです。

4

6 に答える 6

3

テキスト ストリームで複数のキーワードを検索する従来の方法は、検索対象のテキストで時間線形を使用するAho-Corasick 有限オートマトンです。単語の境界でのみ文字列を認識するようにマイナーな調整を行うか、見つかったキーワードをチェックして、それらが大きな単語に埋め込まれていないことを確認するだけの方が簡単です。

で実装を見つけることができますfgrep。さらに良いことに、Preston Briggs は C で非常に優れた実装を作成しました。これは、まさにあなたが話している種類のキーワード検索を行います。(「興味深い」識別子の出現をプログラムで検索します。) Preston の実装は、Noweb literate-programming toolの一部として配布されています。PHP からこのコードを呼び出す方法を見つけるか、PHP で書き直すことができます。認識自体は約 220 行の C であり、メイン プログラムはさらに 135 行です。

Aho-Corasickを含むすべての提案されたソリューションには、次の共通のプロパティがあります。

  • データベース内のキーワードの数に比例して時間とスペースがかかる前処理ステップ。

  • テキストの長さと見つかったキーワードの数に比例する時間とスペースを必要とする検索ステップ。

Aho-Corasick は、検索ステップでかなり優れた比例定数を提供しますが、テキストが小さい場合、これは問題になりません。実際、テキストが小さく、データベースが大きい場合は、前処理ステップで使用されるメモリの量を最小限に抑えたいと思うでしょう。世界最速のスクラブル プログラムからの Andrew Appel の DAWG データ構造は、おそらくうまくいくでしょう。

于 2009-01-02T23:00:06.117 に答える
1

一般に、

  1. テキストを単語に分割する

    b。単語を正規の語根形式に変換し直す

    c。一般的な接続詞を削除する

    d。重複を取り除く

  2. 単語を一時テーブルに挿入してから、キーワードテーブルに対して内部結合を実行するか、（提案したように）キーワードを複雑なクエリ条件に組み込みます

潜在的なキーワードを事前にフィルタリングするための3文字または4文字のハッシュ配列をキャッシュすることは価値があるかもしれません。メモリサイズと有効性の間の最良のトレードオフを見つけるために実験する必要があります。

于 2009-01-02T21:04:39.797 に答える
0

ここで2つのことをします。

まず（これは質問に直接関係していません）、ユーザーキーワードをユーザーごとに分割して分割します。スライスまたはユーザーの範囲が異なるスライスに存在する分散ルックアップの場合は、理想的には異なるサーバー上に、より少ないデータでより多くのテーブルを用意します。別名、useraのすべてのデータはスライス1に存在し、userbはスライス2に存在します。

次に、キーワードの存在を判断するための、ある種のメモリ内ハッシュテーブルがあります。これは、ルックアップを配布するためにもフェデレーションされる可能性があります。n個のキーワードが存在するサーバーの場合、キーワードをハッシュしてnで変更し、それらのキーの範囲をすべてのmemcachedサーバーに分散します。この簡単な方法では、キーワードxが監視されていると言い、ハッシュして、どのサーバー上に存在するかを判断できます。次に、ルックアップを行い、追跡されているキーワードを収集/集約します。

その時点で、少なくともどのキーワードが追跡されているかがわかり、ユーザースライスを取得して後続のルックアップを実行し、どのユーザーがどのキーワードを追跡しているかを判断できます。

つまり、SQLはここでは理想的なソリューションではありません。

于 2009-01-02T21:01:53.733 に答える
0

あなたが何を求めているのか100％明確ではありませんが、探しているのは逆インデックスですか？

アップデート：

転置インデックスを使用して、複数のキーワードを一度に一致させることができます。

新しいドキュメントをトークンに分割し、ドキュメントの識別子とペアになったトークンを転置インデックス テーブルに挿入します。(かなり非正規化された) 逆インデックス テーブル:

inverted_index
-----
document_id keyword

3 つのキーワードを手動で検索する場合:

select document_id, count(*) from inverted_index
  where keyword in (keyword1, keyword2, keyword3)
  group by document_id 
  having count(*) = 3

気になるキーワードの表がある場合は、in() 操作ではなく内部結合を使用してください。

keyword_table
----
keyword othercols

select keyword_table.keyword, keyword_table.othercols from inverted_index 
   inner join keyword_table on keyword_table.keyword=inverted_index.keyword
   where inverted_index.document_id=id_of_some_new_document

これはあなたが望むものに近いですか？

于 2009-01-02T20:47:42.513 に答える
0

Sphinxなどのフルテキスト ソリューションへの移行を検討したことはありますか?

私は自分で使ったことがないので、ここで帽子から話しています。しかし、高速な全文検索ソリューションとして注目を集めています。おそらく、使用しているどのリレーショナル ソリューションよりも優れた拡張性を発揮します。

これは、Sphinx を MySQL の全文検索ソリューションとして使用することに関するブログです。

于 2009-01-02T22:41:23.643 に答える