Как определить длину кодового слова для LZW-декодирования
Я пишу обычную программу LZW-декодера c ++, и у меня возникают проблемы с поиском документации по длине (в битах) используемых кодовых слов. Некоторые статьи, которые я нашел, говорят, что кодовые слова имеют длину 12 битов, в то время как другие говорят, что 16 битов, в то время как другие говорят, что используется переменная длина битов. Так что это? Для меня будет иметь смысл, что длина в битах является переменной, поскольку это даст наилучшее сжатие (то есть сначала начните с 9 битов, затем перейдите к 10 при необходимости, затем перейдите к 11 и т. Д.). Но я не могу найти никакой «официальной» документации о том, что такое отраслевой стандарт.
Например, если бы я должен был открыть Microsoft Paint и создать простое черное изображение размером 100×100 пикселей и сохранить его как TIFF. Изображение сохраняется в формате Tiff с использованием сжатия LZW. Таким образом, в этом сценарии, когда я анализирую кодовые слова LZW, я должен прочитать в 9 битах, 12 битах или 16 битах для первого кодового слова? и как я узнаю, что использовать?
Спасибо за любую помощь, которую вы можете предоставить.
Решение
LZW можно сделать любым из этих способов. Безусловно, наиболее распространенным (по крайней мере, по моему опыту) является запуск с 9-битных кодов, затем, когда словарь заполняется, переход к 10-битным кодам и т. Д. До некоторого максимального размера.
Оттуда у вас, как правило, есть несколько вариантов. Один из них — очистить словарь и начать все сначала. Другой — продолжать использовать текущий словарь, не добавляя новые записи. В последнем случае вы обычно отслеживаете степень сжатия, и если она падает слишком далеко, вы очищаете словарь и начинаете сначала.
Я должен был бы покопаться в документации, чтобы быть уверенным, но если я не ошибаюсь, конкретная реализация LZW, используемая в TIFF, начинается с 9 и достигает 12 бит (когда она создавалась, MS-DOS была главной цель, а в словаре для 12-битных кодов используется большая часть доступной 640К оперативной памяти). Если память служит, она очищает таблицу, как только последний 12-битный код был использован.
Другие решения
Других решений пока нет …