Бор
Опредение
Бор, или префиксное дерево, - структура данных для эффективного хранения и обработки строк. Вершины в боре соответствуют отдельным символам. В каждой вершине хранится также числовое значение, обозначающее, сколько строк заканчиваются в этой вершине. Строки представляются в виде путей по бору от корня (пустой строки) до последнего символа.
В боре, изображённом выше, хранятся следующие строки:
- “to” - 7 экземпляров
- “tea” - 3 экземпляра
- “ted” - 4 экземпляра
- “ten” - 12 экземпляров
- “A” - 15 экземпляров
- “i” - 11 экземпляров
- “in” - 5 экземпляров
- “inn” - 9 экземпляров
Таким образом, в каждой вершине бора хранится количество строк, заканчивающихся в этой вершине, и указатели на дочерние вершины, каждая из которых соответствует определённому символу.
Реализация
При реализации бора используются указатели и динамическое выделение памяти. Предполагается владение этими концепциями языка C++.
Во всех предыдущих реализациях структур данных деревья представлялись или в виде массива с формулами перехода, или в виде списка смежности. Для реализации бора необходимо “реальное” представление деревьев, каждая вершина в которых - отдельный элемент, которому соответствует собственный тип данных. В каждой вершине хранится массив указателей на дочерние вершины.
Реализуем тип данных для представления вершин в дереве:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node {
node *next[26]; //Массив указателей на следующие вершины
//next[i] - указатель на следующую вершину, соответствующую символу ('a' + i)
//(предполагается, что используются только строчные латинские буквы)
int strings; //Количество строк, заканчивающихся в этой вершине.
node() {
for (int i = 0; i < 26; i++) { //изначально заполняем next нулевыми указателями,
next[i] = nullptr; //так как следующие вершины ещё не созданы
}
strings = 0;
}
};
Для добавления в бор очередной строки, нужно создать все необходимые вершины, если они ещё не созданы, и увеличить счётчик строк в последней вершине на \(1\):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
node *root = new node(); //корневая вершина бора, соответствующая пустой строке.
void add(const string& s) {
node *cur_v = root; //текущая вершина
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (cur_v->next[c - 'a'] == nullptr) {
cur_v->next[c - 'a'] = new node();
}
cur_v = cur_v->next[c - 'a'];
}
cur_v->strings++;
}
Проверки наличия в боре строки реализуется похожим образом:
1
2
3
4
5
6
7
8
9
10
11
12
bool has(const string& s) {
node *cur_v = root;
for (int i = 0; i < s.length(); i++) {
cur_v = cur_v->next[s[i] - 'a'];
if (cur_v == nullptr) {
return false;
}
}
return cur_v->strings > 0;
}
С бором можно выполнять множество операций, но большинство из них сводятся к обходу всех строк с помощью DFS. Для примера давайте реализуем функцию, выводящую все строки, содержащиеся в боре:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string cur_str = "";
void write(node *v = root) {
for (int i = 0; i < v->strings; i++) {
cout << cur_str << endl;
}
for (int i = 0; i < 26; i++) {
if (v->next[i] != nullptr) {
cur_str.push_back('a' + i);
write(v->next[i]);
cur_str.pop_back();
}
}
}
Применение
Бор является достаточно легко модифицируемой структурой данных, и в зависимости от значений, хранимых в вершинах, и способа обхода с его помощью можно реализовать множество различных операций. Конкретная реализация бора варьируется от задачи к задаче.
Бор также используется как вспомогательная структура данных для более сложных строковых алгоритмов, в частности, алгоритма Ахо-Корасик.