Алгоритм 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, "а"}}
Приложение