Описание алгортма lzw коментарии по поводу gif


Содержание

GIF декодер (вопрос по LZW)

29.03.2020, 22:09

LZW для Gif на Delphi 7
:wall: По-порядку: пишу LZW-архиватор (с позволения сказать). Проблема в том, что до сжатия дело не.

Чтение файла GIF. Перевод текста в HEX. Декодирование GIF анимации
Всем привет.. задача такая: Необходимо открыть файл GIF.. Например, как в этой статье про.

LZW C++
Кто знает где можно скачать исходники программы для компрессии/декомпрессии текстовых файлов.

LZW алгоритм
Сделал сжатие текста на основе LZW. Считывание происходит с txt файла, запись List .

30.03.2020, 05:13 2 30.03.2020, 15:13 3 30.03.2020, 16:29 4
30.03.2020, 16:29
30.03.2020, 18:02 5

Нет же, в файле gif_tood.h реализован полный декодер: декодирует гифку и вызывет вашу callback функцию для каждого кадра.

Возможно Вас смутил текст «header-only GIF tooder», в данном случае имеется в виду не header гифки а что сама библиотека — headr-only (.h файл, без .c).

30.03.2020, 18:31 6

Ага есть декодер, только там непонятно сколько потребуется ОЗУ в МК, как будут храниться картинки, как выводиться и прочее. В МК все реализуется в тесной связке с железом. Поэтому много чего доделывать нужно будет для конкретного приложения. Пока кто-то не сделает реальный пример использования с высокой эффективностью в микроконтроллерах например STM32, код так и будет сырым лежать.

В микроконтроллерах GIF практической ценности не имеет, поэтому я его до сих пор с Delphi не портировал. В GUI применять смысла нет, постоянное декодирование, накладные ресурсы на процессор, ОЗУ. Все это жрет проц и озу только в путь.
Я свой выбор остановил на BMP картинках сразу подготовленных для прямой DMA передачи в нужном режиме зависящий от дисплея. Минимальная нагрузка на процессор, высокая скорость отрисовки. Часть GUI успешно компилируется во флеш память микроконтроллера, крупные картинки можно хранить во внешней флеш.

Creative Web Projects

Переносимый сетевой графический формат (англ. Portable Network Graphics, PNG) разрабатывается как более эффективная, гибкая и свободная от патентов замена GIF- формату. PNG был задуман для хранения отдельных растровых изображений и дальнейшего их распространения по компьютерным сетям. PNG был создан в 1995 в ответ на давление со стороны Unisys и их патента на алгоритм LZW-сжатия, используемый в GIF. Хотя срок действия патента Unisys уже закончился, причины на переход от GIF к PNG остались практически прежними. Заменив GIF-изображения теми же самыми, но в формате PNG, можно ускорить загрузку страниц и сэкономить трафик пользователей.

Алгоритмы сжатия

PNG использует алгоритм deflate-сжатия обычно со скользящим окном в 32 Кб. Deflate является улучшенной версией алгоритма сжатия Lempel-Ziv (LZ77), который применяется в zip- и gzip-файлах. Созданный Phil Katz для второй версии PKZip, deflate совмещает LZ77 с кодированием Huffman и является на 10-30% более эффективным, чем LZW при сжатии без потери информации. Так же, как и gzip, некоторые инструменты по PNG- сжатию предполагают опциональный параметр «степень сжатия», которая варьируется от 1 до 9. По умолчанию выставляется 6. Практически всегда лучшим выбором для максимального сжатия является 9.

Неудивительно, что изображения, сохраненные как PNG, обычно на 10-30% меньше по размеру, чем GIF, хотя в некоторых редких случаях они могут быть несколько больше (чаще всего это проявляется для небольших изображений). Обычно изображения с большими однотонными областями сжимаются лучше, чем градиентные с большим количеством переходов между цветами.

Возможности PNG

В PNG присутствует набор возможностей, которые делают его привлекательным для использования во многих отраслях, где требуется применение ограниченной палитры. Поддержка в PNG 16-битной серой шкалы прекрасно подходит для создания точных радиологических изображений. PNG предварительно фильтрует данные по конкретному изображению при помощи предсказательных функций. Одной из них является «Вверх» (англ. Up), которая ищет похожие наборы данных в вертикальных шаблонах для полноцветных PNG. PNG с индексированными цветами (8 битов или меньше) обычно не выигрывает от использования фильтрации, поэтому стоит использовать «ничего» (англ. none), если есть возможность для выбора. Для полноцветных или серых изображений лучше применять «Адаптивный» (англ. Adaptive) алгоритм.

Как говорит Greg Roelofs, «PNG, в основном, используется для создания 24-битных RGB сформированных изображений, например, картин с рассчитанным освещением с минимальным числом текстур или математических объектов. Они все обладают искусственно сглаженными цветовыми переходами, которые хорошо сжимаются при помощи PNG-фильтров. Некоторые фракталы могут вести себя таким же образом, но у многих из самых лучших примеров имеется достаточно «зашумленных» областей, которые сжимаются весьма слабо».

Для веб-страниц вполне можно использовать PNG8 (8 битный формат), с помощью которого дизайнеры могут заменить существующие GIF-изображения. У PNG также может быть альфа-значение для каждого цвета в палитре, которое, фактически, означает, что используется RGBA-палитра, а не RGB-XOR-маска, как GIF. Это позволяет варьировать прозрачность цвета в больших пределах, сохраняя преимущества 8-битного изображения перед 32-битным. PNG могут также содержать только один уровень прозрачности, совсем как GIF89a. Алгоритм сжатия PNG для повторяющихся горизонтальных шаблонов совпадает с LZW-сжатием в GIF.

Многослойный PNG-файл также может быть отображен на экране по загрузке только 25% всего файла, в то время как GIF требует загрузки 50% размера перед распознаванием. За исключением весьма редких случаев замена GIF-изображений на PNG-эквиваленты способна существенно уменьшить их размер.

Ниже приведены некоторые из возможностей PNG-формата.

  • 8-битные (индексированная палитра), 16-битные серые или 48-битные полноцветные изображения.
  • Градация альфа-прозрачности до 16 битов.
  • Гамма-коррекция (хотя эта возможность может быть проблематичной).
  • Улучшенный по сравнению с LZW алгоритм сжатия.
  • Двумерная схема для многоуровневых изображений (Adam7).
  • Метаданные (сжатые или несжатые).
  • Формат, свободный от патентов.

Поддержка PNG в браузерах

В Netscape естественная поддержка PNG весьма ограничена: начиная с версии 4.04, для Internet Explorer она зависит от операционной системы. Для Macintosh IE полностью поддерживает PNG с версии 5.0 (в том числе, включая альфа-канал). MSIE для Win32 и Unix обладает естественной поддержкой PNG (на деле же весьма посредственной) начиная с 4.0, но не поддерживает альфа-канал до версии 7.0 (это исправляется при помощи фильтра AlphaImageLoader).

На данный момент большое количество разнообразных браузеров также поддерживает PNG, однако, лишь с 1-битной прозрачностью, что позволяет использовать PNG для замены неанимированных GIF.

PNG и проблема соответствия для фоновых CSS-изображений

К несчастью, поддержка возможностей PNG-гаммы и цветовой коррекции не является кроссбраузерной. Наиболее часто рекомендуемой мерой для исправления возможных ошибок будет исключение фрагментов, обеспечивающих гамму и цветовую коррекцию, для создания «неименованного» PNG (удаление gAMA чанка). Это решает проблему цветового соответствия для современных браузеров, кроме Safari под Mac до OS 10.4 (тут может помочь удаление sRBG чанка, подробнее об удалении чанков рассказывается немного ниже).

Для отдельных PNG-изображений это совсем не проблема, но для дизайна веб-страниц, который требует точного соответствия между CSS-фоном и PNG, к сожалению, это имеет значение (однако, может быть устранено указанными выше путями).

Анимированные PNG: MNG против «PNG+»

Формат составной сетевой графики (англ. Multiple Network Graphics, MNG) представляет собой несколько PNG-изображений, по аналогии с GIF89a. Однако, MNG-формат является более сложным и не поддерживается текущими браузерами (для этого нужно использовать бесплатное расширение libmng).

Группа разработчиков Mozilla расширила текущий (для одного изображения) PNG-формат в браузере Firefox 3, добавив несколько дополнительных кадров для анимации. Существует также встречное предложение со стороны членов группы PNG, подразумевающее создание чего-то подобного, однако, не противоречащего спецификации PNG. Оба этих направления значительно проще, чем MNG, и оба открыты для голосования в группе PNG.

Сейчас же для анимации изображений лучше всего применять GIF89a или Flash. Однако последние достижения в векторной графике, SVG, и развитие анимационных JavaScript- библиотек составляют реальную конкуренцию указанным форматам. Вполне возможно, что через несколько лет вся несложная анимация в браузерах будет осуществляться при использовании именно такого подхода.

Двигаемся к маленьким PNG

PNG работает лучше с большими однотонными областями. Чтобы увеличить степень сжатия, стоит уменьшить количество «шума» в ваших картинках для увеличения размеров однотонных областей. Уменьшайте области размывания, хотя для изображений с градиентами размывание позволяет использовать меньшую глубину цвета. Избегайте сглаживания текста для уменьшения числа цветов, которые для него необходимы, в финальном изображении.

