Бор: различия между версиями
Глеб (обсуждение | вклад) |
|||
Строка 53: | Строка 53: | ||
*[[Алгоритм Ахо-Корасик]] | *[[Алгоритм Ахо-Корасик]] | ||
*[[Цифровой бор]] | *[[Цифровой бор]] | ||
+ | |||
+ | |||
+ | [[Категория:Конспект]] |
Текущая версия на 21:22, 8 мая 2020
Префиксное дерево
Префиксное дерево или бор (англ. trie) — это структура данных для компактного хранения строк.
Он устроен в виде дерева, где на ребрах между вершинами написана символы, а некоторые вершины помечены терминальными. Бор хранит ровно те строки, которые получаются, если выписать подряд все буквы на путях от корня до терминальных вершин.
Бор можно удобно использовать для разных задач:
- Хранение строк — занимает гораздо меньше места, чем массив или сет строк.
- Сортировка строк — по бору можно пройтись dfs-ом и вывести все строки в лексикографическом порядке.
- Сет строк — как мы увидим, в нем легко добавлять и удалять слова, а также проверять, если ли слово в боре.
Реализация
Бор состоит из ссылающихся друг на друга вершин. В вершине обычно хранится такая информация:
- терминальная ли вершина,
- ссылки на детей,
- возможно, какая-нибудь дополнительная зависящая от задачи информация о слове, если вершина терминальная. Например, количество таких слов — так можно реализовать мультисет.
const int k = 26;
struct Vertex {
Vertex* to[k] = {0};
bool terminal = 0;
};
Vertex *root = new Vertex();
Чтобы добавить слово в бор, нужно пройти от корня по символам слова. Если перехода по для очередного символа нет — создать его, иначе пройти по уже существующему. Последнюю вершину нужно пометить терминальной.
void add_string (string &s) {
v = root;
for (char c : s) {
c -= 'a';
if (!v->to[c])
v->to[c] = new Vertex();
v = v->to[c];
}
v->terminal = true;
}
Чтобы проверить, есть ли слово в боре, нужно пройти от корня по символам слова. Если в конце оказались в терминальной вершине — то есть. Если оказались в нетерминальной или когда-нибудь потребовалось пройтись по несуществущей ссылке — то нет.
Удалить слово можно лениво, просто дойдя до него и убрав флаг терминальности.
Как хранить ссылки
Хранить ссылки на детей не обязательно в массиве. Возможно, наш алфавит большой — у нас тогда просто не хватит памяти инициализировать столько массивов, большинство из которых будут пустыми.
В этом случае можно придумать какой-нибудь другой способ хранить отображение из символа в ссылку на вершину, например бинарном дереве (map
) или хэш-таблице (unordered_map
). Они будут работать дольше (но лишь в константу раз), но зато потребление памяти в них будет линейным. У map-а есть ещё одно преимущество, что он хранит ссылки уже отсортированными по символам — так можно отсортировать строки, например.
Учитывайте, что писать бор можно по-разному, особенно когда решаете задачи с жестокими ограничениями.