Список быстрых фильтров

Question

Все знакомы с этой функциональностью. Если вы откроете адресную книгу outlook и начнете вводить имя, список под окном поиска мгновенно фильтруется, чтобы содержать только элементы, соответствующие вашему запросу. .NET Reflector имеет аналогичную функцию при просмотре типов ... вы начинаете печатать, и независимо от размера просматриваемой базовой сборки она почти мгновенная.

Мне всегда было интересно, что за секретный соус был здесь. Как это так быстро? Я предполагаю, что есть также разные алгоритмы, если данные присутствуют в памяти, или если они должны быть извлечены из некоторого внешнего источника (например, БД, поиск некоторого файла и т. Д.).

Я не уверен, что это будет уместно, но если есть ресурсы, мне особенно интересно, как можно сделать это с WinForms ... но если вы знаете об общих ресурсах, мне интересно те, что: -)

Answer 1

Какое наиболее распространенное использование структуры данных Trie?

Trie - это, по сути, древовидная структура для хранения большого списка похожих строк, которая обеспечивает быстрый поиск строк (например, хеш-таблицы) и позволяет вам перебирать их в алфавитном порядке.

Изображение из: http://en.wikipedia.org/wiki/Trie:

В этом случае Trie хранит строки:
я
в
Гостиница
до
чай
десять

Для любого введенного вами префикса (например, 't' или 'te') вы можете легко найти все слова, начинающиеся с этого префикса. Что еще более важно, поиск зависит от длины строки, а не от того, сколько строк хранится в Trie. Прочитайте статью в Википедии, на которую я ссылаюсь, чтобы узнать больше.

Answer 2

Процесс называется полнотекстовой индексацией / поиском.

Если вы хотите поиграть с алгоритмами и структурами данных для этого, я рекомендую вам прочитать Программирование Коллективного разума для хорошего знакомства с полем, если вы просто хотите функциональность, я бы порекомендовал Lucene .