По возможности, уменьшайте число цветов в вашем исходном изображении, если в процессе разработки этот фактор можно контролировать. Стоит также избегать использования многослойных PNG-изображений для уменьшения размера файла, так как семипроходная многослойная схема может добавить от 20% до 35% к размеру PNG- файла. Наконец, можно применять специальное программное обеспечение для оптимизации PNG-изображений, которое специально разрабатывается с этой целью, например, pngout или pngcrush.

Полезные советы

Ниже приведено несколько простых советов, как текущие изображения можно дополнительно уменьшить в размере. Можно написать простой скрипт, который перебирает директории с изображениями перед публикацией сайта и делает следующие действия (далее приведены примеры запуска утилит из командной строки для ОС Linux).

1. Преобразовывает GIF в PNG (и проверяет, есть ли при этом выигрыш):

convert image.gif image.png или так gif2png -nstO image.gif image.png

2. Уменьшает PNG файлы в размере:

pngcrush -qz3 -brute image.png result.png

если при этом нужно удалить и gAMA чанк, то:

pngcrush -qz3 -rem gAMA -brute image.png result.png

если при этом хотим удалить другие чанки, отвечающие за цветовую коррекцию, то:

pngcrush -qz3 -rem gAMA -rem cHRM -rem iCCP -rem sRGB \ -brute image.png result.png

3. Уменьшает JPEG-файлы в размере (без потери качества):

jpegtran -copy none -optimize -perfect image.jpg > result.jpg

Под Windows для уменьшения .png изображений можно использовать TweakPNG ( http://entropymine.com/jason/tweakpng/ ). Аналогом jpegtran является набор портированных утилит jpeg, которые можно загрузить по адресу: http://sourceforge.net/projects/gnuwin32/

Для отдельно взятой страницы общий размер изображений может быть уменьшен на 20- 30% только благодаря следованию этим простым советам.

От формата LZW к формату GIF

Как и BMP, GIF (CompuServe Graphics Interchange Format) является одним из старейших форматов. В 1977 г. израильские математики А. Лемпел и Я. Зив разработали новый класс алгоритмов сжатия без потерь, получивший название метод Лемпела—Зива. Одновременно с самим алгоритмом, именуемым LZ77 (по первым буквам фамилий ученых и последним цифрам года создания), свет увидела статья, где излагались общие идеи данного метода. Впоследствии появилась усовершенствованная версия продукта — LZ78. Многие специалисты стремились доработать его; наибольшее распространение получил вариант LZW, написанный Т. Уэлчем, сотрудником фирмы Unisys, в 1983 г. Он отличался от своего прародителя более высоким быстродействием. В 1985 г. Unisys запатентовала LZW. Этот алгоритм универсален и может использоваться для сжатия информации любого вида. Однако успешнее всего он справляется с графическими изображениями.

В 1987 г. компания CompuServe разработала на основе алгоритма LZW графический формат GIF (Graphic Interchange Format), позволивший эффективно сжимать изображения с глубиной цвета до 8 бит, а по тем временам 256 оттенков считалось огромным количеством. Он был разработан для передачи растровых изображений по сетям.

В 1989 г. CompuServe выпустила усовершенствованную версию формата, названную GIF89a. В нее были добавлены две функции, которые и по сей день обеспечивают формату популярность в Интернете (GIF позиционируется прежде всего как сетевой формат). Во-первых, был добавлен альфа-канал, где может храниться маска прозрачности, во-вторых, GIF стал анимированным, т. е. в один файл можно поместить несколько изображений, которые будут сменять друг друга через заданный интервал времени. Таким образом, GIF начал поддерживать прозрачность и анимацию. Файлы GIF содержат информацию в сжатом виде, что позволяет заметно уменьшить их размер, особенно если в них есть большие пространства, закрашенные одним цветом. Можно назначить один или несколько цветов прозрачными. Помимо этого GIF может хранить сразу несколько изображений, которые будут отображаться последовательно одно за другим. Объединив эти возможности, можно получить мини-мультфильмы, носящие название «анимированные GIF». Такие изображения можно встретить в оформлении интернет-сайтов, хотя в последнее время все большее количество дизайнеров предпочитают пользоваться технологией Flash.

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

Область применения GIF известна всем — это изображения с резкими цветовыми переходами и бизнес-графика (логотипы, кнопки, элементы оформления и т. п.). А вот для тех картинок, где важно постепенное изменение оттенков (например, для фотографий), данный формат подходит меньше всего. Первая причина таких ограничений — небольшая по современным меркам максимальная глубина цвета изображения. Для фото 8 бит явно недостаточно. Вторая — не всегда корректное преобразование файлов с плавными цветовыми переливами в палитру 256 цветов и менее. Третья причина ограниченности сферы применения GIF заключается в особенностях метода сжатия информации. Данные об изображении записываются построчно. В итоге все операции происходят с массивом строк высотой в один пиксел (каждая строка обрабатывается отдельно). Следствие этого — не только крайняя неэффективность сжатия фотографий и любых других изображений, содержащих мало однотонных областей, но и зависимость его результата от расположения объектов. Главный недостаток GIF заключается в том, что изображение может содержать 256 цветов. Это слишком мало для большинства современных задач.

Кстати, алгоритм LZW используется и в формате-TIFF. Однако он по качеству сжатия значительно уступает формату GIF, хотя и поддерживает большее количество цветов в палитре.

Дата добавления: 2014-11-25 ; Просмотров: 370 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Алгоритм LZW

Алгоритм LZ78 существовал до 1984 года как математическая абстракция, пока не был усовершенствован Терри Уэлчем. Главной особенностью алгоритма LZW стало удаление второго поля из метки.

Суть LZW в том, что рабочий модуль первоначально должен инициализировать словарь из 256 символов (в общем случае 8-битного алфавита). Символы с номерами от 0 до 255 дадут нам полный набор наиболее часто используемых в текстах знаков, а также русский и английский алфавиты. Таким образом, первый символ сжимаемого текста совершенно точно будет найден в словаре, и метка может состоять всего лишь из указателя.

На следующем шаге второй символ группируется с первым в строку, и эта строка ищется в словаре. Если она там найдена, то процесс удлинения строки продолжается. Если же строка в словаре не найдена, то выполняется следующий набор действий:

1) В выходной файл записывается указатель на предыдущую строку;

2) В конец словаря записывается ненайденная строка;

3) Строка перестает удлиняться, и начинается работа со следующим символом.

Поясним на примере. Возьмем строку «топот_копыт» и попробуем сжать ее при помощи LZW.

Рабочая строка Присутствие в словаре Запись в словарь Запись в выходной файл
т есть
то нет 256-то 226(т)
о есть
оп нет 257-оп 222(о)
п есть
по нет 258-по 223(п)
о есть
от нет 259-от 222(о)
т есть
т_ нет 260-т_ 226(т)
_ есть
нет 261-_к 32(_)
к есть
ко нет 262-ко 218(к)
о есть
оп есть
опы нет 263-опы 257(оп)
ы есть
ыт нет 264-ыт 235(ы)
т есть
т, eof нет 226(т)

Поясним этот пример. После инициализации словаря мы находим номер первого символа (226). Затем добавляем к нему следующий и видим, что такой строки (то) в словаре нет. Последний символ у нас 255, добавляем «то» под номером 256 в словарь и записываем в выходной файл указатель на «т» — 226. После чего начинаем все заново с символа «о». Если строка из двух символов есть в словаре, точно так же работаем со строкой из трех и более символов, в конце итерации рабочей строке все равно присваивается один символ. Последняя строка «т, eof» в словарь, естественно, не записывается.

Выходной файл будет выглядеть так: 226, 222, 223, 222, 226, 32, 218, 257, 235, 226.

2.2.1. Декодирование LZW

LZW очень удобен в плане декодирования. Особенность его в том, что кодер и декодер в состоянии работать синхронно. То есть, при поступлении на вход декодера закодированного файла он просто инициализирует словарь, смотрит по указателям, из которых состоит файл, номера символов в словаре и восстанавливает файл, исходя из этого.

Пошагово декодер работает так:

1) Вводится указатель, извлекается соответствующая строка I из словаря;

2) Строка записывается в выходной файл;

3) Из нее извлекается первый символ, и с предыдущей строкой J заносится в словарь на свободную позицию;

4) I перемещается в J.

Поясним работу декодера на нашем примере «топот_копыт». Первым символом входного файла является указатель 226. Он соответствует строке «т», которая извлекается по ссылке из словаря и записывается в разжатый файл. Следующий указатель – 222. Извлекается строка «о», записывается в выходной файл, а строка «о» добавляется к предыдущей, образуя строку «то», которая, также как и в кодере, добавляется на последнюю позицию. Таким образом декодер проходит до конца файла, расжимая текст обратно в «топот_копыт».

Резюмируя сказанное, представим достоинства и недостатки алгоритма LZW.

1) Не требует вычисления вероятностей встречаемости символов или кодов.

2) Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

3) Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа.

Недостаток: Алгоритм не проводит анализ входных данных, поэтому не оптимален.

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.
Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Описание функционирования рабочего модуля

В данном разделе описывается построчное функционирование рабочего модуля алгоритма Хаффмана, выполненное в системе Wolfram Mathematica.

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

Кодирование Хаффмана предполагает разбивку текста на символы. При помощи функций Flatten и Characters разобьем текст и выведем в виде переменной-списка символов.

Текст становится таким:

