3

質問があります。30000 名の名前を含むビジネス アドレス帳を実装する必要があります。すべての名前には姓と名が含まれます。名だけでなく姓でも検索するオートコンプリート テキスト ボックスを実装する必要があります。Googleで検索すると、この問題はパトリシアトライを使用して解決されることがわかりましたが、プレフィックス検索のみを行うため、ファーストネーム+ラストネームでトライを作成した場合、ファーストネームだけでなくラストネームでも検索するにはどうすればよいですか?

このように 2 つの文字列を挿入するエントリを複製する必要がありますか? ファーストネーム+ラストネームとラストネーム+ファーストネーム

私を助けてください！！！

検索は非常に効率的でなければなりません。

ありがとう。

4

2 に答える 2

2

もう 1 つの可能性は、2 つの試行を作成することです。

最初のもの (let it be T1) は名用で、2 番目 (let it be T2) は姓用です。

トライを構築するときは、T1(通常は記号として示される$) の各単語ターミネータから、 の関連するエントリへのポインタのリストを追加しますT2。逆もまた同様です。

IE John Doe が前菜の場合:

T1:
     J
     |
     O
     |
     H
     |
     N
     |
     $1
T2:
     D
     |
     O
     |
     E
     |
     $2

$1 は $2 へのポインターを含むリストを保持し、$2 は $1 を含むリストを保持します。

各プレフィックス検索は両方の試行で検索し、オートコンプリートを取得してから、ポインターを使用してフルネームを取得します (部分検索では姓/名のみが得られ、ポインターを使用して 2 番目を取得します)。

フルネームの検索は、両方の試行で検索することによって行われます ( で名を探し、 で姓を探しT1、T2関連する$1と を$2それぞれ取得します)、ポインタが一致するかどうかを確認する必要があります ( containsのリストl1とリストを含む)。もしそうなら、その名前は辞書に載っています。$1$2l2$2$1

ノードへのポインターを取得したら、ルートに到達してこの記号が表す$単語を取得するまで、単純にトライに戻ることができることに注意してください。$(各ノードから親へのポインタが必要)

また、注意: 単純な試行について説明しましたが、同じアプローチを使用して代わりにパトリシア試行を使用しない理由は実際にはありません。

于 2012-06-06T21:22:17.240 に答える
0

はい、最も簡単な解決策は、両方のバリアントを挿入することです。ただし、これはエントリではなく、検索文字列のみを複製する必要があります。おそらく、姓と名の区切りを何らかの方法で正規化する (= アドレス帳とユーザー入力の句読点を削除する) ことで、「John Doe」、「Doe」などの入力のすべてのケースでエントリを見つけることができます。 、ジョン」、「ドウ・ジョン」など。

部分的なトライではなく、バランスのとれたツリーのみを使用します。多くの言語では、ライブラリ (少なくとも Java と C++) のソートされたマップの実装として、バランスのとれたツリーを見つけることができます。

于 2012-06-06T21:20:57.467 に答える