Бор
А. Климовский
Рассмотрим следующую простую задачу: реализовать множество строк (операции добавление, удаление и поиск). С этой задачей успешно справляется структура данных бор. Вместо строгого определения лучше рассмотрим, как он работает.
Заведем корневое дерево, у которого на каждом ребре написан символ алфавита. Из каждой вершины ребро к потомкам будет существовать, только если в том поддереве есть элементы. Каждая вершина будет соответствовать строке, получающейся на пути от корня до этой вершины. Например, вершинам на рис. 1 соответствуют строки “”, “a”, “b”, “bx” (пустая строка соответствует корню, чаще всего это не используется). Это только строки, которые соответствуют вершинам, а не элементы множества.
Множеством будет часть этих строк. Для того, чтобы хранить, какая именно часть входит в множество, а какая — нет, прикрепим к каждой вершине дерева флаг. Он и будет означать, есть ли соответствующая строка в множестве.
Иногда бывает удобно по-другому маркировать элементы множества: заканчивать строки их терминальным символом (например “$”). Здесь мы так делать не будем.
Приступим к реализации.
Тип для вершины.
type
PEl = ^TEl;
TEl = record
f : boolean;
Link : array ['a' .. 'z'] of PEl;
end;
В олимпиадном программировании не рекомендуется использовать динамические переменные, так как операция new довольно долго выполняется. Поэтому заведем массив и счетчик использованных элементов.
При желании можно модифицировать реализацию на динамические переменные и, таким образом, освобождать память после удаления строки. Для эффективной реализации этого нужно будет завести в каждой вершине счетчик количества элементов множества в поддереве. Но в олимпиадах это практически не используется, поэтому останавливаться на этих модификациях не будем.
var
bor : array [0 .. maxEl] of TEl;
uk : integer; root : PEl;
procedure Init;
begin
fillchar(bor, sizeof(bor), 0); uk := 0; root := @bor[0];
end;
procedure Insert(const s : string);
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
inc(uk);
cur^.Link[s[i]] := @bor[uk];
end;
cur := cur^.Link[s[i]];
end;
cur^.f := true;
end;
procedure Delete(const s : string);
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
Writeln('No such string');
exit;
end;
cur := cur^.Link[s[i]];
end;
cur^.f := false;
end;
function Search(const s : string) : boolean;
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
result := false;
exit;
end;
cur := cur^.Link[s[i]];
end;
result := cur^.f;
end;
Оценим сложность операций над этой структурой данных. Все операции для данной строки длины L выполняются за O(L). Память требуется O(S*M), где S — сумма длин всех строк, M – размер алфавита. Понятно, что основная проблема именно в памяти.
Рассмотрим метод устранения этого недостатка. Модифицированная структура называется сжатым бором. Идея в том, что на ребрах будем писать не один символ, а сразу все символы до очередного ветвления. В этом случае, у двух ребер из одной вершины не могут совпадать первые символы (иначе было бы одно общее ребро и дополнительная вершина на разветвлении). Тогда индексировать ребра мы будем по первому символу, а сверять дальше всю подстроку (на случай, если искомой строки нет). Рассмотрим теперь реализацию сжатого бора на примере задачи номер 2 «Файловый менеджер» с Всероссийской олимпиады 2006.
Решение состоит из нескольких частей (построение графа, поиск в нем пути и так далее), мы же только напишем построение всех переходов по кнопке Alt (основная часть построения графа).
Сначала оговорим, что далее мы отождествим вершину бора и строку, ей соответствующую.
Опишем решение задачи, даже примерно не касаясь реализации. Для каждой строки s и файла i переход из него по кнопке Alt и строке s — это первый в циклическом порядке (под циклическим порядком понимается этот: i, i + 1, i + 2, …, N, 1, 2, … N, 1, 2, …) файл, имеющий эту строку s в качестве префикса. В качестве строк s достаточно рассмотреть все строки, являющиеся префиксом хотя бы одного файла.
Попробуем теперь использовать бор для реализации этого решения этой задачи. Сначала решим частный случай: построим переходы из первого файла. Еще раз поймем, какую функциональность мы хотим от модифицированного бора. Нам нужно для каждой строки s знать номер первого файла, имеющего эту строку s в качестве префикса (это и будет тот файл, на который мы перейдем, нажав Alt и s). Поэтому, в принципе, мы можем в каждой вершине завести поле first и добавлять все файлы в порядке с первого по последний и при создании вершины в это поле записывать номер файла, который в тот момент добавлялся. (Так как при добавлении строки мы пройдем ровно те вершины, которым соответствуют префиксы этой строки.) Тогда, обойдя дерево (например, обходом в глубину), мы просмотрим все префиксы всех файлов. Для каждого из них мы получим переход из первой в ту, которая записана в поле first вершины этого префикса.
Но есть недостаток этой реализации: для каждой вершины строить заново бор слишком долго. Поэтому реализуем этот частный случай чуть по-другому (в дальнейшем будет понятно, зачем). Будем идти по файлам в обратном порядке (с последнего по первый) и переписывать поле first каждый раз, когда проходим по вершине (так мы опять же пройдем все ее префиксы). Итак, мы опять получили необходимое нам заполнение полей first.
Теперь посмотрим, что нужно сделать, чтобы перейти от построения переходов из первого файла к построению переходов из последнего. Для этого нужно было бы добавить файлы n–1, n–2, …, 2, 1, n. Но просмотрим на то, что у нас уже есть. Получается, что нужно еще раз добавить n-ый файл. И так далее… Ниже приведен код разобранной части решения задачи.
type
TEl=record
First : int; // Номер строки, описанной выше
i, j : int; // Границы подстроки, написанной на ребре
link : array ['a'..'z'] of int; // Ссылки на «детей»
end;
var
bor : array [0..max] of TEl;
uk : int;
//Добавление строки j
procedure Add(j: int);
var cur, t, x : int;
begin
cur := 0; t := 1;
while t <= length(a[j]) do begin
if bor[cur].link[a[j][t]] = 0 then begin
//Добавление новой вершины
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[cur].link[a[j][t]] := uk;
bor[cur].first := j;
bor[uk].first := j;
bor[uk].i := t;
bor[uk].j := length(a[j]);
Break;
End else begin
//Переход по существующему ребру
bor[cur].first := j;
cur := bor[cur].link[a[j][t]];
x:=bor[cur].i;
//Подсчет количества совпадающих символов на ребре
while (x <= bor[cur].j) and (x <= length(a[j])) and
(a[j][x] = a[bor[cur].first][x]) do inc(x);
dec(x);
if x <> bor[cur].j then begin
//Ребро нужно делить
//Старая вершина отходит продолжению старой ветви
//Создание вершины деления
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[uk].first := bor[cur].first;
bor[uk].i := x + 1;
bor[uk].j := bor[cur].j;
bor[uk].link := bor[cur].link;
bor[cur].first := j;
bor[cur].j := x;
fillchar(bor[cur].link, sizeof(bor[cur].link), 0);
bor[cur].link[a[bor[uk].first][x+1]] := uk;
if x <> length(a[j]) then begin
//Создание вершины для новой строки
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[uk].first := j;
bor[uk].i := x + 1;
bor[uk].j := length(a[j]);
bor[cur].link[a[bor[uk].first][x+1]] := uk;
end;
Break;
end else begin //Ребро не нужно делить
t := x + 1;
bor[cur].first := j;
end;
end;
end;
end;
//Поиск всех путей по Alt из from в поддереве cur
procedure Dfs(from, cur : int);
var lp : char;
begin
if cur <> 0 then begin
//Попытка добавить путь из from в текущую вершину
if g[from, bor[cur].first] > bor[cur].i + 1 then
g[from, bor[cur].first] := bor[cur].i + 1;
end;
for lp := 'a' to 'z' do
if bor[cur].link[lp] <> 0 then dfs(from, bor[cur].link[lp]);
end;
Begin
uk := 0; fillchar(bor[0], sizeof(bor[0]), 0); bor[0].j := -1;
// Инициализация бора
for j := N downto 1 do Add(j); // Добавляем слова
for i := N downto 1 do begin
Add(i); Dfs(i,0); // Обновляем данные и ищем все искомые пути из вершины
end;
End.
Оценим теперь память. Так как в каждой вершине что-то ответвляется или заканчивается строка, несложно доказать, что количество вершин O(N). Итого памяти O(N*M), где M — опять же длина алфавита. В большинстве задач это вполне приемлемо.
Так же можно отметить, что бор подходит не только для множеств, но и для хранения для каждой строки каких-либо данных (для этого нужно просто заменить тип f на указатель на эти данные). Кроме строк могут быть многие составные объекты.
В отдельном материале можно найти применение бора в решении задачи методом динамического программирования по профилю.
Литература
[1]. Дэн Гасфилд. «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»
[2]. Кормен, Лейзерсон, Ривест. «Алгоритмы: построение и анализ»