Для начала необходимо определить частоту вхождения каждого символа в текст. В Mathematica это можно рассчитать с помощью функции Tally (количество копий элементов в списке). Для удобства работы отсортируем список при помощи функций Sort и Transpose:

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8774 — | 7145 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Описание алгортма lzw коментарии по поводу gif

Mark R. Nelson
Перевод: Запольский С.А.

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 — 255 соответствуют отдельным байтам, а коды 256 — 4095 соответствуют подстрокам.


Сжатие.

Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и , если так, выводит существующий код без генерации нового.

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
СИМВОЛ = очередной символ из входного потока
IF СТРОКА+СИМВОЛ в таблице строк THEN
СТРОКА = СТРОКА+СИМВОЛ
ELSE
вывести в выходной поток код для СТРОКА
добавить в таблицу строк СТРОКА+СИМВОЛ
СТРОКА = СИМВОЛ
END of IF
END of WHILE
вывести в выходной поток код для СТРОКА

Рис. 1 Алгоритм сжатия

Простая строка, использованная для демонстрации алгоритма, приведена на рис.2. Входная строка является кратким списком английских слов, разделенных символом «/». Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки «/W» в таблице. Когда он не находит эту строку, то генерирует код для «/» и добавляет в таблицу строку «/W». Т.к. 256 символов уже определены для кодов 0 — 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву («E»), добавляет вторую подстроку («WE») в таблицу и выводит код для буквы «W».

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов «/» и «W», не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка : /WED/WE/WEE/WEB/WET

Вход(символы) Выход(коды) Новые коды и соответствующие строки
/W / 256 = /W
E W 257 = WE
D E 258 = ED
/ D 259 = D/
WE 256 260 = /WE
/ E 261 = E/
WEE 260 262 = /WEE
/W 261 263 = E/W
EB 257 264 = WEB
/ B 265 = B/
WET 260 266 = /WET
T

Рис. 2 Процесс сжатия

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


Распаковка.

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Алгоритм распаковки представлен на рис. 3. В соответствии с алгоритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда читает из входного потока новый код. Все, что ему необходимо сделать в добавок — это перевести каждый входной код в строку и переслать ее в выходной поток.

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 3 Алгоритм распаковки

На рис. 4 приведена схема работы алгоритма на основе сжатых данных, полученных в выше приведенном примере. Важно отметить, что построение таблицы строк алгоритмом распаковки заканчивается как раз тогда, когда построена таблица строк алгоритма сжатия.

Входные коды : / W E D 256 E 260 261 257 B 260 T

Вход СТАРЫЙ КОД СТРОКА СИМВОЛ Новый вход таблицы
/ / /
W / W W 256 = /W
E W E E 257 = WE
D E D D 258 = ED
256 D /W / 259 = D/
E 256 E E 260 = /WE
260 E /WE / 261 = E/
261 260 E/ E 262 = /WEE
257 261 WE W 263 = E/W
B 257 B B 264 = WEB
260 B /WE / 265 = B/
T 260 T T 266 = /WET

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.


Ловушка.

К несчастью прекрасный , простой алгоритм распаковки, приведенный на рис. 4, является все таким слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка «JOEYN» определена в таблице с кодом 300. Когда последовательность «JOEYNJOEYNJOEY» появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.

Входная строка : . JOEYNJOEYNJOEY.

Вход(символы) Выход(коды) Новые коды и соотв. строки
JOEYN 288 = JOEY 300 = JOEYN
A N 301 = NA
. . .
. . .
. . .
JOEYNJ 300 = JOEYN 400 = JOEYNJ
JOEYNJO 400 401 = JOEYNJO

Рис. 5 Некоторые проблемы

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку «JOEYN» и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное «J», к строке. Результатом является правильный перевод кода 400 в строку «JOEYNJ».

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА = перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 6 Модифицированный алгоритм распаковки


Реализация.

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.


Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.

Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка «/WEE» хранится как код 260 и символ «E». Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ «E». Наконец, код 256 хранится как «/» плюс «W».

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов : code_value[i], prefix_code[i] и append_character[i].

Когда необходимо добавить новый код в таблицу, используется хэшфункция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.

Хэш-функция, использованная в этой программе — простая «xor»-типа хэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице — меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.

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

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

Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.


Результаты.

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.

Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях «сжатый» файл может превосходить по своим размерам исходный текст. Небольшой эксперимент даст Вам представление о том, хорошо или плохо упаковываются Ваши данные.


Ваша реализация.

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

Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как «ARC», решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, «ARC» читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.

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

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

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

И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.

Коротко

Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора «C». Она должна нормально работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка «C».

Реализация компиляторов «C» для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются и облегчается использование кодов большей длины.

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

Алгоритм LZW

Непосредственным предшественником LZW является алгоритм LZ78, опубликованный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel—Ziv—Welch).

Содержание

Применение [ править ]

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.

Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время используется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Описание [ править ]

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

Например, если сжимают байтовые данные (текст), то строк в таблице окажется [math]256[/math] (от [math]»0″[/math] до [math]»255″[/math] ). Если используется [math]10[/math] -битный код, то под коды для строк остаются значения в диапазоне от [math]256[/math] до [math]1023[/math] . Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

Для декодирования на вход подается только закодированный текст, поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при декодировании во время получения нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.

Алгоритм [ править ]

Кодирование [ править ]

  • Начало.
  • Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу [math]X[/math] заносится первый символ сообщения.
  • Шаг 2. Считать очередной символ [math]Y[/math] из сообщения.
  • Шаг 3. Если [math]Y[/math] — это символ конца сообщения, то выдать код для [math]X[/math] , иначе:
    • Если фраза [math]XY[/math] уже имеется в словаре, то присвоить входной фразе значение [math]XY[/math] и перейти к Шагу 2 ,
    • Иначе выдать код для входной фразы [math]X[/math] , добавить [math]XY[/math] в словарь и присвоить входной фразе значение [math]Y[/math] . Перейти к Шагу 2.
  • Конец.

Декодирование [ править ]

  • Начало.
  • Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу [math]X[/math] заносится первый код декодируемого сообщения.
  • Шаг 2. Считать очередной код [math]Y[/math] из сообщения.
  • Шаг 3. Если [math]Y[/math] — это конец сообщения, то выдать символ, соответствующий коду [math]X[/math] , иначе:
    • Если фразы под кодом [math]XY[/math] нет в словаре, вывести фразу, соответствующую коду [math]X[/math] , а фразу с кодом [math]XY[/math] занести в словарь.
    • Иначе присвоить входной фразе код [math]XY[/math] и перейти к Шагу 2 .
  • Конец.

Пример [ править ]

Рассмотрим пример сжатия и декодирования сообщения. Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется [math]256[/math] различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие — нет), начальный размер кода будет равен [math]8[/math] битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода [math]0[/math] соответствующему символу с битовым кодом [math]00000000[/math] , тогда [math]1[/math] соответствует символу с кодом [math]00000001[/math] , и т.д., до кода [math]255[/math] .

Символ Битовый код Код
a 000
b 001 1
c 010 2
d 011 3
e 100 4

Больше в таблице не будет других кодов, обладающих этим свойством.
По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. [math]8[/math] -битные группы дают [math]256[/math] возможных комбинации бит, поэтому, когда в словаре появится [math]256[/math] -е слово, алгоритм должен перейти к [math]9[/math] -битным группам. При появлении [math]512[/math] -ого слова произойдет переход к [math]10[/math] -битным группам, что дает возможность запоминать уже [math]1024[/math] слова и т.д.

В нашем примере алгоритму заранее известно о том, что будет использоваться всего [math]5[/math] различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть [math]3[/math] ( [math]8[/math] различных комбинаций).

Кодирование [ править ]

Пусть мы сжимаем последовательность [math]abacabadabacabae[/math] .

  • Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке [math]a[/math] и проверим, есть ли строка [math]a[/math] в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка [math]a[/math] есть в таблице.
  • Шаг 2: Далее мы читаем следующий символ [math]b[/math] из входного потока и проверяем, есть ли строка [math]ab[/math] в таблице. Такой строки в таблице пока нет.

Добавляем в таблицу [math]\langle5\rangle[/math] [math]ab[/math] . В поток: [math]\langle0\rangle[/math] ;

  • Шаг 3: [math]ba[/math] — нет. В таблицу: [math]\langle6\rangle[/math] [math]ba[/math] . В поток: [math]\langle1\rangle[/math] ;
  • Шаг 4: [math]ac[/math] — нет. В таблицу: [math]\langle7\rangle[/math] [math]ac[/math] . В поток: [math]\langle0\rangle[/math] ;
  • Шаг 5: [math]ca[/math] — нет. В таблицу: [math]\langle8\rangle[/math] [math]ca[/math] . В поток: [math]\langle2\rangle[/math] ;
  • Шаг 6: [math]ab[/math] — есть в таблице; [math]aba[/math] — нет. В таблицу: [math]\langle9\rangle[/math] [math]aba[/math] . В поток: [math]\langle5\rangle[/math] ;
  • Шаг 7: [math]ad[/math] — нет. В таблицу: [math]\langle10\rangle[/math] [math]ad[/math] . В поток: [math]\langle0\rangle[/math] ;
  • Шаг 8: [math]da[/math] — нет. В таблицу: [math]\langle11\rangle[/math] [math]da[/math] . В поток: [math]\langle3\rangle[/math] ;
  • Шаг 9: [math]aba[/math] — есть в таблице; [math]abac[/math] — нет. В таблицу: [math]\langle12\rangle[/math] [math]abac[/math] . В поток: [math]\langle9\rangle[/math] ;
  • Шаг 10: [math]ca[/math] — есть в таблице; [math]cab[/math] — нет. В таблицу: [math]\langle13\rangle[/math] [math]cab[/math] . В поток: [math]\langle8\rangle[/math] ;
  • Шаг 11: [math]ba[/math] — есть в таблице; [math]bae[/math] — нет. В таблицу: [math]\langle14\rangle[/math] [math]bae[/math] . В поток: [math]\langle6\rangle[/math] ;
  • Шаг 12: И, наконец последняя строка [math]e[/math] , за ней идет конец сообщения, поэтому мы просто выводим в поток [math]\langle4\rangle[/math] .
