Вопреки сказанному в предыдущем ответе, вы можете не только сжимать суффиксные массивы, но на самом деле сжатие суффикса дерева обычно осуществляется сначала путем эмуляции дерева с использованием массива суффиксов, а затем сжатия этого.
Мне неизвестно о какой-либо готовой реализации Java сжатия суффиксных массивов, и различные существующие алгоритмы слишком сложны, чтобы описывать их здесь подробно.Существует документ , составленный Наварро и Мякиненом (DOI 10.1145 / 1216370.1216372), в котором содержатся подробные описания и сравнения.
Но, в широком смысле, существует два основных подхода :
Подход A: Уменьшение размера массива напрямую (см. Раздел 7.1 документа).Это включает в себя сохранение только некоторых записей массива суффиксов и интерполяцию пропущенных при необходимости.Интерполяция выполняется с использованием функции (называемой the на бумаге), которая сама хранится в виде большого массива (но не такого большого размера, как исходный суффиксный массив) и индексированного битового вектора.
Подход B: Подход FM (см. Раздел 9 документа).Здесь суффиксный массив в основном заменяется на относительно короткий массив C , который указывает начальные позиции (в массиве суффиксов) основных лексикографических сегментов (то есть групп суффиксов, начинающихся с одного и того же начального символа) в сочетании сдругая относительно большая структура данных Occ , которая обеспечивает так называемый обратный поиск .В частности, учитывая шаблон поиска p = c 1 .. c m , он позволяет итеративно сужать область для символа c m до меньшей областидля строки с м-1 с м , а затем далее в ведро для с м-2 с м-1 с m и так далее, пока не будет найден окончательный диапазон для полного шаблона p.Структура данных Occ , которая позволяет это, является большой, но сжимаемой с использованием различных методов, в частности деревьев вейвлетов .
Влияние на производительность поиска
Приведенный выше документ содержит тщательный анализ и сравнение.Но, опять же, в широком смысле, сжатие суффиксного массива приведет к тому, что поиск шаблона длины m (который может быть O (m) в несжатом суффиксном массиве, если тщательно реализован) будет задержан на коэффициент, который зависит от (обычнологарифмически) по длине всего текста .Кроме того, любой подход, использующий вейвлет-деревья, означает дополнительную зависимость от размера алфавита .