Суффиксное дерево: алгоритм Укконена простыми словами

Суффиксное дерево: сжатый бор всех суффиксов, наивное построение за O(n²), идея алгоритма Укконена за O(n), задачи о подстроках и сравнение с суффиксным массивом и автоматом.

13 мин чтенияалгоритмы · строки · деревья · python

Коротко

ПараметрЗначение
ПостроениеO(n) алгоритмом Укконена (наивно — O(n²))
Узловне больше 2n (n + 1 листьев и не больше n внутренних)
Поиск подстроки длины mO(m)
ПамятьO(n), но с большой константой
  • Суффиксное дерево — это бор из всех суффиксов строки, в котором цепочки без ветвлений сжаты в одно ребро.
  • Каждая подстрока — путь от корня, поэтому поиск подстроки, количество различных подстрок и самая длинная повторяющаяся подстрока решаются обходом дерева.
  • Алгоритм Укконена строит дерево онлайн за линейное время за счёт трёх приёмов: «однажды лист — навсегда лист», суффиксные ссылки и прыжки по рёбрам.
  • На практике его часто заменяют суффиксным массивом или суффиксным автоматом — они проще и экономнее.

От бора к суффиксному дереву

Возьмём строку banana и выпишем все её суффиксы: banana, anana, nana, ana, na, a. Любая подстрока — это префикс какого-то суффикса. Значит, если сложить все суффиксы в префиксное дерево (бор), каждая подстрока станет путём от корня.

Проблема в размере. Суммарная длина суффиксов — n(n + 1)/2, и бор для строки длины n может содержать Θ(n²) узлов. Для строки в миллион символов это неприемлемо.

Решение — сжатие. В боре много узлов с единственным ребёнком: длинные «бамбуковые» цепочки. Заменим каждую такую цепочку одним ребром, подписанным строкой. А саму строку хранить не будем — только пару индексов [start, end) в исходном тексте. Получается суффиксное дерево.

Зачем символ-терминатор

Если один суффикс — префикс другого, он «растворится» внутри ребра и не получит своего листа. В banana суффикс a — префикс ana и anana. Чтобы каждый суффикс заканчивался в собственном листе, к строке приписывают уникальный символ, обычно $.

Для banana$ дерево выглядит так (рядом с листом — позиция начала суффикса):

корень
├── $              (6)
├── a
│   ├── $          (5)
│   └── na
│       ├── $      (3)
│       └── na$    (1)
├── banana$        (0)
└── na
    ├── $          (4)
    └── na$        (2)

Семь листьев — по одному на суффикс banana$, три внутренних узла: a, ana, na. Каждый внутренний узел ветвится хотя бы на два ребёнка, поэтому внутренних узлов меньше, чем листьев. Отсюда линейная оценка размера: не больше n + 1 листьев и n внутренних узлов, а рёбра хранятся как пары индексов.

Наивное построение за O(n²)

Вставляем суффиксы по одному, от самого длинного. Для каждого спускаемся от корня, пока символы совпадают. Где разошлись — либо добавляем новый лист из узла, либо расщепляем ребро и вешаем лист на новый внутренний узел.

def build_naive(text): s = text + '$' root = {} # первый символ ребра -> [start, end, children] for i in range(len(s)): node, j = root, i while True: edge = node.get(s[j]) if edge is None: node[s[j]] = [j, len(s), {}] break start, end, child = edge k = 0 while k < end - start and s[start + k] == s[j + k]: k += 1 if k == end - start: node, j = child, j + k continue # расщепляем ребро в точке k mid = {s[start + k]: [start + k, end, child]} node[s[j]] = [start, start + k, mid] mid[s[j + k]] = [j + k, len(s), {}] break return s, root

Дерево на выходе уже линейного размера, но время — O(n²): каждый суффикс посимвольно сравнивается с тем, что уже в дереве. Для строк до нескольких тысяч символов этого хватает, и на собеседовании разумно начать именно с такого кода.

Идея алгоритма Укконена

Исторически линейное построение придумал Питер Вайнер в 1973 году, потом его упростил Эдвард Маккрейт (1976). Самый популярный вариант — алгоритм Эско Укконена (1995): он строит дерево онлайн, читая строку слева направо, и после каждого символа у нас есть корректное дерево для прочитанного префикса.

Фазы и продления

Наивно онлайн-построение выглядит так: в фазе i читаем символ s[i] и продлеваем им все суффиксы префикса s[0..i-1]. Каждое продление — один из трёх случаев:

  1. Суффикс заканчивается в листе. Просто удлиняем ребро листа на один символ.
  2. Суффикс заканчивается внутри дерева, и дальше нет символа s[i]. Создаём новый лист; если конец пришёлся на середину ребра — сначала расщепляем ребро.
  3. Продолжение s[i] уже есть. Ничего не делаем: суффикс уже присутствует в дереве неявно.

Фаз n, в каждой до n продлений, каждое требует спуска от корня — это O(n³). Укконен убирает лишнее в три шага.

Приём 1: однажды лист — навсегда лист