Текущая строка Текущий символ Следующий символ Вывод Словарь
Код Биты
ab a b 000 5: ab
ba b a 1 001 6: ba
ac a c 000 7: ac
ca c a 2 010 8: ca
ab a b
aba b a 5 0101 9: aba
ad a d 0000 10: ad
da d a 3 0011 11: da
ab a b
aba b a
abac a c 9 1001 12: abac
ca c a
cab a b 8 1000 13: cab
ba b a
bae a e 6 0110 14: bae
e e 4 0100

Итак, мы получаем закодированное сообщение [math]0 1 0 2 5 0 3 9 8 6 4[/math] и его битовый эквивалент [math]000 001 000 010 0101 0000 0011 1001 1000 0110 0100[/math] . Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало [math]16[/math] символов, следовательно длина сообщения составляла [math]3 \cdot 16 = 48[/math] бит.

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила [math]4 \cdot 3 + 7 \cdot 4 = 40[/math] бит, что на [math]8[/math] бит короче исходного.

Декодирование [ править ]

Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

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

Данные На выходе Новая запись
Биты Код Полная Частичная
000 a 5: a?
001 1 b 5: ab 6: b?
000 a 6: ba 7: a?
010 2 c 7: ac 8: c?
0101 5 ab 8: ca 9: ab?
0000 a 9: aba 10: a?
0011 3 d 10: ad 11: d?
1001 9 aba 11: da 12: aba?
1000 8 ca 12: abac 13: ca?
0110 6 ba 13: cab 14: ba?
0100 4 e 14: bae

Примечание [ править ]

Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например [math]aaaaaaaaaaaaa. [/math] или [math]303030[/math] … и т. п. Их непосредственное сжатие будет генерировать выходной код [math]005000600007. [/math] . Спрашивается, можно ли в этом частном случае повысить степень сжатия?

Оказывается, это возможно, если оговорить некоторые действия:

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

  • Пусть словарь состоит из слов : [math]a, b, c, d, e[/math] . Будем кодировать стоку [math] aaaaaaaaaa [/math]
  • Итак, кодировщик заносит первую [math]a[/math] в строку, ищет и находит [math]a[/math] в словаре под номером [math]\langle0\rangle[/math] . Добавляет в строку следующую [math]a[/math] , находит, что [math]aa[/math] нет в словаре. Тогда он добавляет запись [math]\langle5\rangle[/math] : [math]aa[/math] в словарь и выводит метку [math]\langle0\rangle[/math] ( [math]a[/math] ) в выходной поток.
  • Далее строка инициализируется второй [math]a[/math] , то есть принимает вид [math]a?[/math] вводится третья [math]a[/math] , строка вновь равна [math]aa[/math] , которая теперь имеется в словаре.
  • Если появляется четвертая [math]a[/math] , то строка [math]aa?[/math] равна [math]aaa[/math] , которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка [math]\langle5\rangle[/math] ( [math]aa[/math] ).
  • После этого строка инициализируется третьей [math]a[/math] , и т.д. и т.п. Дальнейший процесс вполне ясен.
Слово Номер в словаре
a [math]\langle0\rangle[/math]
b [math]\langle1\rangle[/math]
c [math]\langle2\rangle[/math]
d [math]\langle3\rangle[/math]
e [math]\langle4\rangle[/math]
Текущая строка Текущий символ Следующий символ Вывод Словарь
Код Биты
aa a a 000 5: aa
aa a a
aaa a a 5 101 6: aaa
a a a
aa a a
aaa a a
aaaa a a 6 110 7: aaaa
a a a
aa a a
aaa a a
aaaa a a 7 111 8: aaaaa

В результате на выходе получаем последовательность [math]0567[/math] . При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила [math] 4 \cdot 3 = 12 [/math] бит, что на [math] 7 \cdot 3 — 12 = 9[/math] бит короче кодирования стандартным методом LZW. Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это [math]\langle0\rangle[/math] , которому соответствует символ [math]a[/math] . Затем читает код [math]\langle5\rangle[/math] , но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть [math]a[/math] . Поэтому он добавит в свою таблицу строку [math]aa[/math] с кодом [math]\langle5\rangle[/math] , а в выходной поток поместит [math]aa[/math] . И так может быть раскодирована вся цепочка кодов.

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

Как расшифровать LZW в GIF файле?

Дано задание, в котором нужно считать GIF файл(не анимированный) и вывести его на экран. Загвоздка в том, что мне его надо считать массивом байт. Считать легко. Я разобрался(более менее) в структуре GIF, осталось декомпрессировать цвета, которые сжаты с помощью LZW. Нашёл статью на хабре про структуру гиф (Вот), но там только сжатие и при этом я не понимаю, как там цифры с решёткой сопоставить с уже сжатыми данными. Есть много примеров со строками, но там есть просто буквы, а в GIF 16-тиричная система байт.

В общем, как декомпрессировать цвета, подскажите пожалуйста.

П.с. Тяжело объяснить суть непонимания, но надеюсь, суть ясна.

GIF — GIF

Имя файла расширения .gif
Интернет-тип носителя image/gif
Тип кода гифф
Равномерное идентификатор типа (ИМП) com.compuserve.gif
Магическое число GIF87a / GIF89a
Разработан CompuServe
Первый выпуск 1987 ; 32 лет назад ( Тысяча девятьсот восемьдесят семь )
Последний релиз
Тип формата без потерь растрового формата изображения
Веб-сайт WWW .w3 .org / Графика / GIF / спец-gif89a .txt

Формат Graphics Interchange ( GIF , / dʒ ɪ е / JIF или / ɡ ɪ е / ФВМС ), представляет собой растровый формат изображения , который был разработан группой в онлайн — услуг провайдера CompuServe во главе американского компьютера ученый Стив Уилайт 15 июня, 1987. с тех пор она вступит в широкое использование на World Wide Web в связи с ее широкой поддержки и портативности.

Формат поддерживает до 8 бит на пиксель для каждого изображения, что позволяет одно изображение , чтобы ссылаться на свою собственную палитру до 256 различных цветов , выбранных из 24-битного RGB цветового пространства. Он также поддерживает анимацию и позволяет отдельную палитру до 256 цветов для каждого кадра. Эти ограничения палитры делают GIF менее пригодны для воспроизведения цветных фотографий и других изображений с цветовыми градиентами, но хорошо подходит для более простых изображений , таких как графики и логотипы с твердой областью цвета.

GIF изображения сжимаются с использованием Лемпеля-Зив-Велч (LZW) сжатие данных без потерь техники , чтобы уменьшить размер файла без ухудшения качества изображения. Этот метод сжатия был запатентован в 1985 году полемики по поводу лицензионного соглашения между патентным программным обеспечением держателем, Unisys и CompuServe в 1994 году стимулировало развитие Portable Network Graphics (PNG) стандарта. К 2004 году все соответствующие патенты истекли.

содержание

история

CompuServe ввел GIF 15 июня 1987 года , чтобы обеспечить формат изображение цвета для их загрузки файла областей, заменив их ранее длины кодирования (RLE) формат, который был черно-белым только. GIF стал популярным , поскольку он используется сжатие данных LZW , который был более эффективен , чем кодирования длин серий , что форматы , такие как те , которые используются PCX и MacPaint , и , следовательно , могут быть загружены в достаточно короткое время довольно большие изображения, даже при очень медленных модемов ,

Оригинальная версия GIF называлась 87а . В 1989 году CompuServe выпустила улучшенную версию, называемую 89а , которая добавлена поддержка задержки анимации (несколько изображений в потоке уже были поддержаны в 87а), прозрачные цвета фона, и хранения метаданных конкретного приложения. Спецификация 89а также поддерживает включение текстовых меток в виде текста (не встраивая их в графических данных), но есть немного контроля над шрифтами дисплея, эта функция не используется широко. Обе версии можно отличить, посмотрев на первые шесть байт из файла ( « магическое число » или подписи), который, когда интерпретируется как ASCII , читать «GIF87a» и «GIF89a», соответственно.

CompuServe поощрять принятие GIF, предоставляя загружаемые утилиты преобразования для многих компьютеров. К декабрю 1987 года, например, Apple , IIGS пользователь может просматривать фотографии , созданные на Atari ST или Commodore 64 . GIF был один из первых двух форматов изображений , обычно используемых на веб — сайтах, другой черно-белый XBM .

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

В мае 2015 года Facebook добавлена поддержка GIF.

Лингвистические характеристики

