LZW-кодирование

Алгоритм LZW, впервые представленный Уэлчем в 1984 году, в последние несколько лет стал широко используемым методом. Формат GIF файлов CompuServe использует сжатие LZW; это делают и ARC, compress из UNIX, Stuffit и PkZip. Сам алгоритм запатентован фирмой Sperry.

Несмотря на некоторую сложность, этот метод достаточно мощный и быстрый, что, собственно, и обусловило его популярность. LZW работает путем расширения алфавита — он использует дополнительные символы для представления строк обычных символов. Чтобы использовать LZW-сжатие на 8-битовые коды ASCII, вы расширяете алфавит, используя девяти- и более битовые коды. Дополнительные 256 символов, предоставляемые 9-битовым кодом, используются для хранения строк 8-битовых кодов, которые определяются из строк во входном потоке.

Компрессор поддерживает таблицу строк, состоящую из строк и соответствующих им кодов. Таблица строк соответствует расширенному алфавиту. Компрессор начинает с таблицы строк, определенной только 256 кодами букв. Если вы используете 9-битовые коды, таблица строк имеет 256 дополнительных пустых элементов; если вы используете 10-битовые коды, она имеет 768 пустых элемента и т.д.

Алгоритм сжатия работает примерно так. Начните с нулевой строки. Прочитайте символ и добавьте его к строке. Если строка уже находится в таблице, продолжайте чтение, пока не получите строку, которой нет в таблице. Добавьте эту строку к таблице строк. Пишите код для последней известной строки, которая соответствует выходу. Используйте последний символ в качестве основы для новой строки и продолжайте чтение, пока не исчерпаете весь ввод.