快速筛选器列表

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。