84
правки
Изменения
→Декодирование
=== Декодирование ===
Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
Теперь представим ,что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
| style="border-right: none;" | 36:
| style="border-left: none;" | 25, 25, 25
| style="border-right: none;" | -| style="border-left: none;" | -
| style="text-align: left;" |
|-
|}
=== Примечание ===
Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значений, например 12, 12, 12 … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 12, 12, 32 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, да, если мы оговорим следующие действия по кодированию и декодированию: <br>
Кодирование таких цепочек будем осуществлять следующим образом. Первый цвет 12 записывает с его же кодом из таблицы 12. Следующий цвет тоже 12, тогда добавляем в таблицу строку 12, 12 с кодом 32 и в выходной поток сразу заносим этот код, то есть 32. Смотрим входной поток дальше. Если на вход опять поступает цвет 12, он есть в таблице, смотрим следующий – 12, последовательность 12, 12 тоже есть в таблице, смотрим дальше – 12, последовательности 12, 12, 12 присваиваем код 33 и заносим его в выходной поток. В результате на выходе получаем последовательность 12, 32, 33 …, которая гораздо короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12, которому соответствует цвет 12. Затем читает код 32, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12. Поэтому он добавит в свою таблицу строку 12, 12 с кодом 32, а в выходной поток поместит 12, 12. И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точек, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
== Патенты ==
