1. ホーム
  2. 質問と答え
  3. ベストオートコンプリート/提案アルゴリズム、データ構造[C++/C]

ベストオートコンプリート/提案アルゴリズム、データ構造[C++/C]

2009-11-23 18 views

答えて

56

trieは、接頭辞に一致する単語をすばやく見つけるために使用できるデータ構造です。

編集：（それはJavaのないC++でだが）ここでオートコンプリートhttp://rmandvikar.blogspot.com/2008/10/trie-examples.html

を実装するために1を使用する方法を示す例が、ここでは3種類のauto-complete implementationsの比較ですです。

* In-Memory Trie 
* In-Memory Relational Database 
* Java Set

キーをルックアップすると、トライはSet実装よりもわずかに速くなります。トライとセットの両方は、リレーショナルデータベースソリューションよりも素早く優れています。

セットのセットアップコストは、TrieまたはDBソリューションよりも低くなります。新しい "wordsets"を頻繁に構築するのか、ルックアップのスピードを優先するのかを決める必要があります。

これらの結果はJavaであり、マイルはC++ソリューションによって異なる場合があります。簡単な解決策のために

出典

2009-11-23 15:03:59 Glen

+1

を実装するために使用することができるのGoogleのピーター・ノーヴィグの説明ですスペルの修正方法：http://norvig.com/spell-correct.html –

+2

標準的なTrieは非常にメモリを消費しますが、大きなセットの場合は、メモリの占有スペースを大幅に削減するCompacted Trieを使用する必要があります。追加の最適化には、ノード値の遅延初期化と、子/値セットの正しいデータ構造が含まれます。しばらく前に、非常に大きなデータセット（10,000,000+）を処理できる[オートコンプリートライブラリ]（https://github.com/fmmfonseca/completely）を作成し、正確な検索と近似検索に効率的に回答しました。 –

1

：あなたは（Levenshtein）までの距離（1または2）、あなたはハッシュコンテナ（セットで候補者の存在をテストするには、単純なsoltionのために十分であろう最低限の編集で「候補者」を生成、tr30またはboostからunordered_setを使用してください）。

例： あなたはカーを書きました。あなたは車を望みます。 1削除によってarrが生成されます。あなたのunordered_setにarrはありますか？いいえ、crrは1削除によって生成されます。あなたのunordered_setのcrrですか？いいえ、車は1削除によって生成されます。あなたのunordered_setに車はありますか？はい、あなたは勝ちます。もちろん

挿入、削除、移調などがあります...

あなたはunordered_setはほとんどを持っている場合は特に、あなたは時間を無駄にしている場所の候補を生成するためのあなたのアルゴリズムが実際にあることがわかります。

出典

2009-11-23 16:49:08 anno

18

大規模なデータセットの場合、バックエンドに適した候補は、ターナリ検索ツリーです。バイナリ検索ツリーのスペースのオーバーヘッドが低く、デジタル検索の文字ベースの時間効率が試行されます。

は博士ドブスジャーナルで参照してください：http://www.ddj.com/windows/184410528

目標は、ユーザーの種類として、有限結果セットの高速検索で最初のものは、「コンピュータサイエンスは、」あなたは「コンピュータ」から入力を開始することができます検索することを検討することができます。 「科学」ではなく「コンピュータ」ではない。したがって、あるフレーズがある場合は、単語で始まるサブフレーズを生成します。それぞれのフレーズについて、それらをTST（三元検索ツリー）に送ります。 TST内の各ノードはこれまでに入力されたフレーズの接頭辞を表します。そのノードにそのプレフィックスのベスト10（結果）を保存します。ノードの有限の結果（ここでは10）より多くの候補がある場合、2つの結果の競合を解決するランキング機能が必要です。

ツリーは、データのダイナミズムに応じて、数時間に1回作成することができます。データがリアルタイムであれば、他のいくつかのアルゴリズムがより良いバランスをとると思います。この場合、絶対に必要となるのは、すべてのキーストロークが非常にうまく実行された場合の結果の高速検索です。

スペルの修正の提案が含まれている場合、より複雑な問題が発生します。その場合、編集距離アルゴリズムも考慮する必要があります。

国のリストのような小さなデータセットの場合、Trieの簡単な実装が行います。 Webアプリケーションでこのようなオートコンプリートドロップダウンを実装しようとする場合、YUI3のオートコンプリートウィジェットは、リストにデータを入力した後ですべてを処理します。大きなデータを基にしたオートコンプリートのフロントエンドとしてYUI3を使用する場合は、C++でTSTベースのWebサービスを作成し、オートコンプリートウィジェットのスクリプトノードデータソースを使用して、単純なリストではなくWebサービスからデータを取得します。

出典

2009-11-23 19:17:01

3

あなたが最も人気の補完を提案したい場合は、「木を提案する」良い選択かもしれ： Suggest Tree

出典

2010-10-28 09:25:26 Nicolai

関連する問題

 関連する問題