84
правки
Изменения
м
< text=right > Изначальный словарь:
→Пример
== Пример ==
{| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"
=== Декодирование ===
Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.<br>
Теперь представим ,что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью 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.
<br>
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12, которому соответствует цвет 12. Затем читает код 32, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12. Поэтому он добавит в свою таблицу строку 12, 12 с кодом 32, а в выходной поток поместит 12, 12. И так может быть раскодирована вся цепочка кодов.
<br>
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точек, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
