1. Концепция суффиксного массива: математические и логические принципы
Введение в задачу поиска подстроки
Представьте, что перед вами стоит задача найти конкретное слово в полном собрании сочинений Льва Толстого или обнаружить специфический ген в цепочке ДНК, состоящей из миллиардов нуклеотидов. Классические алгоритмы поиска, такие как алгоритм Кнута-Морриса-Пратта или Бойера-Мура, отлично справляются с задачей, если текст меняется часто, а поиск выполняется редко. Однако в ситуациях, когда текст статичен (например, геном человека или база данных энциклопедии), а запросов на поиск поступает огромное количество, линейный проход по тексту каждый раз становится непозволительной роскошью.
Для решения этой проблемы текст предварительно индексируют. Исторически для этого применялось суффиксное дерево — мощная, но крайне «прожорливая» до оперативной памяти структура данных. Из-за необходимости хранить узлы, указатели на потомков и метаданные, суффиксное дерево потребляет объем памяти, многократно превышающий размер самого текста. Кроме того, узлы дерева разбросаны по оперативной памяти хаотично, что приводит к частым промахам в кэше процессора.
В 1990 году исследователи Юджин Майерс и Уди Манбер предложили элегантную альтернативу.
> Суффиксный массив — это лексикографически отсортированный массив всех суффиксов строки, который требует значительно меньше памяти, чем суффиксное дерево, но при этом позволяет выполнять большинство его функций с той же или сопоставимой асимптотической сложностью. > > Wikipedia
Математическая модель и логика структуры
Чтобы понять, как работает суффиксный массив, необходимо разобраться с базовыми терминами.
Пусть задана строка длины . Символы строки индексируются от до . Суффиксом строки , начинающимся в позиции , называется подстрока, которая начинается с символа под индексом и продолжается до самого конца строки. Обозначим такой суффикс как .
Рассмотрим классический пример — слово banana. Длина строки . Выпишем все её суффиксы вместе с их начальными индексами:
Если мы просто сохраним эти строки в массив, мы не получим никакого преимущества для поиска. Ключевая идея алгоритма заключается в лексикографической сортировке (сортировке по алфавиту) этих суффиксов.
Отсортируем суффиксы слова banana по алфавиту:
!Схема преобразования строки в суффиксный массив
Здесь кроется важнейший нюанс, определяющий эффективность структуры: мы не сохраняем сами отсортированные строки в память. Хранение строк потребовало бы памяти, что абсолютно неприемлемо для больших текстов. Вместо этого суффиксный массив хранит только начальные индексы этих суффиксов.
Таким образом, суффиксный массив для строки banana будет выглядеть как массив целых чисел: [5, 3, 1, 0, 4, 2].
Пространственная сложность такой структуры составляет ровно памяти, так как нам нужен лишь один массив целых чисел размером, равным длине исходного текста. Это делает суффиксный массив невероятно компактным и дружелюбным к кэшу процессора (данные лежат в памяти непрерывным блоком).
Механизм поиска подстроки (Наивный бинарный поиск)
Зачем нам понадобилось сортировать суффиксы? Ответ кроется в свойстве отсортированных данных: если какая-то подстрока (паттерн) встречается в тексте , то она обязательно является префиксом (началом) одного или нескольких суффиксов текста .
Поскольку суффиксы в нашем массиве отсортированы по алфавиту, все суффиксы, начинающиеся с одной и той же подстроки, будут располагаться в массиве строго подряд, образуя непрерывный блок.
Это позволяет использовать классический бинарный поиск для нахождения паттерна.
Допустим, мы ищем подстроку ana в слове banana. Наш суффиксный массив: [5, 3, 1, 0, 4, 2].
anana.ana с суффиксом anana. Паттерн ana является префиксом anana (совпадает начало). Мы нашли вхождение!Если бы паттерн был лексикографически меньше текущего суффикса, мы бы сдвинули правую границу (). Если больше — левую ().
!Интерактивная визуализация бинарного поиска
Анализ сложности наивного поиска
Оценим время работы такого алгоритма. Пусть длина текста равна , а длина искомого паттерна — .
Бинарный поиск по массиву размером требует итераций. На каждой итерации мы сравниваем искомый паттерн с текущим суффиксом. В худшем случае (когда строки почти совпадают) сравнение строк символ за символом займет операций.
Итоговая временная сложность наивного поиска составляет .
Для большинства практических задач это отличный показатель. Например, если мы ищем слово из букв в тексте из символов, алгоритму потребуется всего около итераций бинарного поиска, что в сумме даст не более сравнений символов. Линейный поиск потребовал бы миллион операций.
Оптимизация поиска: введение в LCP-массив
Несмотря на высокую скорость, наивный бинарный поиск имеет недостаток: он выполняет избыточные сравнения символов. Если на предыдущей итерации бинарного поиска мы уже выяснили, что паттерн совпадает с суффиксом по первым трем символам, а следующий проверяемый суффикс очень похож на предыдущий, мы всё равно начнем сравнение с первого символа.
Для устранения этой избыточности используется вспомогательная структура — LCP-массив (Longest Common Prefix — наибольший общий префикс).
LCP-массив хранит длины наибольших общих префиксов для соседних лексикографически отсортированных суффиксов. Математически это выражается так: хранит длину совпадающего начала у суффиксов, на которые указывают и .
Использование LCP-массива позволяет алгоритму «запоминать», сколько символов уже было успешно сопоставлено, и пропускать их при следующих сравнениях. Это снижает временную сложность поиска до . Детальное построение LCP-массива и алгоритм Касаи будут рассмотрены в следующих статьях курса, но понимание его роли важно уже на этапе проектирования архитектуры поиска.
Реализация наивного поиска на C++
Закрепим теоретическую базу академичным примером на языке C++. Мы реализуем функцию, которая принимает исходную строку, заранее построенный суффиксный массив и искомый паттерн, а затем возвращает true, если паттерн найден.
В современном C++ для работы с подстроками без лишнего копирования памяти идеально подходит std::string_view.
В этом коде left и right — указатели на границы суффиксного массива. Переменная mid вычисляется безопасным способом left + (right - left) / 2, чтобы избежать переполнения целочисленного типа при работе с огромными массивами. Использование std::string_view гарантирует, что при извлечении суффиксов не происходит выделения новой памяти, что сохраняет заявленную пространственную сложность .
Понимание математической природы суффиксного массива и механизма бинарного поиска по нему — это фундамент. В реальных задачах построение самого массива наивным способом (через std::sort) занимает времени, что недопустимо долго. Поэтому следующим логическим шагом в изучении этой структуры станет разбор алгоритмов её быстрого построения за и .