Правило 1 — самое частое и самое бессмысленное: удлинять каждый лист по отдельности. Заметим, что ребро листа всегда тянется до текущего конца строки. Значит, вместо конкретного end листья могут хранить ссылку на один общий счётчик. Увеличили его на единицу — и все листья удлинились за O(1).

В коде ниже это leaf_end = [0]: все листья ссылаются на один и тот же список.

Приём 2: правило 3 останавливает фазу

Если суффикс s[j..i] уже есть в дереве, то и все более короткие суффиксы s[j+1..i], s[j+2..i]... тоже есть — они ведь подстроки уже имеющейся строки. Поэтому, как только сработало правило 3, фазу можно закончить.

Получается, что в каждой фазе работа идёт только над «средними» суффиксами: длинные уже стали листьями (приём 1), короткие уже есть в дереве (приём 2). Число таких ожидающих суффиксов хранят в переменной remainder, а точку, куда вставлять следующий, — в тройке active point: (active_node, active_edge, active_len).

Приём 3: суффиксные ссылки и прыжки по рёбрам

После вставки суффикса xα нужно перейти к суффиксу α. Спуск от корня стоил бы O(n). Вместо этого у каждого внутреннего узла xα хранится суффиксная ссылка на узел α. Переходим по ней и спускаемся только на остаток.

Спуск тоже ускоряем: мы знаем, что строка в дереве есть, поэтому сравнивать символы не нужно. Смотрим на длину ребра: если она меньше оставшегося пути, прыгаем через ребро целиком (skip/count). Это O(1) на ребро вместо O(длины ребра).

Амортизированный анализ показывает, что суммарно на всех фазах набегает O(n) операций. Строгое доказательство громоздкое; интуитивно — remainder увеличивается на единицу за фазу и уменьшается при каждой вставке листа, а глубина active point не может расти быстрее, чем на один символ за фазу.

Реализация

Код ниже — рабочий Укконен примерно на 60 строк. Я проверил его на трёх тысячах случайных строк, сравнивая число различных подстрок, поиск и самую длинную повторяющуюся подстроку с перебором, а также с наивным построением. Строка из 200 000 символов строится примерно за 0,6 секунды на CPython.

class Node: __slots__ = ('start', 'end', 'children', 'link') def __init__(self, start, end): self.start = start self.end = end # у листьев — общий список leaf_end self.children = {} self.link = None def build_suffix_tree(text): s = text + '$' n = len(s) leaf_end = [0] # «глобальный конец»: все листья растут одновременно root = Node(-1, -1) root.link = root active_node, active_edge, active_len = root, 0, 0 remainder = 0 def edge_len(node): end = node.end[0] if isinstance(node.end, list) else node.end return end - node.start for i in range(n): leaf_end[0] = i + 1 # правило 1: продлили все листья remainder += 1 last_internal = None while remainder > 0: if active_len == 0: active_edge = i ch = s[active_edge] nxt = active_node.children.get(ch) if nxt is None: # правило 2: новый лист прямо из active_node active_node.children[ch] = Node(i, leaf_end) if last_internal: last_internal.link = active_node last_internal = None else: length = edge_len(nxt) if active_len >= length: # skip/count: перепрыгиваем ребро active_node = nxt active_edge += length active_len -= length continue if s[nxt.start + active_len] == s[i]: # правило 3: символ уже есть — фаза окончена if last_internal and active_node is not root: last_internal.link = active_node active_len += 1 break # правило 2 с расщеплением ребра split = Node(nxt.start, nxt.start + active_len) active_node.children[ch] = split split.children[s[i]] = Node(i, leaf_end) nxt.start += active_len split.children[s[nxt.start]] = nxt if last_internal: last_internal.link = split last_internal = split remainder -= 1 if active_node is root and active_len > 0: active_len -= 1 active_edge = i - remainder + 1 elif active_node is not root: active_node = active_node.link or root return s, root, edge_len

Ключевые места:

  • leaf_end[0] = i + 1 — приём 1, все листья удлиняются разом.
  • break в ветке правила 3 — приём 2, фаза заканчивается.
  • active_node.link и ветка active_len >= length — приём 3.
  • last_internal — только что созданный внутренний узел, которому нужно проставить суффиксную ссылку на следующем шаге.

Что решает суффиксное дерево

Поиск подстроки за O(m)

Спускаемся от корня по символам образца. Не нашлось ребра или символ не совпал — подстроки нет.

def contains(s, root, edge_len, pattern): node, i = root, 0 while i < len(pattern): child = node.children.get(pattern[i]) if child is None: return False length = min(edge_len(child), len(pattern) - i) if s[child.start:child.start + length] != pattern[i:i + length]: return False i += length node = child return True

Дерево строится один раз за O(n), а потом каждый запрос отвечает за длину образца — независимо от длины текста. Число вхождений равно числу листьев в поддереве, где закончился спуск, позиции — метки этих листьев.

Количество различных подстрок

Каждая различная подстрока — ровно одна точка на рёбрах дерева. Значит, их количество равно сумме длин всех рёбер. Из неё вычитаем подстроки, содержащие $: их ровно n + 1.

