Суффиксное дерево: сжатый бор всех суффиксов

Если ты нарисуешь суффиксное дерево для abab$, объяснишь, зачем в конце текста символ $, и скажешь, как дерево связано с суффиксным массивом и LCP, - листай до «Теперь сам».

Как думаешь, сколько узлов в боре всех суффиксов

Бор умеет искать слово за его длину, не глядя на размер словаря. Возьмём текст из 10 000 символов и вставим в бор все его суффиксы. Тогда любой образец - начало какого-то суффикса - будет путём от корня, и поиск займёт m шагов.

Прежде чем читать дальше, прикинь, сколько узлов окажется в таком боре. Суффиксов 10 000, самый длинный - 10 000 символов, самый короткий - один. И второй вопрос: до какого числа это можно сжать, не потеряв ни одного пути?

На что это похоже

Представь схему метро. На настоящей линии между двумя пересадочными станциями может быть десяток обычных, но для вопроса «как проехать» важны только пересадки и конечные: между ними ты просто едешь, и выбора нет. Схему можно перерисовать, оставив одни пересадочные и конечные станции, а на перегонах написав «от такой-то до такой-то».

Маршрутов от этого не стало меньше, и ни один не потерян. Стало меньше точек: их число теперь зависит от количества развилок, а не от длины линий. Суффиксное дерево делает с бором суффиксов ровно это.

Механизм: развилки, листья и рёбра-индексы

Суффиксное дерево текста - сжатый бор всех его суффиксов. Узлы остаются только там, где путь ветвится, и там, где суффикс кончается. К тексту заранее дописывается символ $, которого в нём нет.

текст: banana$                              номер листа = начало суффикса

(корень)
   ├ $                                      лист 6
   ├ a ┬ $                                  лист 5
   │   └ na ┬ $                             лист 3
   │        └ na$                           лист 1
   ├ banana$                                лист 0
   └ na ┬ $                                 лист 4
        └ na$                               лист 2

Сыновья каждого узла нарисованы по алфавиту, и $ считается меньше любой буквы. Развилок четыре: корень и узлы a, ana, na. Листьев семь - по одному на суффикс. Всего 11 узлов на текст из семи символов.

Зачем $. Суффикс a - начало суффикса ana, а тот - начало anana. Без завершающего символа они лежали бы на одном пути и кончались посреди него, не получив своих листьев. С символом $ ни один суффикс не может быть началом другого: каждый кончается собственным листом.

Подписи на рёбрах - куски самого текста, поэтому хранить их строками не нужно. Ребро banana$ - это пара чисел «с 0 по 6». Любое ребро занимает два числа, какой бы длины ни была подпись. Если подпись встречается в тексте несколько раз, годится любое её вхождение. Отсюда и линейная память при квадратичной суммарной длине суффиксов.

Теперь прочитай листья слева направо: 6, 5, 3, 1, 0, 4, 2. Это суффиксный массив текста banana$. А глубины развилок - сколько символов от корня до узла: у a один, у ana три, у na два - это ненулевые значения его LCP. Дерево и пара «массив плюс LCP» - одна и та же информация, записанная по-разному.

Правило

У суффиксного дерева текста длины n (с завершающим символом) ровно n листьев и меньше n развилок: у каждой развилки не меньше двух сыновей, поэтому узлов всего меньше 2n. Образец входит в текст, если его можно прочитать от корня вниз по подписям рёбер; все его вхождения - листья под местом, где чтение кончилось, а число вхождений - число этих листьев. Поиск стоит m сравнений символов и не зависит от n. Листья в порядке обхода дают суффиксный массив, глубины развилок - значения LCP.

Разбор: читаем ответы с дерева

Образец ana. От корня: ребро a, затем ребро na - образец прочитан, стоим в развилке ana. Под ней два листа: 3 и 1. Вхождения с позиций 3 и 1, найдено за три сравнения.

Образец an. От корня ребро a, затем первый символ ребра na - образец кончился ПОСРЕДИ ребра. Это нормально: вхождения - листья под концом этого ребра, те же 3 и 1.

Образец nab. Ребро na прочитано, дальше из узла na выходят рёбра на $ и на n - ребра на b нет. Образец в текст не входит, и это выяснилось за три сравнения, а не за проход по тексту.

Самый длинный повтор - самая глубокая развилка: ana, глубина 3. Развилка означает, что строка продолжается в тексте хотя бы двумя разными способами, то есть встречается хотя бы дважды.

