Фильтр Блума и trie

Коротко: Фильтр Блума экономно проверяет, «точно нет» или «возможно есть» элемент в множестве. Trie (префиксное дерево) хранит слова по начальным буквам.

Подробнее: Фильтр Блума — битовый массив с несколькими хеш-функциями. «Нет» — достоверно, «да» может быть ложной тревогой. У trie для каждого символа есть своя ветвь. Общие начала хранятся только один раз; поиск занимает O(длина слова).