0

テンキーしかない携帯電話の場合、検索を高速化する方法で連絡先を保存する必要があります。

ユーザーは数字を入力し、それらの数字に対応する文字で始まるアドレス帳のすべての連絡先を表示する必要があります。

私はインタビューでこれを尋ねられ、トライを作成することを提案しました. アドレス帳の名前ごとに、対応する番号をトライに追加することを提案しました。

したがって、アドレス帳に次の連絡先があるとします。

bob
boby
mat 
mav

対応する番号を使用して試行を作成します。この場合、トライには以下が含まれます。

262     (At the 2nd node 2, keep a pointer to bob)
2629    (At the node 9, keep a pointer to boby)
628     (At the node 8, keep 2 pointers, one to each of mat & mav)

より良いアプローチはありますか？

更新: このトライは、ここで説明されている T9 テクノロジで使用されますT9 タイプのディクショナリの背後にあるデータ構造

4

2 に答える 2

0

文字に基づいてツリーを構築することもできますが、左、右、電話番号のリストの3つの値である必要があります。

だからあなたの例で：

                              root node

               b  (left node)                   m  (right node)
               o                                a
               b (number)             v                   t
               y (number)

次に、ノードを下に移動して、オートコンプリートの提案を表示できます。の場合のようにbob、boby必要に応じて両方の名前を表示できます。

アップデート

今朝少し考えましたが、この論文では、文字列の並べ替えに三分木を使用しているため、この問題への取り組み方について新たな考えが生まれるかもしれません。

http://www.cs.tufts.edu/~nr/comp150fp/archive/bob-sedgewick/fast-strings.pdf

しかし、私の例のノードに5つの値がある場合、次のようになります。

  1. 左ノード
  2. 右ノード
  3. ダウンノード
  4. 現在の手紙
  5. 適用される電話番号のリスト

次に、その位置に正しい文字が見つかるまで左または右に検索し、次に下に移動してから、次の文字が見つかるまで左または右に検索します。

このように、各ノードの各文字に26個のポインターがないため、このツリーはまばらになりますが、おそらく不均衡になります。バランスを取ることは別の問題になります。

于 2013-01-30T01:54:05.667 に答える
0

ほとんどの名前は最初の数文字で区別されると思います (たとえば、リストに "Theodore"、"Theodor"、"Theodora" を含めると、はるかに外れ値になります)。

それに基づいて、トライよりもはるかに単純なもの、つまりプレフィックスを一致するエントリのリストにマッピングするハッシュ テーブルを使用できます (プレフィックスによってリスト内の名前が一意に決定されると、それ以上進む必要はありません)。

たとえば{bob, bobby, matt, mads, zed}、ハッシュテーブルがあるとします

"b" --> [bob, bobby]
"bo" --> [bob, bobby]
"bob" --> [bob, bobby]
"bobb" --> [bobby]
"m" --> [matt, mads]
"ma" --> [matt, mads]
"mat" --> [matt]
"mad" --> [mads]
"z" --> [zed]

「区別しない」接頭辞 (「b」、「bo」、「bob」など) は値リストを共有できることに注意してください。

平均共通プレフィックスが k 文字の場合、オーバーヘッドは k ハッシュ テーブル エントリの係数になります。私が推測するように、k が小さければ、最終的にトライよりも無駄のない単純なデータ構造になるでしょう。

于 2013-01-29T03:29:35.350 に答える