在手機中搜索電話號碼的算法？

Question

當前智能手​​機操作系統使用什麼通用算法從聯繫人列表中搜索姓名？

聯繫人列表不是很大，但仍然是，當我們鍵入'A'時，所有以'A'開頭的名字都很容易出現。 'A'後跟'B'，會帶來像Abe，Abott等名字，

Answer 1

快速做到這一點的一種方法是使用trie（http://en.wikipedia.org/wiki/Trie） - 基本上，您會將所有密鑰存儲在樹中其中根節點表示一個空輸入，並且您輸入的每個字符都會將分支引導至一個子樹，該子樹包含所有以您迄今爲止放置的字母集合開頭的所有名稱。在這裏使用這種技術進行自動完成有一個很好的例子：http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

在您的示例中，輸入'A'將沿着標記爲'A'的分支轉到以「A」開頭的所有名稱的子樹。從那裏輸入'B'將沿着標有'B'的分支到達下一個子樹，該子樹將包含所有'AB'名稱。向樹中添加新名稱遵循相同的流程 - 按照名稱中每個字母的正確分支（添加尚不存在的新分支），直到到達名稱的末尾，此時將其添加爲葉。

Answer 2

我不是100％確定，但如果我猜測它會是Trie。

這個想法是，你從樹的根開始，並追蹤到葉節點的路徑。你下去的每個節點都會添加另一個字母作爲後綴。

在您的示例中的樹看起來像：This（沒有足夠的代表嵌入圖像）

雙圓圈界定「接受」狀態，並不總是一個葉子結點。當你處理Trie時，它會縮小搜索範圍：

• 在「A」之後選擇「N」會拒絕「ABE」，因爲它不在路徑下方。
• 在「ANN」之後選擇「E」會拒絕「ANN」，因爲它不在路徑下方。