Алгоритм поиска совпадений строк в скользящем окне

Одним из основных шагов в сжатии файлов, таких как ZIP, является использование предыдущего декодированного текста в качестве справочного источника. Например, закодированный поток может сказать: «Следующие 219 выходных символов такие же, как символы из декодированного потока 5161 байт назад». Это позволяет представить 219 символов всего тремя байтами или около того. (В ZIP есть нечто большее, чем сжатие Хаффмана, но я говорю только о сопоставлении ссылок.)

Мой вопрос заключается в том, что такое стратегия (и) для алгоритма сопоставления строк. Даже просмотр исходного кода из zlib и тому подобного не дает хорошего описания алгоритма сопоставления сжатия.

Задачу можно сформулировать так: при заданном блоке текста, скажем, 30 КБ, и входной строке найдите самую длинную ссылку в 30 КБ текста, которая точно соответствует началу входной строки». Алгоритм должен быть эффективным при повторении, т. е. 30-килобайтный блок текста будет обновляться путем удаления некоторых байтов спереди и добавления новых байтов сзади и выполнения нового сопоставления.

Меня гораздо больше интересуют обсуждения алгоритма (алгоритмов) для этого, не исходного кода или библиотек. (у zlib очень хороший исходный код!) Я подозреваю, что может быть несколько подходов с разными компромиссами.


zip gzip compression algorithm
person SPWorley    schedule 13.03.2009    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Вы можете ознакомиться с деталями алгоритма LZMA, используемого 7-zip. Автор 7-zip утверждает, что улучшил алгоритм, используемый zlib et al.

person Michael Kristofik    schedule 13.03.2009

arrow_upward
3
arrow_downward

Что ж, я заметил, что вы подробно описываете проблему, но не упоминаете информацию, представленную в разделе 4 RFC 1951 (спецификация формата сжатых данных DEFLATE, т. е. формата, используемого в ZIP), что наводит меня на мысль, что вы могли пропустить этот ресурс.

Их основной подход — цепочка хеш-таблиц с использованием трехбайтовых последовательностей в качестве ключей. Пока цепочка не пуста, все записи в ней сканируются, чтобы а) исключить ложные коллизии, б) исключить слишком старые совпадения и в) выбрать самое длинное совпадение из оставшихся.

(Обратите внимание, что их рекомендации формируются с учетом патентов; может быть, они знали о более эффективной методике, но не могли быть уверены, что она не защищена чьим-то патентом. Лично меня всегда удивляло, почему нельзя найдите самые длинные совпадения, проверив совпадения для трехбайтовых последовательностей, которые начинаются со второго байта входящих данных, третьего байта и т. д., и отсеяв совпадения, которые не совпадают, т. е. если ваши входящие данные " ABCDEFG...", и у вас есть хеш-совпадения для "ABC" по смещениям 100, 302 и 416, но ваше единственное совпадение хэша для "BCD" находится по смещению 301, вы знаете, что если у вас нет двух полностью совпадающих совпадений хэшей - - маловероятно - тогда 302 - это ваше самое длинное совпадение.)

Также обратите внимание на их рекомендацию по дополнительному «ленивому сопоставлению» (которое по иронии судьбы делает больше работы): вместо автоматического поиска самого длинного совпадения, которое начинается с первого байта входящих данных, компрессор проверяет еще более длинное совпадение, начинающееся со следующего байта. Если ваши входящие данные - "ABCDE...", а ваши совпадения в скользящем окне - только для "ABC" и для "BCDE", вам лучше кодировать "A" как буквальный байт, а "BCDE" как матч.

person afeldspar    schedule 22.03.2009

arrow_upward
2
arrow_downward

Я думаю, вы описываете модифицированную версию самой длинной общей подстроки.

person Jason Punyon    schedule 13.03.2009
comment
Да, это очень связано. Большое (и решающее) отличие заключается в том, что совпадение повторяется буквально миллионы раз, каждый раз с новой уникальной исходной строкой (от скольжения предыдущего источника в новое окно). - person SPWorley; 13.03.2009