Microsoft Word Уч пособие 22 09. doc

Кодирование по методу LZW

Кодирование по методу LZW- метод сжатия без потерь информации, названный по первым буквам фамилий разработчиков Абрахама Лемпела, Джекоба Зива и Терри Велча (Lempel, Ziv и Welch) [54]. Впервые алгоритм был опубликован в 1984 г. Он применяется для сжатия данных при записи на жесткий диск компьютера в формате ARJ, ZIP, GZ, применяется при записи файлов в форматах TIFF и GIF.
Особенностью метода является адаптивность и использование кодов переменной длины, с некоторым предопределенным числом разрядов.

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 пуст.
  
• 
  Далее в цикле до конца файла изображения:
  

1. 
   Прочитать очередной байт изображения в буфер (Byte).
   
2. 
   Если в таблице кодов имеется код, соответствующий комбинации CurBuf+ Byte, то увеличить буфер на один байт и поместить в него Byte: CurBuf := CurBuf + Byte. Перейти в начало цикла a).
   
3. 
   Иначе, (если код, соответствующий комбинации CurBuf + Byte,
   

отсутствует) то:

• 
  получить из таблицы код Code, соответствующий содержимому буфера CurBuf,
  
• 
  вывести в выходной поток код Code,
  
• 
  добавить в таблицу код, соответствующий CurBuf + Byte, присвоив ему значение, совпадающее со следующим порядковым номером,
  
• 
  переписать содержимое буфера Byte в CurBuf: CurBuf=Byte,
  
• 
  перейти в начало цикла a).
  
• 
  Поскольку по окончании файла изображения CurBuf не пуст, то необходимо:
  
  • 
    получить из таблицы код Code, соответствующий содержимому буфера CurBuf,
    
  • 
    вывести в выходной поток код Code,
    
  • 
    вывести в выходной поток код конца записи.
    

Описанный алгоритм поясним на примере кодирования последовательности отсчетов: {7, 7, 7, 10, 10, 7, 7, 5, 5}. Кодирование начинается с инициализации таблицы кодов в соответствии с таблицей 8.1. В выходной поток записывается код очистки. CurBuf – пустой. Далее в цикле выполняются следующие действия:
Считываем нулевой байт изображения (7): Byte=7. CurBuf+Byte равен
Byte и присутствует в таблице, поэтому CurBuf=7, переход к a).
Считываем первый байт изображения (7) в буфер Byte=7. Комбинация CurBuf+Byte, представляющая последовательность двух байтов (7,7), отсутствует в таблице. Поэтому получаем из таблицы код, соответствующий CurBuf, Code =7 и записываем его в выходной поток. Добавляем в таблицу код, соответствующий (CurBuf+Byte), присвоив ему значение, совпадающее со следующим порядковым номером Сode =258  (7,7). Переписываем содержимое буфера Byte в CurBuf: CurBuf =7 и переходим в начало цикла a).
Можно далее коротко записать процесс кодирования следующим образом:
Считываем (7). (7,7) есть в таблице. CurBuf = (7,7).
Считываем (10). (7,7,10) нет в таблице. В поток - 258. В таблицу - 259
 (7,7,10). CurBuf =10.
Считываем (10). (10,10) нет в таблице. В поток - 10. В таблицу - 260
 (10,10). CurBuf=10.
Считываем (7). (10,7) нет в таблице. В поток - 10. В таблицу - 261 
(10,7). CurBuf=7.
Считываем (7). (7,7) есть в таблице. CurBuf = (7,7).
Считываем (5). (7,7,5) нет в таблице. В поток - 258. В таблицу - 262 
(7,7,5). CurBuf=5.
Считываем (5). (5,5) нет в таблице. В поток - 5. В таблицу - 263 
(5,5). CurBuf =5.
В поток-5. В поток-257.
Таким образом, выполняя перечисленные действия, мы получили результаты, приведенные в таблице 8.2.
Выходной поток представляет следующую последовательность кодов:
{256, 7, 258, 10, 10, 258, 5, 5, 257}.
Таблица 8.2. Пример кодирования по алгоритму LZW

Чтение байта №	Byte	Код, выводимый в поток	Содержимое таблицы кодов	CurBuf
		256		пустой
0	7			7
1	7	7	258  7,7	7
2	7			7,7
3	10	258	259  7,7,10	10
4	10	10	260  10,10	10
5	7	10	261  10,7	7
6	7			7,7
7	5	258	262  7,7,5	5
8	5	5	263  5,5	5
		5
		257

2.