3

部分文字列の一致を効率的に検索できる図書館の本のタイトルのデータベースを作成したいと考えています。つまり、「プログラミング」を検索すると、プログラミングという単語を含むすべての本のタイトルが返されます。このデータベースは前処理される場合があり、完全にメモリに格納されます。

これを解決するための効率的なデータ構造と検索アルゴリズムは何ですか? これを完全に C++ で実装したいので、サードパーティのライブラリは使用しないでください。

4

2 に答える 2

7

サフィックス ツリーは、部分文字列を検索するための効率的なデータ構造です。

アイデアは次のとおりです
。サフィックスツリーデータ構造を作成し、各リーフから、このサフィックスが表す本に関連するエントリに接続します。
クエリ時に-部分文字列でツリーをトラバースし、到達したエンドポイント（最長一致）から-トラバーサル（たとえばDFS）を実行し、クエリがプレフィックスであるすべてのサフィックスに関連するすべてのエントリを取得します。

もちろん、すべての部分文字列ではなく単語のみが必要な場合は、マップ (ツリー/ハッシュ ベース) でおそらく十分であり、実装と使用がはるかに簡単です (型はmap<string,list<book> >、たとえばツリー ベースのアプローチを使用する必要があり、マップされます各単語から、タイトルにこの単語を含むすべての本を含むリストへ)。 トライを使用してマップを実装
することもできます。

于 2012-12-09T15:52:01.077 に答える
3

サブストリングマッチングには、単純なスキームがあります。「チャンク」で完全なタイトルを分割し、次の方法でデータベースを作成します。

  • 各本は一意に識別されます（ID /ポインター）
  • 各「チャンク」は、本の識別子のセットを指します

ユーザーがシステムにクエリを実行するときは、同じ方法でリクエストをチャンクに分割して、一致する本を特定します。

この単純なスキームでは、機能のカスタマイズの2つのポイントがあります。チャンクを導出する方法と本をランク付けする方法です。技術的なカスタマイズの1つのポイント：異なる一致するチャンクのセットを「マージ/結合」する方法。これは、本をランク付けする方法に依存します。

チャンクを導出する方法は？

単純な（しかし効率的な）方法は、単語の境界で分割することです：The C++ Programming Languageになり{the, c++, programming, language}ます。

注：多くの場合、一部の単語は無視されます（ブラックリストに登録されています）。たとえば、Theおそらくタイトルの80％に表示されるため、ほとんどの場合、それを検討することは役に立ちません。

注：検索では、大文字と小文字を区別しないようにする必要があります。

本をランク付けする方法は？

単純なアルゴリズムは、すべての一致を返すことです。より良い方法は、そのIDに一致したクエリ内のチャンクの数に従ってそれらをランク付けすることです。さらに良い方法は、単語がクエリよりも同じ順序で表示されるタイトル（最長の​​部分一致）を上位にランク付けすることです。そしてもちろん、同義語を検討する必要があります。

ランキングはおそらくシステムの心臓部です。Googleはランキングアルゴリズムがうまく機能するため人気があります。つまり、必要なものが見つかった場合です。

マージ/結合を実装する方法は？

元のクエリのすべてのチャンクに一致する検索結果のみを返したい場合を除いて（これは便利ですが、同義語のために煩わしいです）、順序集合を保持し、チャンクごとにそれらの共通部分を構築する必要があります。

  • chunk1：{B1, B2, B7, B9, B15}
  • chunk2：{B1, B7, B8, B13, B15}
  • chunk3：{B1, B3, B4, B7, B9, B12, B13, B14, B15}

chunk1次に、とのセットを交差さchunk2せ、 （何も変更しない）{B1, B7, B15}と交差させます。chunk3

注：小さいセットから始めると、結果を高速化する小さい中間結果を保持できます。

注：小さなセットをはるかに大きなセットと交差させる場合、大きなセットの線形ウォークは、バイナリ検索よりもはるかに遅くなる可能性があります。

一方、検索結果をランク付けする場合は、中間結果としてマップID->スコアを保持する必要がある可能性があります。そのマップは、バイナリ検索ツリーまたはハッシュマップのいずれかです（後者は非常に大きなコレクションの場合は高速ですが、一般に小さなコレクションの場合はオーバーヘッドがあります）。

このランキングは一般的に非常に遅いですが、簡単に並列化できることに注意してください。これが、GoogleがMapReduceで行うことです。

于 2012-12-09T16:48:53.187 に答える