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

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

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