Сопоставляет перекрывающиеся взгляды на LZ77 / LZSS с суффиксными деревьями
Фон: У меня есть реализация универсального бэкэнда 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 с деревьями суффиксов, в которых упоминаются совпадения, перекрывающие буфер предварительного просмотра?
Решение
Насколько я понимаю, учитывая дерево суффиксов, мы (примерно) заинтересованы в вычислениях для каждого суффикса S, у которого более длинный суффикс имеет самый длинный общий префикс с S.
Добавьте ссылку с каждого узла дерева на лист-потомок с самым длинным суффиксом (линейное время с DFS). От каждого листа идите вглубь, изучая новые ссылки, останавливаясь, если найден более длинный суффикс. Время выполнения последнего шага линейно, потому что каждый край дерева проверяется ровно один раз.
Жизнь с ограниченным окном, к сожалению, сложнее. Вместо того, чтобы распространять одну ссылку, мы распространяем несколько. Чтобы вычислить набор суффиксов, на которые ссылается узел, мы объединяем их в отсортированном порядке по длине. Тогда всякий раз, когда у нас есть суффиксы длин x> y> z, если x — z < 8192 (например), тогда мы можем отбросить y, потому что все три одинаково хороши для всех суффиксов, с которыми текущий узел является самым общим общим предком, и если y находится в окне, то либо x, либо z есть. Поскольку окно является большой частью общего файла, каждый узел будет иметь не более нескольких ссылок.
Если вы хотите оглянуться назад на кратчайшее возможное расстояние, то существует алгоритм времени O (n log ^ 2 n) (вероятно, его невозможно улучшить до O (n log n) с помощью различных трудно реализуемых методов). В ходе работы алгоритма мы создаем для каждого узла двоичное дерево поиска суффиксов-потомков по длине, а затем выполняем следующие самые длинные поиски. Чтобы построить дерево узла из его дочерних, начните с самого большого дочернего дерева и вставьте элементы из других. По тяжелый путь аргумент, каждая длина вставляется O (log n) раз.
Другие решения