Алгоритмы, структуры данных




LZW.


Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управляет повсеместным исключением этих символов, поэтому вывод содержит только указатели [108]. Это достигается инициализацией списка фраз, включающего все символы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.

LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использовании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адаптивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.




Содержание  Назад  Вперед