84
правки
Изменения
м
→Примечание
=== Примечание ===
Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значений, например 12, 12, 12 … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 12, 12, 32 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, да, если мы оговорим следующие действия по кодированию и декодированию: . <br>Кодирование таких цепочек будем осуществлять следующим образом. :<br>Первый цвет 12 записывает с его же кодом из таблицы 12. Следующий цвет тоже 12, тогда добавляем в таблицу строку 12, 12 с кодом 32 и в выходной поток сразу заносим этот код, то есть 32. Смотрим входной поток дальше. Если на вход опять поступает цвет 12, он есть в таблице, смотрим следующий – 12, последовательность 12, 12 тоже есть в таблице, смотрим дальше – 12, последовательности 12, 12, 12 присваиваем код 33 и заносим его в выходной поток. В результате на выходе получаем последовательность 12, 32, 33 …, которая гораздо короче прямого кодирования стандартным методом LZW.<br><br>
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12, которому соответствует цвет 12. Затем читает код 32, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12. Поэтому он добавит в свою таблицу строку 12, 12 с кодом 32, а в выходной поток поместит 12, 12. И так может быть раскодирована вся цепочка кодов.
<br><br>
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точек, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
