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

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

Для начала представим, что нам надо сжать данные, которые состоят из 256 различных символов. Это число не случайно, оно равно максимальному количеству цветов в GIF файлах. На этапе инициализации, ты должен закодировать все возможные значения символов: первому символу назначить "код 1", второму символу - "код 2" и так далее. При сжатии растровых данных GIF файла эта задача упрощается, потому что в качестве символов используются индексы цвета, которые изменяются от 0 до 255. Это значит, что тебе нужно просто создать массив с этими числами. Задача усложниться только если ты будешь сжимать символьные данные, а не числовые, или если числовые будут содержать пропуски (1, 3, 6 …).

Теперь рассмотрим сам алгоритм:

1. Инициализация массива кодов
2. index = пустая строка
3. index + следующий символ
4. Есть index в массиве?

 да:   (BK:=Код для index
        перейти на 3-й шаг)
 иначе:(добавить index в массив кодов
        вывести ВК в выходной массив
        index=текущий символ
        перейти на 4-й шаг)

Первый этап мы уже рассмотрели и останавливаться на нём не имеет смысла.

На втором этапе мы инициализируем переменную index, в которой будем хранить последовательность символов подлежащих сжатию.

На третьем этапе мы присваиваем этой переменной следующий символ (при первом проходе это первый символ) который подлежит сжатию.

Четвёртый этап, мы проверяем наличие последовательности символов index в массиве кодов. На первом этапе index равен одному символу, а в массиве кодов закодированы все возможные символы, поэтому результат обязательно должен быть "да".

Если "да", то мы сохраняем в переменной "ВК" код этого последовательности символов и переходим на шаг 3.

Если "нет", то добавляем index в массив кодов, переменную "ВК" добавляем в выходной массив и в index помещаем текущий символ. Переходим на шаг 4.

Если что-то непонятно, то сейчас всё равно поймёшь. Сейчас я рассмотрю реальный пример. Для удобства, коды я буду представлять со значком #. Представим, что нужно сжать следующую последовательность данных: 4814810147. Это последовательность символов от 0 до 8. Инициализируем массив, где 0 равен "коду 0", 1 = "код 2" и так до 8. В index присваиваем первый символ (4). Проверяем его наличие в массиве кодов. Результат, конечно же "да" (код 4), поэтому ВК=#4. Переходим на шаг 3. Добавляем в index следующий символ, теперь index=48. Такова в массиве кодов нет, поэтому мы добавляем "48" под номером 9, а в выходной массив записываем "ВК". В Index засовываем 8 и переходим на шаг 4. Этот символ опять есть. Записываем код в ВК и переходим на шаг 3. Прибавляем к index "1". Такова символа опять нет, поэтому добавляем в таблицу символ "81" под кодом #10. На следующем этапе мы получаем число "14", которого опять нет, что делать ты уже догадываешься. Следующий этап 48, оно есть, поэтому мы записываем в ВК=#9 и записываем в index=481. Такова символа нет, поэтому добавляем его, а в index=1 и продолжаем. И так далее. Итоговый массив у тебя должен получится вот такой: #4 #8 #1 #9 #1 #0 #1 #11 #7.

Если у тебя получился такой массив, то можешь продолжать чтение, если нет, то перечитай статью заново. Если снова не получится, то иди к почтальону, возможно, что ошибся я.

Этот алгоритм съедает достаточно хорошие ресурсы. Особенно это сказывается при поиске символа в массиве кодов, потому что массив постоянно разрастается. Да и я не оптимизировал свой базар для того, чтобы ты мог понять, о чём тут талдонят.

Если ты разобрался с сжатием, то давай перейдём к распаковке. Её я начну с реального примера, а именно распакуем нашу последовательность #4 #8 #1 #9 #1 #0 #11 #7.

Инициализация абсолютно такая же. Берём первый символ. #4 он есть в таблице, поэтому на выходе будет 4.

Берём следующий код #8, ему соответствует символ 8. На выход добавляем 8, а в массив добавляем предыдущий символ + первый символ этого, т.е. 48.

Берём следующий код #1, что соответствует 1. На выход добавляем 1, а в массив 81.

Берём следующий код #9, что соответствует 48. На выход добавляем 48, а в массив предыдущий символ + первый символ этого, т.е. 14.

Берём следующий код #1, что соответствует 1. На выход добавляем 1, а в массив предыдущий символ (48)+ первый символ этого, т.е. 481. И так далее.

Если ты всё сделал правильно, то массивы при сжатии и распаковке будут одинаковыми, и результат совпадёт. Надеюсь, ты понял алгоритм. Но во время распаковки встречаются и подводные булыжники. Например, ты сжал вот такую последовательность: 333333, при максимуме значений = 8. Результатом сжатия будет #3, #9, #10 и так далее. На этапе распаковке ты наткнёшься на то, что второго символа не будет в твоём массиве. Каким местом ты должен будешь догадываться, чему равен код #9. А тем, что это может быть только 33. На следующем этапе опять ты встречаешь код #10, которого нет в таблице. Тем же самым местом ты должен догадаться, что это будет 333.

Теперь я учёл все подводные плиты и другие дьявольские сооружения, поэтому переходим к особенностям GIF.

В GIF файлах инициализация происходит не как у людей. Помимо начальной таблицы здесь присутствуют два специальных кода. Например, если картинка имеет цветовое разрешение 2 бит, то твоя таблица должна состоять из 4-х значений. Но это не так. Спецификация GIF добавляет ещё два, поэтому будет 6. Если у тебя монохромная картинка, то твои коды будут под номерами 0 и 1, а два специальных под номерами 4 и 5. В остальных случаях специальные коды идут вплотную к твоим. Два специальных кода это "CC" - код очистки, и EOI конец информации. Если вы сжимаете GIF, то "СС" должен быть первым кодом, и так каждый раз, когда код достигает FFF. Это связано с тем, что GIF поддерживает только 12 битное сжатие. При распаковке, как только встречается код "СС" нужно реинсталировать массив.

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