Метод LZW-сжатия данных (стр. 2 )

Входная строка : ...JOEYNJOEYNJOEY...

Вход(символы)	Выход(коды)	Новые коды и соотв. строки
JOEYN	288 = JOEY	300 = JOEYN
A	N	301 = NA
.	.	.
.	.	.
.	.	.
JOEYNJ	300 = JOEYN	400 = JOEYNJ
JOEYNJO	400	401 = JOEYNJO

Рис. 5 Некоторые проблемы

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.
Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА = перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 6 Модифицированный алгоритм распаковки

Реализация

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.
Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.
Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ "E". Наконец, код 256 хранится как "/" плюс "W".
Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов : code_value[i], prefix_code[i] и append_character[i].
Когда необходимо добавить новый код в таблицу, используется хэшфункция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.
Хэш-функция, использованная в этой программе - простая "xor"-типа хэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице - меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.
Реализация алгоритма распаковки имеет свой набор проблем. Одна из проблем алгоритма сжатия здесь исчезает. Когда выполняется сжатие, необходимо организовать поиск в таблице для данной строки. При распаковке необходимо организовать просмотр для отдельного кода. Это означает, что можно хранить префиксы кодов и добавочные символы, индексируясь по их строковому коду. Это устраняет необходимость в хэш-функции и освобождает массив, использовавшийся для хранения значений кодов.

К сожалению метод, использованный для хранения строковых величин, приводит к тому, что декодировка строк должна выполняться в инверсном порядке. Это значит, что все символы для данной строки при декодировании должны помещаться в стековый буфер, а затем выводиться в обратном порядке. В приведенной программе это выполняется функцией decode_string.
Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.

Результаты

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.
Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях "сжатый" файл может превосходить по своим размерам исходный текст. Небольшой эксперимент даст Вам представление о том, хорошо или плохо упаковываются Ваши данные.

Ваша реализация

Программа, приведенная в статье, является рабочей. Она была написана, однако, с иллюстративной целью и не очень эффективна. Например, процедуры, организующие входные и выходные потоки, невелики по размерам и легки для понимания, но увеличивают накладные расходы. Вы можете попробовать увеличить скорость программы, совершенно переписав эти процедуры с использованием кодов фиксированной длины, скажем 12 бит.
Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как "ARC", решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, "ARC" читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.
Другой проблемой больших файлов является то, что с увеличением числа прочитанных байтов степень сжатия может начать ухудшаться. Причина проста : так как размер таблицы строк фиксирован, после занесения определенного числа строк их уже просто некуда добавить. Но построенная таблица нужна только для той части файла, по которой она была построена. Оставшиеся части файла могут иметь другие характеристики и в действительности нужна уже несколько отличная таблица.
Обычным способом решения этой проблемы является контроль степени сжатия. После того, как таблица строк заполнена, упаковщик следит за поведением коэффициента сжатия. После определенной степени его ухудшения таблица строк очищается и начинает строиться заново.
Процедура распаковки определяет этот момент тем, что упаковщик записывает в свой выходной поток специальный код. Альтернативным способом является определение наиболее часто встречающихся строк и чистка остальных. Адаптивная техника, подобная этой, может, однако, встретить трудности реализации в программах разумного размера.
И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.