Сжатие файлов и коды

Question

Я реализую версию lzw.Допустим, я начинаю с 10-битных кодов и увеличиваю всякий раз, когда я максимально использую коды.Например, после 1024 кодов мне понадобится 11 бит для представления 1025. Проблема заключается в выражении сдвига.

Как мне сказать декодеру, что я изменил размер кода?Я думал об использовании 00, но программа не может различить 00 как приращение и 00 как два экземпляра нулевого кода.

Есть предложения?

Answer 1

Ты не. Вы переходите на новый размер, когда словарь заполнен. Словарь дешифратора синхронизирован со словарем энкодера, поэтому они оба будут заполнены одновременно, и декодер перейдет к новому размеру именно тогда, когда это произойдет.

Время, когда вам нужно отправить код, чтобы сообщить об изменении, - это когда вы полностью заполнили словарь - вы использовали все самые большие доступные коды. В этом случае вы , как правило, хотите продолжать использовать словарь до тех пор, пока / или если уровень сжатия не начнет падать, затем очистите словарь и начните все сначала. Вам нужно поставить маркер, чтобы сказать, когда это произойдет. Как правило, для этой цели вы резервируете самый большой код, но любой код, который вы не используете для других целей, будет работать.

Редактировать: кроме того, обратите внимание, что вы обычно хотите начинать с кодов, которые на один бит больше, чем коды для входа, поэтому, если вы сжимаете 8-битные байты, вы должны начать с 9-битных кодов. 1007 *

Answer 2

Количество бит увеличивается при создании кода для 2 ⁿ -1.Поэтому, когда вы создаете код 1023, немедленно увеличивайте размер бита.Вы можете получить лучшее описание схемы сжатия GIF .Обратите внимание, что это была запатентованная схема (которая отчасти вызвала создание PNG).Срок действия патента к настоящему времени истек.

Answer 3

Это часть алгоритма LZW.

При распаковке вы автоматически создаете словарь кодов снова.Когда новый код точно заполняет текущее количество битов, размер кода должен быть увеличен.

Подробнее см. Википедия .

Answer 4

Поскольку декодер создает ту же таблицу, что и компрессор, его таблица заполняется при достижении последнего элемента (например, 1023 в вашем примере), и, как следствие, декодер знает, что следующим элементом будет 11 бит.