LZW в GIF

Алгоритм LZW имеет несколько особенностей своей реализации в формате сжатия изображений gif. Первая особенность – это переменный размер кода таблицы цепочек, который не может превышать 12 бит, т.е. не превышать числа 4095. Вторая особенность состоит в использовании двух специальных кодов – это код обновления (реинициализации) таблицы цепочек, и код завершения потока символов.

В самом начале своей работы алгоритм определяет количество цветов, используемых в изображении. В случае GIF их максимум может быть 256, т.к. любое изображение, даже с большим набором цветов преобразуется в 256 цветовое пространство. Минимум может быть 2 цвета. Если используется только два цвета, то начальный размер кодов в таблице равен 3 битам. Причем коду 0 ставится цвет 0, а коду 1 – цвет 1. Коды 4 и 5 соответствуют коду очистки таблицы и коду. При большем количестве цветов размер кода таблицы равен числу бит N, приходящихся на один пиксел. При этом специальные коды равны и. Начальный размер кодов в таблице записывается в заголовок GIF файла.

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

Разработчики формата GIF ограничили максимальный размер кодов в таблице 12 битами. Это значит, что когда код достигает значения, то размер увеличивать уже нельзя. Но в то же время и размер кодов становится больше 12 бит. Как разрешить данную ситуацию? Простым решением является выполнить перегенерирование таблицы последовательностей, после чего она будет содержать только цепочки длины, равной 1, т.е. значения пикселей и плюс специальные коды. Таким образом, она перейдет в то же состояние, в котором была на момент начала кодирования изображения. А для того, чтобы декодировщик знал, что в определенный момент произошло перегенерирование таблицы, кодировщик в выходной поток записывает код управляющего символа.