Программные методы защиты информации. Часть 1. Крыжановская Ю.А. - 28 стр.

                                        28
ния). Он формулируется следующим образом: "если в прошедшем ранее выход-
ном потоке уже встречалась подобная последовательность байт, причем запись о
ее длине и смещении от текущей позиции короче чем сама эта последователь-
ность, то в выходной файл записывается ссылка (смещение, длина), а не сама по-
следовательность". Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодиру-
ется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".
      Распространенный метод сжатия RLE (англ. Run Length Encoding), который
заключается в записи вместо последовательности одинаковых символов одного
символа и их количества, является подклассом данного алгоритма. Рассмотрим,
например, последовательность "ААААААА". С помощью алгоритма RLE она бу-
дет закодирована как "(А,7)", в то же время ее можно достаточно хорошо сжать и
с помощью алгоритма LZ77: "А(-1,6)". Действительно, степень сжатия именно
такой последовательности им ниже (примерно на 30-40%), но сам по себе алго-
ритм LZ77 более универсален и может намного лучше обрабатывать последова-
тельности вообще несжимаемые методом RLE.
      Суть метода Лемпеля-Зива состоит в следующем: упаковщик постоянно
хранит некоторое количество последних обработанных символов в буфере. По
мере обработки входного потока вновь поступившие символы попадают в конец
буфера, сдвигая предшествующие символы и вытесняя самые старые.
      Размеры этого буфера, называемого также скользящим словарем (sliding
dictionary), варьируются в разных реализациях кодирующих систем.
      Экспериментальным путем установлено, что программа LHarc использует
4-килобайтный буфер, LHA и PKZIP - 8-ми, а ARJ - 16-килобайтный.
      Затем, после построения хеш-таблиц, алгоритм выделяет (путем поиска в
словаре) самую длинную начальную подстроку входного потока, совпадающую с
одной из подстрок в словаре, и выдает на выход пару (length, distance), где length
- длина найденной в словаре подстроки, а distance - расстояние от нее до входной
подстроки (то есть фактически индекс подстроки в буфере, вычтенный из его
размера). В случае, если такая подстрока не найдена, в выходной поток просто
копируется очередной символ входного потока.
      В первоначальной версии алгоритма предлагалось использовать простей-
ший поиск по всему словарю. Однако, в дальнейшем, было предложено исполь-
зовать двоичное дерево и хеширование для быстрого поиска в словаре, что по-
зволило на порядок поднять скорость работы алгоритма.
      Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных
символов в два параллельных потока длин и индексов в таблице (length+distance).
      Очевидно, что эти потоки являются потоками символов с двумя новыми
алфавитами и к ним можно применить один из упоминавшихся выше методов
(RLE, кодирование Хаффмана или арифметическое кодирование).
      Так мы приходим к схеме двухступенчатого кодирования - наиболее эф-
фективной из практически используемых в настоящее время. При реализации
этого метода необходимо добиться согласованного вывода обоих потоков в один
файл. Эта проблема обычно решается путем поочередной записи кодов символов
из обоих потоков.