Как существительное , слово GIF встречается в новых изданиях многих словарей. В 2012 году американское крыло Oxford University Press признал GIF в качестве глагола , а также, что означает «создать GIF — файл», как в «GIFing была идеальной средой для распространения сцены из летних Олимпийских играх ». Лексикографы пресса — голосовали это их слово года , заявив , что GI превратились в «инструмент с серьезными приложениями , включая исследование и журналистики».

Произношение GIF

Создатели формата произносили слово , как «мкф» с мягким «G» / dʒ ɪ е / , как и в «джин». Стив Уилайт говорит , что предполагаемое произношение намеренно повторяет американскую арахисовое масло марки мкф , и сотрудники CompuServe часто говорят , что «Разборчивые разработчики выбирают GIF», подмены телерекламы этого бренда. Слово в настоящее время также широко произносятся с жестким «G» / ɡ ɪ е / , как в «дар». В 2020 году, неформальный опрос на сайте программирования Stack Overflow показал некоторое численное предпочтение аппаратно произношение «G», особенно среди респондентов в Восточной Европе, хотя и программно «G» и выговаривая каждую букву по отдельности были найдены , чтобы быть популярным в Азии и развивающиеся страны.

Heritage Dictionary американского цитирует и, указывая на «камеру jПри» в качестве основного произношения, а Кембриджский словарь американского английского языка предлагает только жесткосферическое «G» произношение. Merriam-Webster Энциклопедический словарь и КДИ цитируют оба произношения, но место «GIF» в положение по умолчанию ( «\ GIF, Jif \»). New Oxford American Dictionary дал только «камеры jПри» в своем 2 — м издании , но был обновлен до «мкф, GIF» в 3 — м издании.

Разногласия по поводу произношения привело горячие дебаты в Интернете. По случаю получения награды за достижения в 2013 году Webby Award церемонии, Wilhite отверг жесткосферической «G» произношение, и его выступление привело к 17000 постов на Twitter и 50 новостных статей. Белый дом и телепрограмма Jeopardy! также вступила в дискуссию в течение 2013 года .

использование

  • GIFs пригодны для острой кромки линии искусства (например, логотипы) с ограниченным числом цветов. Это использует сжатие без потерь в формате, который способствует плоским участкам однородного цвета с четко выраженными краями.
  • GIFs может быть использован для хранения низким цвета спрайта данных для игр.
  • GIFs могут быть использованы для небольших анимаций и низкого разрешения видеоклипов.

Формат файла

Концептуально GIF файл описывает фиксированный размером графической области ( «логический экран») заполняется нуль или более «изображения». Многие GIF файлы имеют одно изображение, которое заполняет весь логический экран. Другие делят логический экран на отдельные суб-изображения. Изображения могут также функционировать в качестве кадров анимации в анимированный файл GIF, но опять-таки это не нужно заполнить весь логический экран.

GIF файлы начинаются с фиксированной длины заголовка ( «GIF87a» или «GIF89a») дает версию, а затем с помощью фиксированной длины логического дескрипторе экрана дает размеры пикселей и другие характеристики логического экрана. Дескриптор экрана может также указать наличие и размер глобальной таблицы цвета, который следует дальше, если присутствуют.

После этого файл разделен на сегменты, каждый введенного 1-байтовый часовой:

  • Изображения (введенный 0x2c, с ASCII запятой «» )
  • Блок расширения (введен 0x21, в ASCII восклицательным «!» )
  • Прицеп (один байт значение 0x3B, ASCII , точка с запятой «;» ), который должен быть последним байтом файла.

Изображения начинаются с фиксированной длиной дескриптором изображения, которые могут указывать на наличие и размер Color Table (Local, которое следует дальше, если он присутствует). Данные изображения следующим образом: один байт дает ширину бита некодированных символов (который должен быть по крайней мере 2 бита, даже для двухцветных изображений), а затем связанный список суб-блоков, содержащих данные LZW-кодированию.

Удлинительные блоки (блоки, которые «расширяют» определение 87a посредством механизма, уже определенного в спецификации 87a) состоят из Sentinel, дополнительный байта с указанием типа расширения, и связанным списка субблоков с данными расширения. Блоки расширения, которые изменяют изображение (например, расширение управления Graphic, который определяет дополнительное время задержки анимации и дополнительный прозрачный цвет фона) должны непосредственно предшествовать сегмент с изображением они относятся.

Связанные списки, используемые данные изображений и удлинительные блоки состоят из серии субблоков, каждый субблок, начиная с байтом, давая количество последующих байт данных в субблока (от 1 до 255). Серии субблоков завершаются пустым субблоком (а 0 байт).

Эта структура позволяет файл, который будет обработана, даже если не все части понимается. GIF отмечены 87a может содержать блоки расширения; намерение состоит в том, что декодер может считывать и отображать файл без особенностей, охватываемых расширений, не понимают.

Полная деталь формата файла описывается в спецификации GIF.

Палитры

GIF является палитрой на основе: цвет , используемый в изображении (кадр) в файле имеет свой RGB значение , определенное в таблице палитры , которая может содержать до 256 записей, а также данные для изображения относится к цветам их индексы ( 0-255) в таблице палитры. Определения цвета в палитре можно извлечь из цветового пространства миллионов оттенков (2 24 оттенков, 8 бит для каждого первичного), но максимальное число цветов кадра можно использовать 256. Это ограничение представляется разумным , когда GIF был разработан потому что немногие люди могут позволить себе оборудование для отображения большего количества цветов одновременно. Простая графика, штриховые рисунки, мультфильмы, и полутоновые фотографии обычно требуется меньше , чем 256 цветов.

Каждый кадр может назначить один индекс в качестве «прозрачного» цвета фона: любой пиксель, присвоенного этот показатель принимает на цвете пикселя в том же самом положении от фона, который, возможно, был определен с помощью предыдущего кадра анимации.

Многие методы, в совокупности называемых размываниями , были разработаны , чтобы приблизить более широкий диапазон цветов с небольшой цветовой палитрой, используя пиксели из двух или более цветов , чтобы аппроксимировать в-между цветами. Эти методы жертвуют пространственное разрешение , чтобы приближать глубокое разрешение цвета. Хотя это и не входит в спецификацию GIF, сглаживание может быть использован в дальнейшем изображений , закодированных в формате GIF изображений. Это часто не является идеальным решением для GIF изображений, как из — за потери пространственного разрешения , как правило , делает изображение выглядит нечетким на экране, а также потому , что размывания структура часто мешает сжимаемости данных изображения, работа с основной целью GIF изображения.

В первые дни графических веб — браузеров, графические карты с 8-битовых буферов ( с учетом только 256 цветов) были широко распространены , и это было довольно распространенным , чтобы сделать GIF изображения с помощью палитры websafe . Это обеспечило прогнозируемый дисплей, но серьезно ограничивает выбор цветов. Когда 24-битный цвет стал норма палитры вместо могли быть заселены с оптимальными цветами для отдельных изображений.

Небольшая таблица цветов может быть достаточна для небольших изображений, и держать таблицу цветов маленькой позволяет файл для загрузки быстрее. Оба 87a и 89a характеристики позволяют цветовые таблицы 2 п цветов для любого п от 1 до 8. Большинство графических приложений будет считывать и отображать GIF изображения с любой из этих размеров таблиц; но некоторые не поддерживают все размеры при создании изображений. Таблицы 2, 16 и 256 цветов широко поддерживается.

Истинный цвет

Хотя GIF почти никогда не используется для полноцветных изображений, то можно сделать так. GIF изображение может включать в себя несколько блоков изображения, каждый из которых может иметь свой собственный 256-цветовую палитру, и блоки могут быть выложены плиткой , чтобы создать полный образ. В качестве альтернативы, спецификация GIF89a ввела идею «прозрачного» цвета , где каждый блок изображения может включать в себя свою собственную палитре 255 видимых цветов плюс один прозрачного цвета. Полное изображение может быть создано путем наслаивания блоков изображения с видимой частью каждого слоя , показывая через прозрачные части указанных выше слои.

Оказывать полноцветное изображение в формате GIF, исходное изображение должно быть разбиты на более мелкие участки, не имеющие не более 255 или 256 различных цветов. Каждый из этих регионов затем сохраняется в виде отдельного блока изображения с его собственной локальной палитры и, когда блоки изображения отображаются вместе (либо черепицей или отводками частично прозрачные блоки изображения) появляется полная, полноцветное изображение. Например, нарушая изображение в плитки 16 на 16 пикселей (256 пикселей в общей сложности) гарантирует, что ни одна плитка не имеет больше, чем локальный предел палитры 256 цветов, хотя более крупные плитки могут быть использованы и другие подобные цвета слиты в результате к некоторой потере цвета Информация.

Поскольку каждый блок изображения требует своей локальную таблицы цветов, является файл формат, имеющий множество блоков изображения может быть очень большим, что ограничивает полезность полноцветных GIFs. Кроме того, не все GIF рендеринга программы обрабатывать кафельные или многослойные изображения правильно. Многие программы рендеринга интерпретировать плитки или слои, как кадры анимации и отображать их в последовательности в виде бесконечной анимации с большинством веб-браузеров автоматически отображать кадры с временем задержки 0,1 секунды или более.

Пример GIF-файл

Microsoft Paint сохраняет небольшой черно-белое изображение , как следующий файл GIF. Краска не оптимально использовать GIF; из — за излишне большой таблицу цветов (хранение целых 256 цветов вместо использованных 2) и ширины символа, этот GIF — файл не является эффективным представление 15-пиксельного изображения (показано в увеличенном масштабе выше).

