Сопоставляет перекрывающиеся взгляды на LZ77/LZSS с суффиксными деревьями

Question

Предыстория: у меня есть реализация универсального бэкэнда LZSS на C++ (доступно здесь. Алгоритм сопоставления, который я использую в этой версии, чрезвычайно прост, потому что он изначально предназначался для сжатия относительно небольших файлов (максимум 64 КБ) для относительно древнего оборудования (особенно, Mega Drive/Sega Genesis, где 64 КБ - это основная оперативная память).

Тем не менее, некоторые файлы слишком долго сжимаются в моей реализации, порядка нескольких минут. Причина двойная: наивный алгоритм сопоставления занимает большую часть времени, но это происходит именно потому, что я строю график сжатия из файла для достижения оптимального сжатия. Глядя на профилировщик, большую часть времени тратится на поиск совпадений, затмевая даже квадратичный размер результирующего графа.

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

Моя текущая реализация позволяет совпадениям в скользящем окне перекрывать буфер просмотра, так что этот вход:

aaaaaaaaaaaaaaaa

может быть непосредственно закодирован как

(0,'a')(1,0,15)

вместо

(0,'a')(1,0,1)(1,0,2)(1,0,4)(1,0,8)

Здесь (0, "a") означает кодирование символа "a" в качестве литерала, а (1,n,m) означает "скопировать m символов из позиции n".

Вопрос: сказав все это, вот моя проблема: каждый ресурс, который я нашел в деревьях суффиксов, похоже, подразумевает, что они не могут обрабатывать перекрывающийся регистр, а вместо этого позволяет только находить непересекающиеся совпадения. Когда использовались деревья суффиксов, исследовательские работы, книги и даже некоторые реализации давали примеры сжатия без наложения, как если бы они были идеальным сжатием (я бы ссылался на некоторые из них, но моя репутация не позволяет этого). Некоторые из них даже упоминали, что перекрытия могут быть полезны при описании базовых схем сжатия, но странно молчали об этом при обсуждении суффиксных деревьев.

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

Мой подход неправильный или неправильный? Есть ли реализация или обсуждение LZ77/LZSS с деревьями суффиксов, в которых упоминаются совпадения, перекрывающие буфер предварительного просмотра?

Answer 1

Насколько я понимаю, учитывая суффиксное дерево, мы (примерно) заинтересованы в вычислениях для каждого суффикса S, у которого более длинный суффикс имеет самый длинный общий префикс с S.

Добавьте ссылку с каждого узла дерева на лист-потомок с самым длинным суффиксом (линейное время с DFS). От каждого листа идите вглубь, изучая новые ссылки, останавливаясь, если найден более длинный суффикс. Время выполнения последнего шага линейно, потому что каждое ребро дерева проверяется ровно один раз.

Жизнь с ограниченным окном, к сожалению, сложнее. Вместо того, чтобы распространять одну ссылку, мы распространяем несколько. Чтобы вычислить набор суффиксов, на которые ссылается узел, мы объединяем их в отсортированном порядке по длине. Тогда всякий раз, когда у нас есть суффиксы длин x > y > z, если x - z < 8192 (например), мы можем отбросить y, потому что все три одинаково хороши для всех суффиксов, с которыми текущий узел является самым общим общим предком, и если у в окне, то либо х или г есть. Поскольку окно является большой частью общего файла, каждый узел будет иметь не более нескольких ссылок.

Если вы хотите оглянуться назад на самое короткое возможное расстояние, то существует алгоритм времени O(n log^2 n) (вероятно, его невозможно улучшить до O(n log n) с помощью различных трудно реализуемых методов). В ходе работы алгоритма мы строим для каждого узла двоичное дерево поиска суффиксов-потомков по длине, а затем выполняем следующие самые длинные поиски. Чтобы построить дерево узла из его дочерних, начните с самого большого дочернего дерева и вставьте элементы из других. С помощью аргумента с тяжелым путем каждая длина вставляется O(log n) раз.