Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

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

2 <h2>Почему массив плохо подходит?</h2>

3 Проверка, совпадает ли строка-паттерн, для которой мы ищем продолжение, с началом другой строки в худшем случае требует O(k) времени, где k -длина паттерна. Фильтрация всех слов в массиве, соответствующих паттерну, займёт O(nk) времени в наихудшем случае - и никак не меньше, чем O(n), где n - количество слов. Слишком медленно, слишком неэффективно.

4 <h2>Поможет ли ассоциативный массив?</h2>

5 В плане скорости обработки запроса - безусловно, да, так какхеш-таблицы, например, могут обеспечить в среднем O(1) для запроса (в случае со строками в качестве ключей всё равно может потребоваться O(k) операций, так как нужно сравнивать две строки на равенство, но количество сравнений строк будет равно O(1)). В качестве ключа использовать множество всех возможных паттернов, а в качестве ассоциированного значения - список ссылок на подходящие строки или набор возможных продолжений.

6 Рис. 1. Так выглядит словарь для трёх слов: “foo”, “bar”, “baz” для каждого из суффиксов, подсказывающий возможные продолжения. Справа вариант, хранящий строки-продолжения, слева - хранящий ссылки на возможные продолжения.

7 И хотя ассоциативный массив гораздо лучше, чем обычный массив или список, он всё же не оптимально распоряжается ресурсами: каждый ключ - это один из возможных префиксов, и некоторые префиксы могут быть вложены друг в друга, как матрешка (“f” и “foo”, “b” и “ba”): это можно использовать для оптимизации хранения данных.

8 <h2>Trie</h2>

9 ОпределениеTrie(или бора, или префиксного дерева) довольно простое:

10 #include <unordered_map> // обеспечивает поиск за O(1) struct Trie { int isLeaf; std::unordered_map<char, Trie> children; };Каждый узел хранит коллекцию ссылок на дочерние узлы (фактически, другиеTrie). Проходя от корня до узла, можно получить префикс, ассоциирующийся с этим узлом. Обычно в узлахTrieне хранятся ключи (но, естественно, структуру данных можно расширить и хранить в узлах, что душа пожелает, например, ассоциированные с ключами значения). Однако ключ можно "восстановить", пройдя от корня до одной из листовых вершин (помечена какisLeaf). Если соответствующей ключу листовой вершины нет в Trie, значит, такой ключ здесь не хранится.

11 Рис. 2. Пример Trie, сформированный из строк “foo”, “bar”, “baz”. Зелёным выделены листовые вершины. В корне находится ε - символ, обозначающий пустую строку.

12 Чтобы использовать Trie для автодополнения, нужно взять строку-паттерн и найти узел в дереве, соответствующий этой строке (если такого узла нет - значит, известных продолжений строки нет). Все возможные листья найденного узла и есть строки-кандидаты для автодополнения!

13 Рис. 3. Поиск всех известных продолжений строки “ba” в Trie. Красным выделен путь, который пройден от корня до узла, соответствующего “ba”, бирюзовым - возможные продолжения (“r” и “z”). Глубина продолжений может быть больше одного уровня.

14 Время на поиск нужного узла - O(k), где k - длина строки, так как надо сделать максимум k-операций по поиску нужной ссылки в k-узлах.

15 Как и поиск, вставка и удаление элементов из Trie требуют O(k) операций, что позволяет эффективно расширять или чистить словарь.

16 На практике для автодополнения используют более эффективные<a>DAFSA</a>, которые расширяют и дополняют идею Trie.

17 <h2>Как ещё использовать Trie</h2>

18 Также Trie можно использовать как быстрый ассоциативный массив для хранения ключей, которые можно представить как последовательности - не только строки, но и массивы, списки и так далее.

19 Легко обеспечить обход всех листьев Trie (точнее, ассоциированных с ними ключей) в отсортированном порядке. Поскольку алфавит (или набор возможных элементов в последовательностях) ограничен, то отдельный уровень Trie можно сортировать за линейное время относительно количества дочерних узлов и размера алфавита O(n + K) при помощи алгоритма сортировки подсчетом (Counting Sort). Более подробно сортировка при помощи Trie за O(N) рассматривается<a>здесь</a>и на странице обсуждения статьи или<a>здесь</a>- см. раздел "Tries".

20 Вариант Trie, хранящий в узлах ссылки на другие узлы, используется в качестве основы для алгоритмаАхо-Корасик, который ищет все вхождения набора строк в текст за линейное время (он используется в утилите<a>fgrep</a>).

21 При помощиTrieможно легко подсчитать количество значений, если данные являются иерархическими: например, количество номеров телефонов, начинающихся с +7(900) …, или количество почтовых индексов в одном регионе, и так далее - если в каждом узле сохранять количество его вхождений.

22 Также есть усовершенствования Trie, направленные на дальнейшее "сжатие", например, компактное префиксное дерево (Radix Tree, или<a>PATRICIA</a>).

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