Бор

Бор (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

Пример

Бор для набора образцов {he, she, his, hers}:

Построение

Пусть $P = \{P_1,...,P_k\}$ — набор строк, называемый словарем.

Пусть $n = \sum_{i=1}^k|P_i|$.

Начинаем с дерева из одной вершины (корня); добавляем шаблоны $P_i$ один за другим: Следуем из корня по ребрам, отмеченным буквами из $P_i$, пока возможно.

Если $P_i$ заканчивается в $v$, сохраняем идентификатор $P_i$ (например, $i$) в $v$ и отмечаем вершину $v$ как терминальную.

Если ребра, отмеченного очередной буквой $P_i$ нет, то создаем новые ребра и вершины для всех оставшихся символов $P_i$.

Это занимает, очевидно, $O (|P_1| + ... + |P_k|) = O (n)$ времени.

Поиск строки в бору

Поиск строки $S$ в бору: начинаем в корне, идем по ребрам, отмеченным символами $S$, пока возможно. Если с последним символом $S$ мы приходим в вершину с сохраненным идентификатором, то $S$ — слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет. Ясно, что это занимает $O (|S|)$ времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.

Сжатый бор

Сжатый бор — структура данных для хранения набора строк, отличающаяся от бора следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту вершину, ребро, входящее в нее, и ребро, исходящее из нее, можно объединить в одно ребро с более чем одним символом.

Источники информации

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — ISBN 5-8489-0857-4