Хотя блок управления Графика Расширение объявляет цветовой индекс 16 (шестнадцатеричное 10), чтобы быть прозрачным, что индекс не используется в изображении. Единственные цветовые индексы, появляющиеся в данных изображения десятичные 40 и 255, которые Глобальный Color Table сопоставляется черный и белый соответственно.

Обратите внимание , что шестнадцатеричные числа в следующих таблицах в прямой порядок байтов порядка байтов, как спецификация формата предписывает.

кодирование изображения

Пиксель изображения данные, сканируется в горизонтальном направлении от верхнего левого, преобразуется кодированием LZW кодов , которые затем преобразуются в байты для хранения в файле. Коды пикселов , как правило , не совпадают с 8-битный размер байтов, так что эти коды упакованы в байты с помощью «маленькой-Endian» схеме: наименее значимого бита первого кода хранится в наименее значащий бит первый байт, старшие биты порядка кода в старшие биты порядка байта, выплескивания в биты низкого порядка следующего байта по мере необходимости. Каждый последующий код сохраняется , начиная с наименьшего значащего бита уже не используется.

Этот поток байт хранится в файле в виде серии «субблоков». Каждый субблок имеет максимальную длину 255 байт и префикс байт, указывающее количество байт данных в субблоке. Серии субблоков завершается пустой субблока (одного байта 0, что указывает на суб-блок с байт 0 данных).

Для получения изображения образца выше обратимого отображения между 9-битовых кодов и байтов, показан ниже.


9-битовый код
(HEX)
двоичный Б
(шестнадцатеричный)
| 00000000 00
100
0101000 | 1 51
028
111111 | 00 FC
0FF
00011 | 011
103
0010 | 1000 28
102
011 | 10000 70
103
10 | 100000 A0
106
1 | 1000001 С1
107
10000011 | 83
| 00000001 01
101
0000000 | 1 01

Небольшое сжатие очевидно: цвета пикселей, определенные первоначально 15 байт точно представлены 12 кодовых байт, включая управляющие коды. Процесс кодирования, который производит 9-битовые коды приведен ниже. Локальная строка накапливает номер цвета пикселя из палитры, без вывода действия до тех пор, как локальная строка может быть найдена в таблице кодов. Существует специальная обработка первых два пикселей, которые прибывают перед таблицей растет от его первоначального размера путем добавления строк. После каждого выходного кода, локальная строка инициализация до последнего цвета пикселя (которые не могут быть включены в выходном коде).

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

Алгоритм LZW требует поиска таблицы для каждого пикселя. Линейный поиск через до 4096 адресов сделает кодирование медленно. На практике эти коды могут быть сохранены в порядке числового значения; это позволяет каждому поиск сделать с помощью SAR ( с регистром последовательного приближения, используемые в некоторых АЦП ), только с 12 магнитуд сравнений. Для этой эффективности дополнительная таблица необходима для преобразования между кодами и фактическими адресами памяти; дополнительный стол и содержание в порядке требуется только тогда , когда новый код будет сохранен , который происходит при значительно меньше скорости пикселей.

декодирования изображения

Декодирование начинается отображение сохраненных байтов обратно в 9-битовых кодов. Они декодируются для восстановления цвета пикселей, как показано ниже. Таблица идентична той, которая используется в кодере строится путем добавления строк по этому правилу:

Длина кода LZW

Более короткие длины кода могут быть использованы для палитр меньших, чем 256 цветов в примере. Если палитра только 64 цветов (так цветовые индексы 6 бит в ширине), символы могут варьироваться от 0 до 63, а ширина символа может быть принята 6 бит, с кодами, начиная с 7 бит. В самом деле, ширина символа не обязательно соответствует размеру палитры: до тех пор, как значения декодированных всегда меньше, чем количество цветов в палитре, символы могут быть любой шириной от 2 до 8, и размера палитры любой степени 2 от 2 до 256. Например, если только первые четыре цвета (значения от 0 до 3) из палитры используются, символы могут быть приняты, чтобы быть 2 бита с кодами, начиная с 3 битами.

С другой стороны, ширина символа может быть установлена ​​на уровне 8, даже если только значения 0 и 1 используются; эти данные будут требовать только таблицы 2-цветной. Несмотря на то, что не было бы никакого смысла при кодировании файла, который так, что-то подобное, как правило, происходит из-за двухцветных изображений: минимальная ширина символ 2, даже если только значения 0 и 1 используются.

Кодовая таблица изначально содержит коды, которые на один бит длиннее , чем размер символа для того , чтобы учесть два специальных коды CLR и конец и коды для строк, которые добавляются в ходе процесса. Когда таблица заполнена увеличивается длина коды , чтобы освободить место для более строк, вплоть до максимального кода 4095 = FFF (шест). По мере того как декодер строит свою таблицу он отслеживает эти увеличения длины коды и она способна распаковать входящие байты соответственно.

несжатый GIF

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

Модифицированный метод кодирования игнорирует построения таблицы LZW и излучает только корневую коду палитры и коды для ясного и STOP. Это дает более простое кодирование (соответствие 1-к-1 между кодовыми значениями и палитрой кодами), но жертвами все сжатия: каждый пиксел в изображении генерирует выходной код, указывающий его индекс цвета. При обработке несжатых GIF, стандартный GIF декодер не будет предотвращено писать строки в его словарную таблицу, но ширина кода никогда не должна увеличиваться, так что вызывает различную упаковку бит в байты.

Если ширина символов равно п, коды ширины п + 1 падения , естественно , в два блока: нижний блок из 2 — н — кодов для кодирования отдельных символов, а также верхний блок из 2 — н — кодов , которые будут использоваться декодером для последовательностей длина больше , чем один. Из этого верхнего блока, первые два кода уже приняты: 2 п для ясного и 2 п + 1 для STOP. Декодер также должен быть предотвращен с использованием последнего кода в верхнем блоке, 2 N + 1 — 1, потому что , когда декодер заполняет этот слот, он будет увеличивать ширину коды. Таким образом , в верхнем блоке есть 2 п — 3 коды , доступные для декодера , который не будет вызывать увеличение ширины кода. Поскольку декодер всегда один шаг позади в поддержании таблицы, это не создает запись в таблице после получения первого кода из кодера, но будет генерировать один для каждого последующего кода. Таким образом , кодер может генерировать 2 п — 2 кодов , не вызывая увеличение ширины коды. Поэтому кодер должен излучать дополнительные Очистить коды с интервалом в 2 н — 2 или меньше кодов , чтобы декодер сброса словаря кодирования. Стандарт GIF позволяет таким дополнительные Очистить коды , которые будут вставлены в данных изображения в любое время. Поток композитного данных разбивается на подблоки , что каждый несут от 1 до 255 байт.

Для образца 3×5 изображений выше, следующие 9-битные коды представляют собой «чистый» (100), а затем пиксели изображения в порядке сканирования и «стоп» (101).

После того, как вышеуказанные коды отображаются в байты, несжатый файл отличается от сжатого файла, таким образом:

пример сжатия

Тривиальный пример большого изображения сплошного цвета демонстрирует сжатие LZW с переменной длиной слова, используемое в GIF файлах.

Последний 9-битный код

Последний 10-битный код

Последний 11-битный код

Кодовая таблица полная

Код Пиксели Заметки
Количество
Н я
Значение
N я + 256
Длина
(биты)
Этот код
N я
Накопленная
Н яя + 1) / 2
Отношения с использованием N я применять только кампанией с такими же
цветами пикселей до кодирования таблицы не заполнится.
100h 9 Очистить таблицу кодов
1 FFh 1 1 Верхний левый пиксель цвет выбран в качестве самого
высокого показателя 256-цветовой палитры
2 102h 2 3
3

255
103H

1FFh
3

255
6

32640
256

767
200h

3FFh
10 256

767
32896

294528
768

1791
400h

7FFh
11 768

1791
295296

1604736
1792

3839
800h

FFFH
12 1792

3839
1606528

7370880
FFFH 3839 Максимальный код может повторяться для более одного цвета пикселей.
В целом сжатие данных асимптотически приближается к
3839 × 8/12 = 2559 1/3
101h Конец данных изображения

Эти кодовые значения, показанные упакованы в байты, которые затем упакованы в блоки до 255 байт. Блок данных изображения начинается с байта, который объявляет число байтов, чтобы следовать. Последний блок данных для изображения отмечен нулевой блок-байт длины.

Переплетение

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

Чересстрочное изображение делятся сверху вниз на полоски 8 пикселей в высоту, а строки изображения представлены в следующем порядке:

  • Шаг 1: линия 0 (самый верхний линия) от каждой полосы.
  • Pass 2: Линия 4 от каждой полосы.
  • Pass 3: Линии 2 и 6 из каждой полосы.
  • Проход 4: Линии 1, 3, 5 и 7 из каждой полосы.

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

Анимированные GIF

Основная анимация была добавлена в GIF89a спецификации с помощью расширения Graphics Control (GCE), что позволяет различные изображения (кадры) в файле должны быть окрашены с временными задержками, образуя видеоклип . Анимированный файл GIF содержит некоторое количество кадров, которые отображаются последовательно, каждый представил свой собственный GCE, что дает задержку по времени ожидания после того , как кадр рисуются. Глобальная информация в начале файла применяется по умолчанию для всех кадров. Данные потоки-ориентированные, поэтому файл-смещение начала каждого GCE зависит от длины предшествующих данных. В пределах каждого кадра данные изображени LZW закодированный расположено в подблоках до 255 байт; размер каждого субблока объявлен байт , который предшествует ему.

