快速篩選器列表

Question

每個人都熟悉此功能。如果您打開Outlook通訊錄並開始鍵入名稱，搜索框下面的列表會立即進行篩選，僅包含與您的查詢匹配的項目。當您瀏覽類型時，.NET Reflector具有類似的功能......您開始輸入內容，無論您瀏覽的底層程序集有多大，它都是即時的。

我一直很想知道這裏的祕訣是什麼。它如此之快？我想如果數據存在於內存中，或者需要從某個外部源（例如，數據庫，搜索某個文件等）獲取數據，也有不同的算法。

我不知道這是否會是相關的，但如果有資源在那裏，我特別感興趣的一個如何與WinForms的做到這一點......但如果你知道一般資源，我很感興趣在這些以及:-)

Answer 1

What is the most common use of the trie data structure?

特里結構基本上是一個樹結構，用於存儲相似字符串的大名單，其提供串快速查找（如散列表），並允許您迭代他們按字母順序排列。 http://en.wikipedia.org/wiki/Trie：

從圖片

在這種情況下，特里存儲字符串：
我
在
客棧
到
茶

對於您輸入的任何前綴（例如't '或'te'），您可以輕鬆查找以該前綴開頭的所有單詞。更重要的是，查找取決於字符串的長度，而不取決於Trie中存儲了多少個字符串。閱讀我引用的維基百科文章以瞭解更多信息。

Answer 2

該過程被稱爲全文索引/搜索。

如果你想玩這個算法和數據結構，我會建議你閱讀Programming Collective Intelligence的一個很好的介紹該領域，如果你只是想要的功能，我會推薦lucene。