Алгоритм сжатия

Алгоритм сжатия для схемы LZ77 и его варианты используют два буфера.

Скользящий буфер предыстории содержит N символов источника, обработанных последними, а буфер упреждающей выборки содержит следующие L символов,

Рисунок 10.8 - Пример использования схемы LZ77

которые должны обрабатываться следующими (рис. 10.9(а)). Алгоритм пытается найти два или большее число символов из буфера упреждающей выборки в строке из скользящего буфера предыстории. Если совпадений не найдено, пер-вый символ из буфера упреждающей выборки выводится как 9-битовый символ, сам этот символ перемещается в скользящее окно, а самый старый символ из этого окна выталкивается. Если совпадение обнаружено, алгоритм продолжает просматривать символы в поиске совпадающей последовательности наибольшей длины. Затем совпадающая строка выводится в виде трех значений (индикатор, указатель, длина). Для строки из К символов самые старые К символов из скользящего окна выталкиваются, а К символов кодированной строки сдвигают-ся в это окно.

На рис. 10.9(6) показано действие этой схемы на последовательности из нашего примера. На иллюстрации изображено 39-символьное скользящее окно и 13-символьный буфер упреждающей выборки. В верхней части иллюстрации уже обработано 40 первых символов и последние 39 из них в несжатом виде находятся в скользящем окне. Остальная часть данных источника находится в буфере упреждающей выборки. Алгоритм сжатия определяет следующее повторение символов, перемещает пять символов из буфера упреждающей выборки в скользящее окно и выводит код соответствующей строки. Состояние буфера после этих действий показано в нижней части иллюстрации.

Схема LZ77 является эффективной и адаптирующейся к природе вводимых данных, и, тем не менее, она имеет определенные недостатки. Алгоритм использует ограниченное окно для поиска совпадений в предыдущем тексте. Для очень длинных блоков текста в сравнении с размерами окна много потенциальных совпадений будет проигнорировано. Размер окна может быть увеличен, но за это придется платить следующим: (1) увеличением времени выполнения алгоритма ввиду того, что необходимо выполнять сравнения строк из буфера упреждающей выборки с каждой позицией в скользящем окне и (2) увеличением длины поля <указатель> ввиду необходимости указывать более длинные переходы.