По умолчанию, однако, анимация показывает последовательность кадров только один раз, останавливаясь , когда отображается последний кадр. Поскольку GIF разработан , чтобы позволить пользователям определять новые блоки, Netscape в 1990 — х годах используется блок расширения приложений (предназначенный , чтобы позволить поставщикам , чтобы добавить информацию конкретного приложения в файл GIF) для реализации блока Netscape Application (NAB). Этот блок, расположенный непосредственно перед всеми кадрами анимации, определяет, сколько раз должна быть воспроизведена последовательность кадров. (Значение 0 означает непрерывное отображение.) Поддержка этих повторяющихся анимация первой появилась в Netscape Navigator версии 2.0, а затем распространилась на другие браузеры. Большинство браузеров теперь признают и поддерживают NAB, хотя это не является строго частью спецификации GIF89a.

Следующий пример показывает структуру файла анимации вращающейся Земли (большой) .gif показано (как эскиз) в верхней части статьи.

Задержка анимации для каждого кадра задаются в БКА в сотых долей секунды. Некоторые экономики данных можно где кадр нужно только переписать часть пикселей дисплея, так как дескриптор изображения может определить меньший прямоугольник будет перепроверен вместо всего изображения. Браузеры или другие дисплеи, которые не поддерживают анимированные GIF-файлы, как правило, показывают только первый кадр.

Качество размера и цвета анимированных файлов GIF может значительно изменяться в зависимости от приложения, используемого для их создания. Стратегии для минимизации размера файла включают в себя использование общей глобальную таблицы цветов для всех кадров (а не полная локальная таблицы цветов для каждого кадра) и свести к минимуму количества пикселей, охватываемым в последовательных кадрах (так, что только пиксели, которые изменяются от одного кадра к следующий включены в последнем кадре). Просто упаковка ряда независимых изображений кадра в составную анимацию, как правило, дают большие размеры файлов.

Internet Explorer замедляет GIFs , если частота кадров составляет 20 кадров в секунду или выше и Microsoft сообщает , что Google Chrome и Safari также замедлить некоторые GIF анимацию.

С начала 1995 года Университет Ульма используется анимированный GIF в формате потокового видео в реальном времени показывать управляемую модель железной дороги.

Метаданные

Метаданные могут быть сохранены в GIF-файлов в качестве комментария блока, простой текстовый блок, или расширение приложений блока конкретного приложения. Несколько графических редактора используют неофициальные блоки расширения приложения, чтобы включать в себя данные, используемые для формирования изображения, так что он может быть восстановлен для дальнейшего редактирования.

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

Extensible Metadata Platform (XMP) стандарт метаданных введен негласный , но теперь широко распространенное расширение приложений блок «Data XMP» для включения данных XMP в GIF — файлов .. Так как данные XMP кодируется с использованием UTF-8 без символов NUL, нет 0 байт в данных. Вместо того , чтобы разбить данные в формальные подблоки, блок расширения завершается с прицепом «волшебным» , который направляет любое приложение обработки данных в виде субблоков до конечных 0 байт , что завершает субблоку цепь.

Unisys и LZW патентных прав

В 1977 и 1978 годах, Иаков Зив и Авраам Лемпель опубликовал пару статей о новом классе алгоритмов сжатия данных без потерь, в настоящее время совместно именуемые LZ77 и LZ78 . В 1983 году Терри Уэлч разработал быстрый вариант LZ78 , который был назван Лемпела-Зива-Уэлча (LZW).

Welch подал заявку на патент для метода LZW в июне 1983 года в результате патента, США 4558302 , выданный в декабре 1985 года был назначен Sperry Corporation , который впоследствии слился с Burroughs Corporation в 1986 году и формируется Unisys . Другие патенты были получены в Великобритании, Франции, Германии, Италии, Японии и Канаде.

В июне 1984 года, статья Уэлч была опубликована в IEEE журнала , который публично описал метод LZW впервые. LZW стал популярным методом сжатия данных и, когда патент был выдан, Unisys заключила лицензионные соглашения с более чем ста компаний.

Популярность LZW привело CompuServe , чтобы выбрать его в качестве метода сжатия для их версии GIF, разработанной в 1987 году В то время, CompuServe не было известно о патенте. Unisys стало известно , что версия GIF используется метод сжатия LZW и вступили в переговоры о лицензировании с CompuServe в январе 1993 года последующее соглашение было объявлено 24 декабря 1994 года Unisys заявили , что они ожидали , что все крупные коммерческие онлайновые информационные услуги компании , использующей патент LZW лицензировать технологию от Unisys по разумной ставке, но они не требуют лицензирования, или сборы , которые будут оплачены, в некоммерческих, некоммерческих GIF-приложений, в том числе для использования на он-лайн услуг ,

После этого заявления, было широко распространено осуждение CompuServe и Unisys, и многие разработчики программного обеспечения пригрозили прекратить использование GIF. Формат PNG (см ниже) был разработан в 1995 году в качестве предполагаемой замены. Однако получение поддержки от создателей веб — браузеров и других программ для формата PNG оказалось трудным и не было возможности заменить GIF, PNG , хотя постепенно увеличивается в популярности. Таким образом, были разработаны варианты GIF без сжатия LZW. Например , библиотека libungif, основанный на Eric S. Raymond giflib «с, позволяет создавать GIFs , которые следовали за формат данных , но избежать возможности сжатия, что позволяет избежать использования патента Unisys LZW. В 2001 году д — ра Dobb в статье описана другая альтернатива для сжатия LZW, на основе квадратных корней.

В августе 1999 года Unisys изменил детали их лицензирования практики, объявляя возможность для владельцев определенных некоммерческих и частных веб — сайтов для получения лицензии на оплату лицензионного сбора на одноразовое $ 5000 или $ 7500. Такие лицензии не требуются для владельцев веб — сайтов или других пользователей GIF , которые использовали лицензионное программное обеспечение для создания GIF — файлов. Тем не менее, Unisys был подвергнут тысячи интернет — атак и оскорбительных писем от пользователей , полагая , что они собираются платить $ 5000 или подали в суд за использование GIFs на своих сайтах. Несмотря на предоставление бесплатных лицензий на сотни некоммерческих организаций, школ и правительств, Unisys была совершенно не в состоянии генерировать любую хорошую рекламу и продолжает быть осуждены лицами и организациями , такие как Лига для программирования свободы , которые начали «Сжечь все GIFs» кампанию в 1999.

Патент США LZW истек 20 июня 2003 года Патенты аналогов в Великобритании, Франции, Германии и Италии истек 18 июня 2004 года, японские патенты истек 20 июня 2004 года, а также канадский патент истек 7 июля 2004 г. Следовательно, , в то время как Unisys имеет дополнительные патенты и заявки на патенты, относящиеся к совершенствованию техники LZW, GIF теперь может свободно использоваться.

альтернативы

Portable Network Graphics (PNG) был разработан в качестве замены GIF, чтобы избежать нарушения патента Unisys’ на технологии сжатия LZW. PNG обеспечивает лучшее сжатие и больше возможностей , чем GIF, анимацию будучи единственным существенным исключением. PNG является более подходящим , чем GIF в тех случаях , когда в истинном цвете изображения и альфа — прозрачность требуются.

Хотя поддержка формата PNG пришли медленно, новые веб — браузеры обычно поддерживают PNG. Более старые версии Internet Explorer не поддерживает все функции , PNG. Версии 6 и более ранние версии не поддерживают альфа — канал прозрачности без использования Microsoft-специфических расширений HTML. Гамма — коррекция PNG изображений не поддерживается до версии 8, и отображение этих изображений в более ранних версиях может иметь неправильный оттенок.

Для идентичных 8-бит (или ниже) данных изображения, PNG файлы, как правило, меньше, чем эквивалентные GIFs, за счет более эффективных методов сжатия, используемых при кодировании PNG. Полная поддержка GIF усложняется главным образом сложной структуры холста он позволяет, хотя это то, что позволяет компактные функции анимации.

форматы анимации

MNG первоначально был разработан в качестве PNG на основе решения для анимации. MNG достигла версии 1.0 в 2001 году, но лишь немногие приложения поддерживают его.

В 2006 году , расширение в формате PNG под названием APNG был предложен в качестве альтернативы формату MNG по Mozilla . APNG дают возможность анимировать PNG файлов, сохраняя при этом обратную совместимость в декодеров , которые не могут понять анимации кусок ( в отличие от MNG). Более старые декодеры будут просто визуализировать первый кадр анимации. Группа PNG официально отвергнута APNG в качестве официального расширения на 20 апреля 2007 г. Там было несколько последующих предложений по простому анимированным графическому формату на основе PNG , используя несколько различных подходов. Тем не менее, анимированные Portable Network Graphics еще в стадии разработки Mozilla и поддерживается в Firefox 3 в то время как поддержка MNG была сброшена .. APNG в настоящее время поддерживается большинством основных веб — браузеров , включая Chrome , начиная с версии 59.0 и Opera и Firefox.

