Распаковка

Сжатие

Алгоритмы LZ78 и LZW

Алгоритм распаковки

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

Алгоритмы LZ78 и LZW пытаются обойти ограничения схемы LZ77, вместо огра­ниченного окна создавая словари. Как и схема LZ77, алгоритм LZW (и LZ78) поддерживает словарь строк вместе с их кодами как для сжатия, так и для распаковки. Когда любая строка словаря по­является на входе алгоритма сжатия, эта строка заменяется кодом. Распаковщик, наоборот, заменяет коды соответствующими им строками. По мере работы алго­ритма сжатия к словарю добавляются новые строки.

В любой момент времени словарь содержит все односимвольные строки плюс некоторые многосимвольные строки. Механизм работает так, что любые ведущие подстроки присутствующей в словаре строки также могут использоваться в каче­стве элементов словаря. Например, если в словаре есть строка MEOW, снабжен­ная своим уникальным кодовым словом, тогда строки МЕО и ME также присут­ствуют в словаре и у каждой есть свое уникальное кодовое слово. Логически словарь может быть представлен в виде набора деревьев, при этом корень каждого дерева соответствует символу алфавита. Таким образом, по умол­чанию имеется 256 деревьев (все возможные 8-битовые символы). Далее будет более детально описан алгоритм, имеющий много общего со стан­дартом V.42bis и схемами LZ78 и LZW.

Прежде чем перейти к описанию алгоритма, введем следующие обозначения:

· С₁ — следующее доступное неиспользуемое кодовое слово;

· С₂ — размер кодового слова, по умолчанию 9 бит;

· N₂ — максимальный размер словаря, равный количеству кодовых слов ( 2^C₂);

· N₃ — размер символа, по умолчанию 8 бит;

· N₅ — первое кодовое слово, используемое для обозначения строки из более
чем одного символа;

· N₇ — максимальная длина строки, которая может быть закодирована.

Алгоритм сжатия реализует три основные действия:

· поиск совпадений строк и кодирование;

· добавление новых строк к словарю;

· удаление старых строк из словаря.

Алгоритм всегда ищет в словаре строку максимальной длины, совпадающую с входной строкой. Передатчик разбивает входной поток на строки, присутствую­щие в словаре, и преобразует каждую строку в соответствующее кодовое слово. Поскольку все односимвольные строки уже находятся в словаре, весь входной по­ток может быть разбит на строки, присутствующие в словаре. Приемник прини­мает поток кодовых слов и преобразует каждое кодовое слово в соответствующую символьную строку. Алгоритм всегда ищет новые строки, которые можно добавить к словарю, а так­же заменить ими старые строки, которые вряд ли встретятся в будущем. Процедура выглядит следующим образом:

1. Входные символы обрабатываются, чтобы получить совпадающие строки
большей длины.

2. Если совпадающая строка имеет максимальную длину (N₇ символов), тогда
алгоритм передает код для этой строки и переходит к шагу 1.

3. В противном случае к совпадающей строке добавляется следующий символ,
а сама строка добавляется к словарю и ей назначается код. Однако посколь­
ку эта строка еще отсутствует в словаре получателя, алгоритм передает код
оригинальной строки и использует оставшийся символ, чтобы опять начать
с шага 1.

Процедура добавления новой строки к словарю зависит от того, является ли словарь полным или нет. В любом случае передатчик хранит переменную С₁ пред­ставляющую собой значение следующего доступного кодового слова. При иници­ализации системы переменной С₁ присваивается значение N₅ , которое представ­ляет собой следующее значение, после того как всем односимвольным строкам присвоены значения. Таким образом, по умолчанию значение С₁ начинается с 256. До тех пор пока словарь пуст, при определении каждой новой строки ей назнача­ется код С₁ и этот код увеличивается на единицу.

Когда словарь полон, при определении новой строки ей назначается кодовое значение С₁ затем выполняется следующая процедура:

1. С₁ увеличивается на единицу.

2. Если значение С₁ равно максимальному размеру словаря N₂, оно устанавливается равным N₅. To есть как только величина С₁ достигает своего макси­мального значения, она снова устанавливается равной минимальному зна­чению.

3. Если узел, идентифицируемый значением С₁, не является листовым узлом,
тогда выполняется переход к шагу 1.

4. Если узел является листовым узлом, тогда он удаляется из словаря.

В конце этой процедуры в словаре появляется место для новой записи, а С₁ представляет собой неиспользуемый код, присваиваемый этой записи. Теперь си­стема готова к определению следующей новой строки словаря.

Рисунок нижеиллюстрирует работу алгоритма сжатия, для которого использу­ется трехсимвольный алфавит. Вначале в словаре находятся только односимволь­ные строки (верхняя часть таблицы). Входные данные считываются слева направо. Поскольку в таблице нет совпадающих строк длиннее а, для этой строки выводится код 1, а к таблице добавляется новая строка ab, которой назначается код 4. Затем для начала новой строки используется символ b. Поскольку строки bа нет в словаре, она добавляется в словарь с кодом 5, а в выходной поток направля­ется символ b. Процесс продолжается подобным образом.

В таблице показан словарь, формируемый в данном примере. Более компакт­ный метод хранения иллюстрирует правая часть таблицы, в которой каждая стро­ка представляется в виде префиксного кода строки и последнего символа. При та­ком представлении все многосимвольные элементы словаря имеют равную длину.

Такое представление также предполагает структуру словаря, состоящую из не­скольких деревьев, как показано на рисунке.

Интересный аспект работы семейства алгоритмов LZ78 заключается в том, что словарь не передается явно алгоритму распаковки. Вместо этого алгоритм распа­ковки создает идентичный словарь в процессе распаковки. Это возможно благо­даря тому, что при распаковке строка, соответствующая коду, всегда встречается прежде самого кода.

Нижняя часть рисунка, описывающего процесс кодированияиллюстрирует процесс распаковки. Каждый встреченный код преобразуется в соответствующую символьную строку. Между тем, выходной по­ток используется для создания новых элементов словаря по тем же правилам, что и в алгоритме сжатия.