3

iPhone/Android アプリのユーザーが検索する必要がある文字列の大きなリストがあります。文字列はアルファベット順にソートされていますが、検索クエリが文字列の先頭だけでなく文字列内のどこかにある場合、文字列を結果に含める必要があるため、実際にはそれほど有用ではありません。ユーザーが検索クエリを入力しているときに、現在入力した内容の結果を反映するように検索を更新する必要があります。(たとえば、「cat」と入力すると、「c」、「ca」、および「cat」の結果が表示されます)。

私の現在のアプローチは次のとおりです。

空から始まる「検索結果」のスタックがあります。ユーザーが検索クエリを長くするために何かを入力した場合、現在の検索結果をスタックにプッシュし、現在の検索結果のみを検索して新しい結果を検索します (何かが完全な文字列リストにあることは不可能ですが、現在のリストにはありません)。この場合の結果)。

ユーザーがバックスペースを押した場合、検索結果をスタックからポップして復元するだけで済みます。これはほぼ瞬時に実行できます。

このアプローチは、「後方」検索 (検索クエリを短くする) や、検索クエリがすでに十分に長く、結果の数が少ない場合に最適です。ただし、ユーザーが入力する最初の数文字のそれぞれについて、文字列の完全なリストを O(n) 時間で検索する必要があり、非常に時間がかかります。

私が検討したアプローチの 1 つは、2 文字または 3 文字の可能なすべての検索クエリの結果を事前にコンパイルしたリストを用意することです。このアプローチの問題点は、26^2 または 26^3 のようなリストが必要になり、かなりのスペースを占有することです。

考えられる他の最適化または代替アプローチはありますか?

4

3 に答える 3

4

事前に計算されたリストを作成するには、プレフィックス ツリー (trie) の使用を検討する必要があります。「c」、「ca」、および「cat」の結果をサブキャラクターごとに表示するのが良い考えかどうかはわかりません。たとえば、ユーザーが「食べる」という単語を検索しているとします。アルゴリズムは、「e」、「ea」、最後に「eat」を含むすべての単語を見つける必要があります。そのほとんどはユーザーにとって役に立ちません。電話アプリなら単語ベースでやったほうがいいかもしれません。複数の単語からなる文字列はトークン化できるため、「大きな賭け金」で「賭け金」を検索するとうまくいきますが、「取る」は検索できません。

于 2012-05-02T21:49:26.843 に答える
1

圧縮サフィックスツリーを使用できます

于 2012-05-03T00:35:49.477 に答える
1

私は、1 つか 2 つの文字だけが押されたときに、Google や他の人が完全なリストを提供しないことに気付きました。あなたの場合、おそらく良い出発点は、ユーザーが最低3文字を入力したときにのみ検索クエリ結果の入力を開始することです.

それ以降のバージョンでは、それが重要な場合は、Google の方法からヒントを得て、より洗練された処理を行うことができます。以前のユーザーが選択した実際のエントリを追跡し、頻度順に並べ替えます。次に、サーバーで cron ジョブを毎日実行して、小さなデータベース テーブルに各文字で始まる上位 10 エントリを入力します。1 つまたは 2 つの文字しか押されていない場合は、すべてをスキャンする代わりに、この小さなテーブルの結果を使用します。リスト。

于 2012-05-02T21:19:40.613 に答える