Конспект: бор и Ахо-Корасик

Понятия

Бор (префиксное дерево) - дерево, где на рёбрах символы, путь от корня читается как начало слов набора, а узлы, где слова кончаются, помечены. Узел не хранит своё слово: слово - это путь к нему.

Сжатый бор - бор, в котором цепочки узлов с единственным сыном склеены в рёбра со строками. Узлов не больше удвоенного числа слов.

Суффиксная ссылка узла - узел, строка которого есть самый длинный собственный конец строки этого узла, имеющийся в боре; если такого нет - корень.

Выходная ссылка узла - ближайший помеченный узел на его цепочке суффиксных ссылок.

Оценка, чувствительная к выходу - оценка времени, в которую входит размер ответа.

Тернарное дерево поиска - бор, где выбор ребёнка - дерево поиска по символу: узел хранит символ и ссылки «меньше, равно, больше». Памяти в разы меньше, шагов на букву - больше; вставлять вразнобой.

Что унести

БОР
вставка и поиск слова длины L          L переходов, от числа слов не зависит
слово есть в наборе                    путь существует И последний узел помечен
все слова с началом s                  поддерево узла, куда приводит s
самое длинное слово - начало строки    один спуск, помнить последний помеченный узел

13 команд, 41 буква → 27 узлов;   сжатый бор → 18 узлов

СУФФИКСНАЯ ССЫЛКА сына u узла v по символу c
k = ссылка v
пока k не корень и из k нет ребра c:   k = ссылка k
если из k есть ребро c:                ссылка u = конец этого ребра
иначе:                                 ссылка u = корень
сыновья корня → корень;   узлы обходятся В ШИРИНУ

ВЫХОДНАЯ ССЫЛКА
если суффиксная ссылка u ведёт в помеченный узел - она и есть выходная
иначе - выходная ссылка того узла (уже посчитана)

ПОИСК, один символ текста c
пока в узле нет ребра c и это не корень:   уйти по суффиксной ссылке
если ребро c есть:                         спуститься
сообщить слово узла (если помечен) и все слова по цепочке ВЫХОДНЫХ ссылок

Цена - три слагаемых: O(n + L + z). Текст n: не больше 2n переходов, от числа образцов не зависит. Образцы L: сумма их длин, один раз. Ответ z: число вхождений, может превысить оба.

z БЫВАЕТ БОЛЬШЕ ТЕКСТА
образцы a, aa, …, десять a;  текст - тысяча a:   1990 переходов, 9955 вхождений

НУЖНЫ ТОЛЬКО КОЛИЧЕСТВА
считать посещения узлов; потом в порядке, обратном обходу в ширину:
schet[ссылка u] += schet[u]        цена - текст плюс число узлов, без z

Ловушки джокера

Бор без пометок. Каждое начало каждого слова считается словом.

Массив сыновей на большой алфавит. Сто тысяч узлов над байтами - 25 миллионов ячеек.

Удаление слова сносом пути. Снимать пометку; узлы удалять с конца, пока нет сыновей и пометки.

Бор вместо множества. Для вопроса «есть ли слово целиком» хеш-таблица быстрее.

Ссылки обходом в глубину. Соседняя ветка ещё не обработана, ссылки выходят короче, вхождения теряются.

Сын корня ссылается на себя. Сыновей корня кладут в очередь отдельно, со ссылкой в корень.

Забыто условие «не корень» в цикле ухода. В корне без нужного ребра цикл не кончится.

Сообщается только слово своего узла. На rakursa найдено два слова из четырёх.

Цепочка суффиксных ссылок на каждом символе. 32 280 просмотренных узлов вместо 325.

Повторы в списке образцов. Второй номер затирает первый.

Конец вхождения принят за начало. Начало - i − d + 1.

Ожидание линейного времени при вложенных образцах. Время не меньше размера ответа.

Куда это ведёт

Во всех трёх главах готовился образец, а текст читался как есть. Так удобно, когда образцов мало, а текстов много. Обратная ситуация - один большой текст и тысячи запросов к нему: геном, архив журналов, корпус документов. Читать текст заново на каждый запрос нельзя. В следующей главе готовится сам текст: по нему строится индекс, после чего вопрос «есть ли такая подстрока» решается за время, зависящее от длины запроса, а не текста.