Число различных подстрок - суммарная длина всех подписей на рёбрах, не считая символов $: каждая точка на каждом ребре - отдельная подстрока.

Разбор: размер дерева по массиву LCP

Число развилок можно посчитать, не строя дерево: каждая развилка - это глубина, на которой расходятся соседние суффиксы. Идём по LCP и держим в стеке глубины развилок на текущем пути от корня.

def razvilok(lcp):
    stek = [0]                        # корень: глубина 0
    uzlov = 1
    i = 1
    while i < len(lcp):
        while stek[len(stek) - 1] > lcp[i]:
            stek.pop()                # эти развилки остались левее
        if stek[len(stek) - 1] < lcp[i]:
            stek.append(lcp[i])       # новая развилка на глубине lcp[i]
            uzlov = uzlov + 1         # при равенстве - та же развилка, ещё один сын
        i = i + 1
    return uzlov

print(razvilok([0, 0, 1, 3, 0, 0, 2]))        # LCP текста banana$: 4

Замер. Текст tekst(n, 4, 1) + "$": в первом столбце - длина без символа $, с ним на единицу больше, и листьев ровно столько. В последнем столбце - число узлов обычного, несжатого бора тех же суффиксов (оно равно числу различных подстрок плюс корень):

длина без $    листьев    развилок    всего узлов     несжатый бор
     1 000       1 001        617         1 618            497 349
    10 000      10 001      6 266        16 267         49 956 747

Последнее число - это 49 946 745 различных подстрок из прошлого урока, 10 001 подстрока с символом $ и корень.

Ответ на вопросы из начала урока: почти пятьдесят миллионов узлов против шестнадцати тысяч. Обычный бор суффиксов квадратичен, сжатый - линеен, и разница на десяти тысячах символов - три тысячи раз.

Строить дерево вставкой суффиксов по одному - квадратичное время. Линейные алгоритмы есть: Вайнера (1973), Мак-Крейта (1976) и Укконена (1995). Алгоритм Укконена читает текст слева направо и достраивает дерево по символу; ему помогают суффиксные ссылки между развилками - те же, что в алгоритме Ахо-Корасика, с той же ролью: не спускаться от корня заново. Второй путь - построить суффиксный массив и LCP, а дерево собрать по ним тем же стеком, что в razvilok.

Что ломается без этого

Первое: дерево без завершающего символа. В banana суффиксы a, ana, na кончаются посреди путей и листьев не получают. Под узлом a один лист вместо трёх, и подсчёт вхождений по листьям сообщает, что a встречается один раз.

Второе: строки на рёбрах. Если в ребре хранить подпись как строку, суммарный размер подписей квадратичен - на тексте в сто тысяч символов это гигабайты. Ребро хранит два индекса.

Третье: память на узел. Даже с индексами узел дерева - это ссылки на сыновей, границы ребра, суффиксная ссылка. Аккуратные реализации тратят 10-20 байт на символ текста, простые - больше пятидесяти. Суффиксный массив - четыре байта на символ, с LCP - восемь. Для генома разница между «помещается в память» и «не помещается».

Четвёртое: рекурсивный обход. У текста из одинаковых букв дерево - гребёнка глубиной n. Рекурсия на тексте в миллион символов упрётся в предел стека; обход пишут со своим стеком.

Зачем это в работе

Первый сюжет - время запроса, не зависящее от текста. Если запросов очень много, а образцы длинные, множитель log n у суффиксного массива заметен; дерево его убирает.

Второй - несколько текстов сразу. В одно дерево можно вставить суффиксы нескольких строк с разными завершающими символами. Тогда наибольшая общая подстрока - самая глубокая развилка, под которой есть листья обеих строк; для сотни строк задача решается тем же обходом. На таких деревьях построено сравнение геномов.

Третий - словарь идей. Суффиксное дерево - структура, в терминах которой сформулированы десятки результатов про строки; в книге Гасфилда ему отведена целая часть. В рабочем коде его чаще заменяет суффиксный массив с LCP - они знают то же самое и занимают меньше, - либо суффиксный автомат, родственная структура с числом узлов того же порядка и более коротким построением. Но объясняют все три через дерево.

Теперь сам

Нарисуй суффиксное дерево для текста abab$. Сколько в нём развилок, какие листья лежат под b и какая подстрока - самый длинный повтор?

(корень)
   ├ $                    лист 4
   ├ ab ┬ $               лист 2
   │    └ ab$             лист 0
   └ b ┬ $                лист 3
       └ ab$              лист 1