Встроенный Adobe Flash объектов и MPEGs используется на некоторых веб — сайтах , чтобы отобразить простое видео, но требует использования дополнительного модуля браузера. WebM и WebP находятся в стадии разработки и поддерживаются некоторыми браузерами. Другие варианты для веб — анимации включают в себя обслуживание отдельных кадров с помощью AJAX , или оживляющий SVG изображений с помощью JavaScript или SMIL .

С появлением широко распространенной поддержкой HTML5 тега в большинстве веб — браузеров, некоторые веб — сайты используют петельчатую версию видеотега генерируемой JavaScript функций. Это дает появление GIF, но с размером и скоростью преимущества сжатого видео. Характерные примеры являются Gfycat и Imgur и их GIFV metaformat, который действительно тег видео воспроизведения зацикленной MP4 или WebM сжатого видео.

Описание алгортма lzw коментарии по поводу gif

Mark R. Nelson
Перевод: Запольский С.А.

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 — 255 соответствуют отдельным байтам, а коды 256 — 4095 соответствуют подстрокам.


Сжатие.

Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и , если так, выводит существующий код без генерации нового.

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
СИМВОЛ = очередной символ из входного потока
IF СТРОКА+СИМВОЛ в таблице строк THEN
СТРОКА = СТРОКА+СИМВОЛ
ELSE
вывести в выходной поток код для СТРОКА
добавить в таблицу строк СТРОКА+СИМВОЛ
СТРОКА = СИМВОЛ
END of IF
END of WHILE
вывести в выходной поток код для СТРОКА

Рис. 1 Алгоритм сжатия

Простая строка, использованная для демонстрации алгоритма, приведена на рис.2. Входная строка является кратким списком английских слов, разделенных символом «/». Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки «/W» в таблице. Когда он не находит эту строку, то генерирует код для «/» и добавляет в таблицу строку «/W». Т.к. 256 символов уже определены для кодов 0 — 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву («E»), добавляет вторую подстроку («WE») в таблицу и выводит код для буквы «W».

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов «/» и «W», не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка : /WED/WE/WEE/WEB/WET

Вход(символы) Выход(коды) Новые коды и соответствующие строки
/W / 256 = /W
E W 257 = WE
D E 258 = ED
/ D 259 = D/
WE 256 260 = /WE
/ E 261 = E/
WEE 260 262 = /WEE
/W 261 263 = E/W
EB 257 264 = WEB
/ B 265 = B/
WET 260 266 = /WET
T

Рис. 2 Процесс сжатия

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


Распаковка.

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Алгоритм распаковки представлен на рис. 3. В соответствии с алгоритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда читает из входного потока новый код. Все, что ему необходимо сделать в добавок — это перевести каждый входной код в строку и переслать ее в выходной поток.

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 3 Алгоритм распаковки

На рис. 4 приведена схема работы алгоритма на основе сжатых данных, полученных в выше приведенном примере. Важно отметить, что построение таблицы строк алгоритмом распаковки заканчивается как раз тогда, когда построена таблица строк алгоритма сжатия.

Входные коды : / W E D 256 E 260 261 257 B 260 T

Вход СТАРЫЙ КОД СТРОКА СИМВОЛ Новый вход таблицы
/ / /
W / W W 256 = /W
E W E E 257 = WE
D E D D 258 = ED
256 D /W / 259 = D/
E 256 E E 260 = /WE
260 E /WE / 261 = E/
261 260 E/ E 262 = /WEE
257 261 WE W 263 = E/W
B 257 B B 264 = WEB
260 B /WE / 265 = B/
T 260 T T 266 = /WET

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.


Ловушка.

К несчастью прекрасный , простой алгоритм распаковки, приведенный на рис. 4, является все таким слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка «JOEYN» определена в таблице с кодом 300. Когда последовательность «JOEYNJOEYNJOEY» появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.

Входная строка : . JOEYNJOEYNJOEY.

Вход(символы) Выход(коды) Новые коды и соотв. строки
JOEYN 288 = JOEY 300 = JOEYN
A N 301 = NA
. . .
. . .
. . .
JOEYNJ 300 = JOEYN 400 = JOEYNJ
JOEYNJO 400 401 = JOEYNJO

Рис. 5 Некоторые проблемы

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку «JOEYN» и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное «J», к строке. Результатом является правильный перевод кода 400 в строку «JOEYNJ».

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА = перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 6 Модифицированный алгоритм распаковки


Реализация.

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.

Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.

Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка «/WEE» хранится как код 260 и символ «E». Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ «E». Наконец, код 256 хранится как «/» плюс «W».

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов : code_value[i], prefix_code[i] и append_character[i].

Когда необходимо добавить новый код в таблицу, используется хэшфункция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.

Хэш-функция, использованная в этой программе — простая «xor»-типа хэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице — меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.

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

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

Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.


Результаты.

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.

Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях «сжатый» файл может превосходить по своим размерам исходный текст. Небольшой эксперимент даст Вам представление о том, хорошо или плохо упаковываются Ваши данные.


Ваша реализация.

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

Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как «ARC», решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, «ARC» читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.

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

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

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

И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.

Коротко

Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора «C». Она должна нормально работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка «C».

Реализация компиляторов «C» для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются и облегчается использование кодов большей длины.

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

Анализ растровых данных GIF — LZW

Я пытаюсь распаковать GIF в PHP и, похоже, все, кроме декомпрессии LZW. Я сохранил изображение, которое показано:

Это изображение равно 3 x 5:

Я решил пройти вручную в Binary и проанализировать этот файл. Результат ручного разбора приведен ниже. Я все еще придерживаюсь того, как здесь декодировать растровые данные. Может ли кто-нибудь сломать, как растровые данные становятся изображением? Я смог сломать одно изображение, но ничего больше (не этот образ). Я опубликовал свое понимание того, как это должно сломаться, но я, очевидно, делаю это неправильно.

Моя попытка

Исходный размер кода = 3 Прочитайте 2 бита за раз

В этот момент я уже ошибаюсь. Первый цвет должен быть синим.

Ресурсы, которые я использовал:

GIF-парсер

Вы сказали, что хотите написать свой собственный синтаксический анализатор GIF, чтобы понять, как он работает. Я предлагаю вам посмотреть исходный код любой из библиотек, содержащих GIF-считыватели, такие как фактическая эталонная реализация GIFLIB. Соответствующий исходный файл dgif_lib.c ; запустите в slurp для декодирования или перейдите в реализация декомпрессии LZW.

Вот как ваше изображение декодируется.

Я думаю, что проблема заключалась в том, что вы неправильно разбивали входные байты на коды LZW.

Число цветов (0b001 + 1) * 2 = 4 .

Размер кода начинается с 2 + 1 = 3 бит.

Итак, начальный словарь

Теперь GIF упаковывает коды LZW в байты в первом порядке LSB. Соответственно, первый код сохраняется как 3 младших значащих бита первого байта; второй код — следующие 3 бита; и так далее. В вашем примере (первый байт: 0x84 = 10000100 ) первые 2 кода, таким образом, 100 (clear) и 000 (синий). Все это

разделяется на коды (переключается на 4-битные группы после считывания наивысшего 3-битного кода, 111 ) как

Итак, начинается вывод (обертывание до 3 столбцов):

Решение без написания собственного GIF-считывателя

Для использования, отличного от вашего собственного назидания, попробуйте это.

Несколько примечаний

  • Ваш GIF файл — GIF89a. Вы связаны со спецификацией GIF87a; спецификация 89a здесь.
  • Вы, похоже, обеспокоены тем, что использование библиотеки для анализа изображения ухудшит производительность. Это не имеет никакого смысла. Библиотеки обычно реализуются в оптимизированном C; ваше ручное решение будет написано на PHP, интерпретируемом языке.
  • Вы упомянули PCX, какие библиотеки, такие как imagemagick, поддерживают.

Или просто используйте PNG

В соответствии с Руководство по программированию ZPL 2 поддерживается PNG. Например, команда

DY (Загрузить графику) принимает параметр b (format), для которого параметр P (PNG) является необязательным, кроме GRF по умолчанию. См. Также Печать изображений PNG на сетевой принтер zebra.

Существует множество библиотек для преобразования GIF в PNG. Вы можете использовать ImageMagick (привязка PHP) или просто использовать функции PHP imagecreatefromgif и imagepng .

Я не могу помочь вам с декодированием LZW, но не будет ли проще использовать библиотечную функцию, например imagecreatefromgif() из расширения PHP GD для анализа файла GIF и извлечения данных изображения, которые затем можно преобразовать в целевой формат?

Этот сайт является отличным ресурсом о формате GIF и предлагает отличное объяснение процесса сжатия и декомпрессии LZW:

Хорошо, что вы хотите знать, как делать LZW, не используя библиотеки, написанные кем-то другим. LZW не декодирует изображения по пикселям. Он ищет повторяющиеся блоки в потоке данных, сохраняет их в словаре и ссылается на них. Если 100 пикселей повторяются где-то только один код используется для воспроизведения 100 пикселей вместо 100, как с растровыми изображениями (BMP). Вот почему GIF отлично подходит для диаграмм, где у вас может быть много серий из 100 белых пикселей, а затем несколько черных, чтобы нарисовать линию. С другой стороны, это отвратительно для фотографий, потому что очень мало длинных повторов, и GIF обычно ограничен 256 цветами, если вы не используете некоторые сложные трюки.

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

Илон Маск рекомендует:  Что такое код fillpoly
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL