2.2. Алгоритм lzw

Алгоритм LZ78 существовал до 1984 года как математическая абстракция, пока не был усовершенствован Терри Уэлчем. Главной особенностью алгоритма LZW стало удаление второго поля из метки.

Суть LZW в том, что рабочий модуль первоначально должен инициализировать словарь из 256 символов (в общем случае 8-битного алфавита). Символы с номерами от 0 до 255 дадут нам полный набор наиболее часто используемых в текстах знаков, а также русский и английский алфавиты. Таким образом, первый символ сжимаемого текста совершенно точно будет найден в словаре, и метка может состоять всего лишь из указателя.

На следующем шаге второй символ группируется с первым в строку, и эта строка ищется в словаре. Если она там найдена, то процесс удлинения строки продолжается. Если же строка в словаре не найдена, то выполняется следующий набор действий:

1. В выходной файл записывается указатель на предыдущую строку;

2. В конец словаря записывается ненайденная строка;

3. Строка перестает удлиняться, и начинается работа со следующим символом.

Поясним на примере. Возьмем строку «топот_копыт» и попробуем сжать ее при помощи LZW.

Рабочая строка	Присутствие в словаре	Запись в словарь	Запись в выходной файл
т	есть	-	-
то	нет	256-то	226(т)
о	есть	-	-
оп	нет	257-оп	222(о)
п	есть	-	-
по	нет	258-по	223(п)
о	есть	-	-
от	нет	259-от	222(о)
т	есть	-	-
т_	нет	260-т_	226(т)
_	есть	-	-
_к	нет	261-_к	32(_)
к	есть	-	-
ко	нет	262-ко	218(к)
о	есть	-	-
оп	есть	-	-
опы	нет	263-опы	257(оп)
ы	есть	-	-
ыт	нет	264-ыт	235(ы)
т	есть	-	-
т, eof	нет	-	226(т)

Поясним этот пример. После инициализации словаря мы находим номер первого символа (226). Затем добавляем к нему следующий и видим, что такой строки (то) в словаре нет. Последний символ у нас 255, добавляем «то» под номером 256 в словарь и записываем в выходной файл указатель на «т» - 226. После чего начинаем все заново с символа «о». Если строка из двух символов есть в словаре, точно так же работаем со строкой из трех и более символов, в конце итерации рабочей строке все равно присваивается один символ. Последняя строка «т, eof» в словарь, естественно, не записывается.

Выходной файл будет выглядеть так: 226, 222, 223, 222, 226, 32, 218, 257, 235, 226.

2.2.1. Декодирование LZW

LZW очень удобен в плане декодирования. Особенность его в том, что кодер и декодер в состоянии работать синхронно. То есть, при поступлении на вход декодера закодированного файла он просто инициализирует словарь, смотрит по указателям, из которых состоит файл, номера символов в словаре и восстанавливает файл, исходя из этого.

Пошагово декодер работает так:

1. Вводится указатель, извлекается соответствующая строка I из словаря;

2. Строка записывается в выходной файл;

3. Из нее извлекается первый символ, и с предыдущей строкой J заносится в словарь на свободную позицию;

4. I перемещается в J.

Поясним работу декодера на нашем примере «топот_копыт». Первым символом входного файла является указатель 226. Он соответствует строке «т», которая извлекается по ссылке из словаря и записывается в разжатый файл. Следующий указатель – 222. Извлекается строка «о», записывается в выходной файл, а строка «о» добавляется к предыдущей, образуя строку «то», которая, также как и в кодере, добавляется на последнюю позицию. Таким образом декодер проходит до конца файла, расжимая текст обратно в «топот_копыт».

Резюмируя сказанное, представим достоинства и недостатки алгоритма LZW.

Достоинства:

1. Не требует вычисления вероятностей встречаемости символов или кодов.

2. Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

3. Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа.

Недостаток: Алгоритм не проводит анализ входных данных, поэтому не оптимален.

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода. Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Описание функционирования рабочего модуля

В данном разделе описывается построчное функционирование рабочего модуля алгоритма Хаффмана, выполненное в системе Wolfram Mathematica.

Первоначально для работы модуля требуется непосредственно задать кодируемый текст – он задается в виде списка.

Кодирование Хаффмана предполагает разбивку текста на символы. При помощи функций Flatten и Characters разобьем текст и выведем в виде переменной-списка символов.

Текст становится таким:

{"в", "о", "т", ",", " ", "и", "з", "в", "о", "л", "и", "т", "е", "

", "в", "и", "д", "е", "т", "ь", ",", " ", "т", "а", "к", " ", "н",

"а", "з", "ы", "в", "а", "е", "м", "а", "я", " ", "э", "в", "р", "и",

"с", "т", "и", "ч", "е", "с", "к", "а", "я", " ", "м", "а", "ш", "и",

"н", "а"}

Для начала необходимо определить частоту вхождения каждого символа в текст. В Mathematica это можно рассчитать с помощью функции Tally (количество копий элементов в списке). Для удобства работы отсортируем список при помощи функций Sort и Transpose:

Получим список:

{{1, "ш"}, {1, "ч"}, {1, "р"}, {1, "э"}, {1, "ы"}, {1, "ь"}, {1,

"д"}, {1, "л"}, {2, "с"}, {2, "я"}, {2, "м"}, {2, "н"}, {2,

"к"}, {2, "з"}, {2, ","}, {2, "о"}, {4, "е"}, {5, "т"}, {5,

"в"}, {6, "и"}, {6, " "}, {7, "а"}}

Приложение

Рабочий модуль кодирования Хаффмана, написанный в системе Wolfram Mathematica

Функции Wolfram Mathematica, используемые в программной реализации модуля

Функция	Назначение
Characters[“string”]	демонстрирует список символов строки
Flatten [list]	разъединяет вложенные символы
Sort[list]	сортирует элементы списка в определенном порядке
Tally[list]	Выводит количество копий элементов в списке
Transpose [list]	Транспонирует первые два уровня списка
Nest [f, expr,n]	Выводит f как функцию аргумента expr n раз
Delete [expr, n]	Удаляет элемент с n-ной позицией из expr
Take [list,n]	Выводит первые n элементов из списка
ReplacePart[expr, i->new]	Выводит выражение, в котором i-ый элемент заменен на new
Length[n]	Выводит длину n
Clear [symbol1, symbol2...]	Очистка символов
Cases[{e1,e2…}, pattern]	Выводит список элементов, соответствующих pattern
MapIndexed[f,expr]	Выводит все элементы expr как упорядоченные аргументы f
ToString[expr]	Выводит expr в виде строки
StringJoin [“s1”, “s2”…]	Объединяет s1 и s2 в одну строку
StringReplace[“string”, s->sp]	Заменяет в строке s на sp

Приложение

Рабочий модуль кодирования LZW, написанный в системе Wolfram Mathematica

decompress::bc="Bad compressed `1`";

decompress[compressed_]:=Module[{dictsize,dictionary,w,result,entry},dictsize=256;

dictionary=##&/@FromCharacterCode/@Range@dictsize;

w=result=compressed[[1]];

Do[Which[MemberQ[dictionary[[All,1]],k],entry=k/.dictionary,kdictsize,entry=w<>StringTake[w,1],True,Message[decompress::bc,k]];

result=result<>entry;

AppendTo[dictionary,dictsizew<>StringTake[entry,1]];

dictsize++;

w=entry,{k,compressed[[2;;]]}];

result];