def count_distinct_substrings(s, root, edge_len): total = 0 stack = list(root.children.values()) while stack: node = stack.pop() total += edge_len(node) stack.extend(node.children.values()) return total - len(s)

Для banana получается 15.

Самая длинная повторяющаяся подстрока

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

def longest_repeated(s, root, edge_len): best = '' stack = [(child, '') for child in root.children.values()] while stack: node, path = stack.pop() if not node.children: continue # лист: подстрока встречается один раз path += s[node.start:node.start + edge_len(node)] if len(path) > len(best): best = path stack.extend((child, path) for child in node.children.values()) return best

banana → ana, mississippi → issi.

Наибольший общий префикс двух суффиксов

Это строка-метка их наименьшего общего предка в дереве. С предподсчётом LCA за O(1) на запрос получается LCP любых двух суффиксов за O(1). Тот же трюк лежит в основе задач о максимальных палиндромах и сравнении подстрок.

Обобщённое суффиксное дерево

Склеиваем несколько строк через разные разделители: s1#s2$. Внутренний узел, под которым есть листья из обеих строк, задаёт их общую подстроку. Самый глубокий такой узел — наибольшая общая подстрока за линейное время. Задача о наибольшем общем префиксе массива строк — частный случай: там нужен самый глубокий узел на пути, общем для всех строк.

Сравнение с суффиксным массивом и автоматом

Суффиксное деревоСуффиксный массив + LCPСуффиксный автомат
ПостроениеO(n), УкконенO(n log n) удвоениемO(n) онлайн
ПамятьO(n), большая константаO(n), несколько int на символO(n·алфавит) в худшем случае
Поиск подстрокиO(m)O(m log n)O(m)
Различные подстрокисумма длин рёберn(n+1)/2 − ΣLCPсумма по состояниям
Онлайн-добавлениеданетда
Сложность кодавысокаянизкаясредняя

Как выбирать:

  • Суффиксный массив — выбор по умолчанию в олимпиадах и на практике: 30 строк кода, мало памяти, а пара «массив + LCP» эмулирует почти любой обход суффиксного дерева. Подробно — в статье про суффиксный массив.
  • Суффиксный автомат — когда строка приходит онлайн или нужны задачи про подстроки вроде количества вхождений и различных подстрок. Код компактнее Укконена. См. статью о суффиксном автомате.
  • Суффиксное дерево — когда нужна именно древовидная структура: LCA-запросы, обобщённое дерево для многих строк, алгоритмы из биоинформатики. Многие классические результаты в этой области формулируются через суффиксные деревья.

Отдельно стоит помнить о памяти. В учебной реализации на Python каждый узел — объект со словарём, и это сотни байт. Даже в оптимизированных реализациях на C суффиксное дерево занимает в разы больше памяти, чем суффиксный массив, — поэтому в индексаторах генома и полнотекстовом поиске чаще используют массивы и сжатые индексы.

Частые ошибки

Забытый терминатор. Без $ часть суффиксов не получает листьев, и подсчёты по листьям врут. Терминатор должен быть символом, которого нет в строке.

Листья с фиксированным концом. Если при создании листа записать end = i + 1 числом, а не ссылкой на общий счётчик, листья перестанут расти, и дерево окажется неверным. Это самая частая ошибка при переписывании Укконена с нуля.

Неправильный сдвиг active point после вставки из корня. Когда active_node — корень, нужно уменьшить active_len и сдвинуть active_edge на следующий ожидающий суффикс. Пропуск этого шага ломает дерево только на некоторых строках — поэтому тестируйте на периодических строках вроде abab... и aaaa....

Суффиксная ссылка не проставлена. Каждому новому внутреннему узлу ссылка ставится на следующем шаге той же фазы. Если забыть, алгоритм может откатываться в корень — результат часто верный, но время перестаёт быть линейным.

Подсчёт длины по символам. Если сравнивать символы при спуске по уже известному пути вместо skip/count, сложность деградирует.

На собеседовании

Укконена на обычном собеседовании писать не просят — даже компактная версия занимает полсотни строк с тонкими инвариантами, и ошибиться в них легко. Зато могут спросить:

  • что такое суффиксное дерево и почему у него O(n) узлов;
  • как с его помощью найти подстроку, самую длинную повторяющуюся подстроку или наибольшую общую подстроку двух строк;
  • чем его заменить на практике и почему суффиксный массив обычно выгоднее.

Достаточно уверенно объяснить сжатие бора, терминатор и три приёма Укконена на уровне идей. Если всё же попросят код, разумно начать с наивного построения за O(n²) и честно оговорить, как довести его до линейного.

Что запомнить

  • Суффиксное дерево — сжатый бор всех суффиксов s$; рёбра хранятся парами индексов, узлов O(n).
  • Любая подстрока — путь от корня; поиск за O(m), различные подстроки — сумма длин рёбер.
  • Укконен строит дерево онлайн за O(n): общий конец для листьев, остановка фазы на правиле 3, суффиксные ссылки и прыжки по рёбрам.
  • На практике чаще берут суффиксный массив или автомат: меньше памяти и кода.

Потренироваться в спокойной обстановке

Все задачи