algorithm - 携帯電話で電話番号を検索するアルゴリズム?

Question

連絡先リストから名前を検索するために、現在のスマートフォンのオペレーティング システムで使用されている一般的なアルゴリズムは何ですか?

連絡先リストはそれほど大きくありませんが、「A」と入力すると、「A」で始まるすべての名前が簡単に表示されます。「A」の後に「B」が続くと、Abe、Abott などの名前が表示されます。

Answer 1

これをすばやく行う 1 つの方法は、トライ ( http://en.wikipedia.org/wiki/Trie ) を使用することです。基本的には、ルート ノードが空の入力を表すツリーにすべてのキーを格納し、それぞれのキーを入力した文字は、これまでに入力した一連の文字で始まるすべての名前を保持するサブツリーへの分岐をたどります。この手法をオートコンプリートに使用する良い例がここにあります: http://igoro.com/archive/effective-auto-complete-with-a-ternary-search-tree/

あなたの例では、「A」と入力すると、「A」というラベルの付いたブランチを下って、「A」で始まるすべての名前を保持するサブツリーに移動します。そこから「B」と入力すると、「B」というラベルの付いたブランチを下って次のサブツリーに移動し、すべての「AB」名が保持されます。トライに新しい名前を追加する場合も同じプロセスに従います。名前の末尾に到達するまで、名前の各文字の右側のブランチをたどって (まだ存在しない場所に新しいブランチを追加します)、その時点でそれを葉。