Аппаратно-программные средства и методы защиты информации. Варлатая С.К - 271 стр.

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




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


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

                                     271