Составители:
95
8.3
Кодирование по методу LZW
Кодирование по методу LZW- метод сжатия без потерь информации,
названный по первым буквам фамилий разработчиков Абрахама Лемпела,
Джекоба Зива и Терри Велча (Lempel, Ziv и Welch) [54]. Впервые алгоритм
был опубликован в 1984 г. Он применяется для сжатия данных при записи
на жесткий диск компьютера в формате ARJ, ZIP, GZ, применяется при
записи файлов в форматах
TIFF и GIF.
Особенностью метода является адаптивность и использование кодов
переменной длины, с некоторым предопределенным числом разрядов.
8.3.1 Кодирование
Начальная кодовая таблица инициализируется так, что каждому
отсчету изображения из диапазона [0,255] ставятся в соответствие код,
которым этот отсчет будет представлен в потоке, и два специальных кода:
код очистки (256) и код конца потока (257), как показано в таблице 8.1.
Таблица 8.1 Таблица инициализации кодера/декодера LZW
№ по порядку Десятичное значение строки
байтов изображения или
имя кода
Десятичное
значение кода в
потоке
0 0 0
… … …
254 254 254
255 255 255
256 Код очистки 256
257 Код конца записи 257
Пусть длина кода ограничена 12 разрядами. Тогда, если номера кодов
превышают 12-разрядное значение, равное 4095, используют код очистки
для новой инициализации таблицы. Код конца потока является признаком
конца кодовой последовательности.
Алгоритм LZW можно записать формально:
Инициализировать таблицу кодов (таблица 8.1).
Записать в поток код очистки. Текущий буфер CurBuf пуст.
Далее в цикле до конца файла изображения:
a)
Прочитать очередной байт изображения в буфер (Byte).
b)
Если в таблице кодов имеется код, соответствующий комбинации
CurBuf+ Byte, то увеличить буфер на один байт и поместить в
него Byte: CurBuf := CurBuf + Byte. Перейти в начало цикла a).
c)
Иначе, (если код, соответствующий комбинации CurBuf + Byte,
отсутствует) то:
−
получить из таблицы код Code, соответствующий содержимому
буфера CurBuf,
−
вывести в выходной поток код Code,
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
