что значит пнг в аниме

PNG формат — это что такое простыми словами и как его создать? А также его преимущества и недостатки

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

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

PNG формат — что это такое простыми словами?

ПНГ – это один из самых популярных форматов для фото.

Появился он уже очень давно, поэтому сейчас ПНГ открывается на любом устройстве.

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

Эта базовая программа для работы с изображениями.

Очевидно, что ей не хватает форматов, но пройти мимо ПНГ там нельзя.

Главное преимущество такого формата заключается в том, что он позволяет сохранять фотки с прозрачным фоном.

И это делает его практически незаменимым для всего.

Например, вы хотите добавить на фотографию какой-то объект.

Вам не нужно будет каждый раз его вырезать, ведь можно просто сохранить в ПНГ.

Да, со временем люди научились с помощью зелёного фона решать эту проблему.

Но если у вас нет под рукой Фотошопа, то ничем этот способ не поможет.

Да и там качество после такой обрезки оставляет желать лучшего.

Также png будет очень хорошо смотреться на сайтах.

Всё дело в том, что он позволяет придавать объектам и фотографиям лучшую форму.

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

Преимущества и недостатки PNG

Давайте сразу оговоримся.

В этом пункте мы будем сравнивать png с похожими по формату файлами.

Всё дело в том, что есть условные гифки, которые иногда путают с похожими форматами.

Очевидно, что у них будут совсем другие преимущества, ведь это по сути своей видео.

Этот формат имеет главное преимущество – компактность.

Если вы хотите добавить на свой сайт объекты, но не хотите полностью перекрывать ими весь вид, то это идеальный вариант.

Если вы хотите себе современное оформление, то это идеальный вариант для вас.

Поэтому не стоит подходить со скептицизмом к возможности добавить к себе на страницы такой формат.

Также преимущество пнг заключается в том, что такой формат очень легко менять.

Если вы хотите добавить какой-то объект на несколько фотографий, то вам точно нужно сохранить его в пнг.

Но при этом у такого типа файлов есть и свои недостатки.

Самый заметный из них – большие размеры.

Допустим, вы делаете превью на Ютуб.

Если вы сохраните в ПНГ, то оно может не пройти из-за того, что весит больше 2 МБ.

И это при достаточно среднем качестве.

Аналогично и со своим сайтом только здесь картинка загрузится, но и время загрузки вашего сайта увеличится.

А также ПНГ просто не всегда подходит.

В некоторых местах этот формат не распознаётся.

И тогда вместо красивого объекта вы получите красивый объект на чёрном квадрате.

Или даже шахматной доске.

Стоит ли использовать ПНГ и как его сделать?

Давайте сначала поговорим о том, как сделать пнг.

Для этого можно воспользоваться Фотошопом, Paint и другими графическими редакторами.

Просто во время сохранения документа укажите нужный формат.

После этого у вас будет файл формата пнг.

А вот стоит ли добавлять пнг – это более интересный вопрос.

Допустим, что вам нужна картинка на Ютуб.

Тогда пнг точно не нужен, так как загрузить получится лишь среднюю по качеству картинку.

Аналогично стоит поступить и владельцам мобильных сайтов.

Всё же мобильные телефоны точно не справятся с такой нагрузкой.

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

А вот на версии для компьютера можно использовать пнг.

Но здесь важно понимать, что иногда форма объектов не играет значения.

Допустим, что вы делаете какой-то информационный сайт.

И там нет разницы, поставите ли вы квадратный объект или необычной формы.

Ведь текст всё равно будет квадратным.

Ну и отказываться от этого формата не стоит, если вы регулярно работаете с фотографиями.

Так вы сможете легко и быстро добавить на них новые и интересные объекты.

Учитывая, что вам так и так пришлось бы тратить время на его вырезание, пнг вообще не отнимет у вас много времени.

PNG формат. Как сделать PNG картинку? — смотреть видео

Заключение

Вот вы и узнали, что такое PNG формат.

На данный момент это один из двух лучших и самых популярных формата для изображений.

Он выделяется ещё и тем, что позволяет удалить фон.

А это очень удобно, если вы хотите добавить какой-нибудь объект.

Хотя стоит учитывать, что на некоторых сайтах такие фокусы не поддерживаются.

Сделать такой формат можно и в Photoshop, и в Paint.

При этом в двух случаях вам нужно будет лишь сохранить документ в правильном формате.

А ещё при работе с пнг форматом стоит учитывать его вес.

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

В интернете регулярно спорят о том, какой формат лучше, jpg или png. А что думаете вы?

P.S. А еще мы предоставляем услуги по продвижению ваших аккаунтов и групп в социальных сетях. Ознакомиться с ними вы сможете на этой странице

P.S.S. Чтобы написать данную статью, было потрачено много сил и времени. И если она принесла пользу вам, то возможно она принесет пользу и вашим друзьям.

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

А хотите первыми узнавать об обновлениях? Подписывайтесь на новости блога

Источник

Как это устроено: структура изображений в формате PNG. Разбираем на примере

Привет! В этой статье я познакомлю вас с устройством изображений в формате PNG, а так же с механизмом работы алгоритма Deflate. Мы на примере рассмотрим все аспекты этой темы. Надеюсь, вам будет интересно.

Дисклеймер

Данный материал не призван быть максимально объективным и академически верным. Автор статьи (в дальнейшем — я и другие личные местоимения первого лица) мог упускать некоторые моменты, а некоторые рассматривать лишь с одной стороны. Статья была рождена на свет исключительно из спортивного интереса, а также желания лучше понимать то, с чем я работаю каждый день. Если ты, дорогой читатель, не согласен со мной или считаешь, что я забыл дописать что-то очень важное, то, пожалуйста, напиши об этом в комментариях. Этим сотрудничеством мы сможем добиться ликвидации пробелов в знаниях и, быть может, сделать мир чуточку лучше.
Тем не менее, данная статья поможет начинающим примерно понять внутреннее устройство PNG (о котором и идёт речь), что создаст основу для дальнейшего развития.
В разделе «материалы» я оставил ссылки на полезные статьи и спецификации PNG и zlib, которые помогли мне понять всё то, о чём я написал (и даже больше). Иногда я прямо указываю на них, о чём пишу в виде «ссылка #<номер ссылки>».

Пример изображения

Внутреннее устройство PNG мы будем разбирать на примере маленького изображения 2 x 2 пикселя. Ссылку на него я оставлю в разделе «материалы» в нижней части страницы.
Вот так выглядит увеличенная копия изображения:

» data-medium-file=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/example-max-min.png?fit=200%2C200&ssl=1″ data-large-file=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/example-max-min.png?fit=200%2C200&ssl=1″ src=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/example-max-min.png?resize=200%2C200&ssl=1″ alt=»example-max-min» width=»200″ height=»200″ data-recalc-dims=»1″ />

Долой длинные вступления. Начинаем!

Структура PNG

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

Любой файл PNG начинается со следующей последовательности байтов (в шестнадцатеричном представлении):

Это так называемая подпись PNG (PNG file signature). 50 4E 47 — как раз и соответствуют символам P N и G из таблицы ASCII. Наличие данной строки указывает программе-декодеру, что она имеет дело с классическим изображением формата PNG, которое состоит из последовательности чанков (об этом ниже), первый из которых — это IHDR, а последний — IEND. Отчасти именно эта подпись позволяет большинству программ преспокойно прочитать изображение PNG, даже если у него в качестве расширения указан, скажем, JPEG.

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

Каждый чанк состоит из следующих обязательных частей:
1. Length — информация о длине чанка. Нужна для того, чтобы декодер знал, когда заканчивается тот или иной чанк. Записывается при помощи 4 байт.
2. Chunk type — тип чанка. У каждого из них есть своё собственное предназначение, поэтому программа интерпретирует их по-разному. 4 байта.
3. Chunk data — непосредственно данные, которые содержит чанк. Длина зависит от того, что было указано в поле Length. Может быть пустым.
4. CRC — контрольная сумма Length и Chunk type, высчитанная при помощи алгоритма CRC-32. 4 байта.

Все чанки можно разделить на обязательные (critical) и вспомогательные (ancillary). Самые догадливые уже всё поняли, но я, всё же, опишу несколькими словами их различия. Обязательные чанки должны присутствовать в любом PNG-изображении, а вспомогательные — нет (вот это новость!). Отсутствие обязательного чанка вызовет ошибку, а вот отсутствие вспомогательного, даже если на него ссылается какой-нибудь другой чанк, декодер проигнорирует.

Названия обязательных чанков всегда начинаются с прописной буквы, а вспомогательных — со строчной (например IDAT — обязательный, а вот tIME — нет).

К обязательным чанкам относятся:
IHDR — содержит сведения об изображении: ширина, высота, глубина цвета и другие.
PLTE — содержит перечень цветов, используемых в изображении. Является обязательным, но в некоторых случаях может отсутствовать. Об этом немного позже.
IDAT — чанк, содержащий непосредственно данные изображения.
IEND — чанк, указывающий программе-декодеру на окончание файла. Данных не содержит.

Перечень вспомогательных чанков можно найти в документации PNG (ссылка #1), а обязательные мы разберем немного подробнее:

Это самый первый из обязательных чанков. Важно запомнить, что он должен располагаться в самом начале документа. Состоит из 13 байт:
4 байта — ширина изображения
4 байта — высота изображения
1 байт — глубина цвета (bit depth)
1 байт — цветовая модель (color type)
1 байт — метод сжатия
1 байт — метод фильтрации
1 байт — метод чересстрочной развертки

Наиболее важными для нас являются 9 и 10 байты. Давайте рассмотрим их чуть подробнее.

Color type

Используемая цветовая модель. Может принимать следующие значения:

Глубина цвета

Цветовая глубина — значение, представляющее собой количество битов, которое необходимо для кодирования одного канала. Например, если у нас color type равен RGB, а глубина цвета — 8 бит, то количество битов, необходимое для кодирования 1 пикселя будет равняться 24.

То, что я написал выше, очень важно запомнить или записать, так как эта информация обязательно пригодится нам при расшифровке чанка IDAT.

В нашем случае чанк IHDR является следующей строкой (в шестнадцатеричном представлении):

Теперь нам совершенно не составит труда всё это расшифровать:
Ширина изображения — 2 пикселя.
Высота изображения — 2 пикселя.
Глубина цвета — 16 пикселей на канал.
Color type — 2.
Сжатие, фильтрация и чересстрочная развертка — по нулям.

Что же это означает? Color type равняется 2, значит используется цветовая модель RGB, т.е. комбинация красного, зелёного и синего каналов. Глубина цвета равняется 16, а значит каждый из этих каналов закодирован парой байтов. Отсюда также несложно понять, что для кодирования одного пикселя изображения используется 48 бит или 6 байт. Идём дальше.

Считается обязательным чанком, но фактически является таковым только для color type 3. PLTE содержит от 1 до 256 трёхбайтовых цветов:
1 байт — красный (от 0 до 255)
1 байт — зелёный (от 0 до 255)
1 байт — синий (от 0 до 255)

Подробно на нём останавливаться я не собираюсь, так как на практике color type 3 встречается очень редко. Самые любознательные смогут найти исчерпывающую информацию в спецификации PNG (ссылка #1).

Наконец-то мы добрались до содержимого нашего изображения. Чанк IDAT начинается с 4 байтов — 49 44 41 54, которые, собственно, и декодируется в «IDAT». Согласно спецификации PNG, содержимое IDAT сжато методом Deflate и упаковано в формат zlib. В общем случае чанк состоит из следующих обязательных частей:

Давайте немного подробнее.

Zlib header

Спецификация RFC 1950 говорит нам, что zlib header должен состоять из двух байтов. Первый байт – это Compression Method and Flags (CMF), который в свою очередь содержит:

Второй байт — Flags (FLG), содержит:

Схематично Zlib header можно изобразить так:

В нашем случае: 78 DA или в двоичном представлении 0111100011011010:

Нижними подчёркиваниями я обозначил любые значения, ибо они нам в данный момент безразличны.
Как видим, наше значение не попадает в первый промежуток. Идём дальше:

А вот тут уже интереснее. Значение действительно попадает в промежуток. Теперь смотрим во второй столбец и видим, что необходимое количество битов — 9. Значит берём еще два бита, после чего наша измученная последовательность выглядит так: 110011000.
Теперь, чтобы восстановить исходное значение, нужно воспользоваться следующей формулой:

А вот и сама таблица (ссылка #3):

Код 256 — признак конца блока, символы 286 и 287 лишние.

Таблицы длин и обратных смещений

Тут тоже нет ничего сложного. Если код, который мы высчитали по предыдущей таблице попадает в промежуток от 257 до 285 (то есть, 3 и 4 случаи, исключая код 256, 286 и 287), то наше итоговое значение будет высчитываться по длине и обратному смещению. Но что же это? А это и есть результат работы Deflate. Название таблицы говорит само за себя. Когда мы натыкаемся на подобную команду, нужно отступить назад на количество битов, равное обратному смещению и взять количество битов, равное длине.

Таблица длин (ссылка #4):

Код 285 обозначает длину 258

Внимательность: пара замечаний по таблице. Я так понимаю, она была сгруппирована по доп. битам и сделано это лишь с целью экономии места. Поэтому немного объясню. Первая колонка содержит диапазоны кодов, а вторая — соответствующие им диапазоны длин. То есть, например, коду 265 соответствуют длины 11-12, 266 — 12-13, 267 — 13-14, ну и так далее со всеми остальными. Дополнительные биты нужны для того, чтобы в этом диапазоне длин выбрать нужное значение. Если, например, у нас длины равны 12-13 и есть 1 дополнительный бит, то 0 будет указывать на 12, а 1 — на 13. Думаю, логика примерно ясна.

Таблица обратных смещений:

Логика здесь точно такая же. После того, как мы нашли значение длины, считываем еще 5 битов (от младшего к старшему, естественно), переводим в десятичное представление для удобства. Этот код находим в таблице, используем дополнительные биты при необходимости и находим обратное смещение. Поехали дальше, начнём разбирать наш код.

Приступаем

Для удобства переведём всю последовательность в двоичный код (можно написать программу для этого, можно сделать вручную, а можно воспользоваться калькулятором, которых в Интернете полно; лично я предпочитаю первый вариант). Итак, у нас получается код (не забывайте про нули, их здесь может и не быть, но каждый байт обязательно является двоичным восьмибитным числом):

Выглядит эффектно, правда? На самом деле, тут всё просто. Начинаем:

1. Считываем первые 3 бита, заголовок первого блока.
| 0 | 10 | 00110
BFINAL — 0 — блок не последний.
BTYPE — 10 — используются фиксированные коды Хаффмана.

2. На этом этапе нужно брать минимум 7 битов, определять префикс. Далее уже переводить в число, либо считать смещения и длины. Что же мы стоим? Вперёд!

2.1 Берём первые 7 битов: |00110 00| 011010
0011000 — префикс попадает в первую категорию, а значит число должно иметь длину 8 бит. Берем еще один — 00110000.
По формуле находим значение:

Первое число равно 0. FILTER:NONE. Идём дальше. Берем еще 7 битов: |11010 10|00|1101 — 2-й промежуток, 9 бит. Находим значение:

Таким же образом проделываем всю остальную работу. Мы помним, что для кодирования 1 пикселя в нашем случае используется 6 байтов. Считаем их всех, а потом ненадолго остановимся:

Самые смышлёные тут опять же вспомнят, что в данном изображении используется цветовая модель RGB с глубиной цвета 16 бит. Каждый их трёх каналов закодирован двумя байтами. Чтобы получить 16-битное значение мы должны просто конкатенировать два байта. Далее, если мы захотим преобразовать их в 8-битный аналог, то я предлагаю решить следующую пропорцию. Можно, конечно же, просто отбросить второй байт, но тогда есть небольшая вероятность того, что полученное значение будет искажено. Поехали:

Символами \(\lceil\) \(\rceil\) обозначают потолок, то есть округление до целого в большую сторону.

Получилось, что R в нашем случае равен 168. Если мы проделаем то же самое с G и B-каналами, то получим, что цвет нашего первого пикселя в RGB-представлении равен (168, 32, 112). Теперь посмотрим на скриншот:

» data-medium-file=»https://i1.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/305de3f6fe-min.jpg?fit=300%2C204&ssl=1″ data-large-file=»https://i1.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/305de3f6fe-min.jpg?fit=556%2C378&ssl=1″ src=»https://i1.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/305de3f6fe-min.jpg?resize=556%2C378&ssl=1″ alt=»Скрин» width=»556″ height=»378″ srcset=»https://i1.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/305de3f6fe-min.jpg?w=556&ssl=1 556w, https://i1.wp.com/blog.underpowered.net/wp-content/uploads/2017/10/305de3f6fe-min.jpg?resize=300%2C204&ssl=1 300w» sizes=»(max-width: 556px) 100vw, 556px» data-recalc-dims=»1″ />

Мы движемся в верном направлении. А это значит, что нет смысла останавливаться! Второй пиксель декодируем так:

Путём несложных вычислений получаем наш код: RGB(255, 255, 255) — белый цвет. Всё верно. На этом строка заканчивается, так как её ширина составляет всего 2 пикселя. Приступаем ко второй (и последней) строке:

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

Заглянем в таблицу длин и получим значения:
1. Длина — 6
2. Доп. биты — 0

Теперь считываем следующие 5 битов, которые являются обратным смещением: \(00101=5\)
По таблице:
1. Доп.биты — 1
2. Расстояние 7,8
Следующий бит скажет скорректирует смещение. Он равен 0, значит фактическое смещение равняется 7.

А вот тут самое интересное. Наш «курсор» находится сразу же после байта со значением FILTER (который равен 0). Вернёмся на 7 байтов назад (обратное смещение) и скопируем 6 байтов (это как раз байты последнего пикселя первой строки):

Вот и всё. Ничего тут страшного нет. Цвет первого пикселя второй строки — RGB(255, 255, 255), что правда. Ух, надо идти вперёд! Я буду краток:

3-й промежуток. Код — 260:
1. Длина — 6
2. Доп. биты — 0

1. Доп. биты — 3
2. Длина — 17-24

Цвет — RGB(168, 32, 112). В принципе, может показаться, что это всё. Но на самом деле, нет. Считываем дальше:

256 — признак конца блока. Мы закончили.

Итак, что у нас получилось? Две строки по два пикселя. Первый имеет цвет RGB(168, 32, 112), второй RGB(255, 255, 255), третий и четвёртый — RGB(255, 255, 255) и RGB(168, 32, 112) соответственно. Если вы вспомните изображение, то поймете, что это недалеко от правды. Значит, мы всё делаем правильно, что внушает надежду на светлое будущее.

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

Судя по всему, начало нового блока? Ладно. Сжатия нет, блок последний.

Здесь самый простой вариант — без сжатия. В этом случае после заголовка идёт выравнивание на границу байта (то есть мы должны взять оставшееся количество битов в этом байте). Потом два байта — LEN и еще 2 — NLEN.
LEN — длина несжатых данных, NLEN — дополнение LEN до единицы.

Как мы видим, всё действительно так. Единственное, что LEN = 0, т.е. данных нет. Зачем это сделано — непонятно.

Ну и наконец, в самом конце чанка IDAT следует четырёхбайтовая хеш-сумма несжатых данных, высчитанная по алгоритму Adler-32. В нашем случае, хеш-сумма в двоичном представлении выглядит так:

Adler-32

Подробную информацию о том, как работает Adler-32 можно найти по ссылке #5. А мы пока возьмем последовательность расшифрованных байтов и захешируем её.

Последовательность (в десятичном представлении):

$start_1 = 1;
$start_2 = 0;

Найдите 10 отличий. Хеш-суммы совпадают, а поэтому с полной уверенностью заявляю, что мы сделали всё верно! Со следующего байта уже начинается чанк IEND, с IDAT же мы наконец-то закончили.

Стоит признать, что это было довольно просто. В пункте про алгоритм Deflate мы также рассмотрим декодирование строки (да, для примера возьмем обычную строку) с динамическими кодами Хаффмана.

Обязательный чанк, который должен следовать после всех остальных. Символизирует окончание PNG-документа и не содержит какой-либо информации.

Deflate

Чтобы сильно не утомлять моего читателя, который к этому моменту мог уже слегка подустать, расскажу лишь то, что встречалось выше. Данные в PNG хранятся в формате zlib и представляют собой последовательность блоков, сжатых при помощи Deflate. Deflate — это алгоритм сжатия, комбинирующий LZ77 и метод Хаффмана. Если очень коротко, то несжатая последовательность обрабатывается при помощи LZ77, после чего получившиеся коды упаковываются при помощи алгоритма Хаффмана.

Сам алгоритм довольно сложный, поэтому объясню его принцип, что называется, «на пальцах». LZ77 — это алгоритм сжатия без потерь, основанный на принципе «скользящего окна» (помните я писал про размер окна?), призванный заменять последовательности, встречающиеся чаще одного раза, на ссылки, указывающие на самые ранних из них. Что я имею в виду? Программа поочерёдно считывает последовательность битов, держа «в голове» (то есть в буфере) информацию об уже прочитанных битах. Когда программа натыкается на последовательность, которая уже содержится в буфере, то она полностью заменяется ссылкой, которая представляет собой сведения о смещении и длине последовательности. Смещение может быть как прямым (то есть начинаться от начала окна, либо от произвольной точки), так и обратным (отсчитываться смещение будет в обратном порядке относительно обрабатываемого бита). На самом деле, я не особо уверен в существовании прямого смещения, так как на практике не встречал, но в разных документах я видел упоминания о нём. Проще говоря, программа-интерпретатор получает указания отступить на n шагов назад и взять m байтов. Размер окна — это и есть размер нашего буфера, то есть расстояние от первого бита, который программа еще помнит, до первого бита, который программа уже помнит. Во время кодирования, программа без проблем может заменять комбинации, которые пока еще лежат за пределами окна.

Алгоритм Хаффмана

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

Ладно, уговорили. Допустим, у нас есть строка: «Hello, World!». Поехали:

1. Сначала выстраиваем список «Символ — частота»:

2. Сортируем его по частоте и создаем очередь. Приоритетом является частота. При этом, элементы с самым низким приоритетом выстраиваются в самом начале:

3. Теперь создаем бинарное дерево. Алгоритм такой: Берем первые два элемента и формируем из них мини-дерево, где листьями будут наши элементы. В таблицу записываем сумму приоритетов, помещая его в нужное место:

Таким же образом делаем со всеми остальными. В итоге получается такое дерево:

Общий приоритет — 11. Теперь присвоим коды. Каждая левая ветка — 0, правая — 1. В итоге получается что-то вроде этого:

Теперь нужно заменить нашу последовательность полученными кодами и выстроить таблицу, чтобы интерпретатор мог без проблем её декодировать. В принципе, это всё.

Ближе к теме

Я уже выше писал, но напомню еще раз. Данные состоят из блоков, следующих друг за другом последовательно. Каждый из них содержит заголовок, состоящий из 3 битов (RFC 1950):
1 бит – BFINAL. Устанавливается в 1, если данный блок последний.
2 бита – BTYPE. Содержит информацию о типе сжатия:

«Без сжатия» означает, что данные представлены в нетронутом виде. Мы рассмотрели работу с подобными данными в подпункте IDAT пункта «структура PNG».
«Сжатие с фиксированными кодами Хаффмана» — данные сжаты с помощью уже заранее предопределенных кодов. Этот способ мы тоже рассмотрели.
«Cжатие с динамическими кодами Хаффмана» — в данном случае, сжатая последовательность состоит из кодов, создаваемых «на лету». Коды и их значения хранятся непосредственно в блоке. Давайте рассмотрим немного подробнее.

Для урока я взял простую последовательность, которая не включает в себя длины и смещения. Тем не менее, работать с подобными данными мы уже умеем, так как это было рассмотрено выше, а метод сжатия значения не имеет, ибо всё происходит точно так же. Также уточню, что строка ниже не содержит заголовка zlib и контрольной суммы. Мы рассматриваем только Deflate.

Пример Deflate с динамическими кодами Хаффмана

Предположим, у нас есть следующая последовательность:

В двоичном представлении:

Считываем по байтам, биты от младшего к старшему. Первые 3 байта — заголовок:
101 — последний блок, динамический Хаффман. Да, информация о типе сжатия берется справа-налево, если мы идём от младшего к старшему. Дальше идут следующие значения:

HLIT — 5 бит, которое равно: количество_длин_и_символов минус 257. В нашем случае, 0, значит количество длин и символов — 257.
HDIST — 5 бит, которое равно: количество_смещений минус 1. В нашем случае 0, значит количество смещений — 1.
HCLEN — 4 бита, которое равно: количество_длин_и_команд минус 4. В нашем случае 11. Значит количество команд и длин — 15.

Давайте ненадолго остановимся и рассмотрим всё это. Блок с динамическими кодами состоит из следующих частей (исключая заголовок и описание длин):

1. Сначала следуют трёхбитовые длины команд и кодов, которых FCLEN + 4. Длины нам помогут декодировать наши значения.
Дело в том, что у каждого кода и команды есть длина (0110 — 4, 111 — 3). Знание длин команд и кодов даёт нам возможность узнать сами коды, нигде их не записывая. Как это работает? Допустим, у нас есть 5 кодов, которые имеют длины соответственно 2, 3, 4, 4, 4. Если при кодировании использовались канонические коды, то мы без проблем их восстановим. Начинаем с наименьшей длины, присваиваем ей код 00. а дальше увеличиваем их в пределах своей длины, дописывая 0, если длина меняется:

Еще раз, если не очень понятно. Если у нас одна длина, то увеличиваем значение на 1. Если длина меняется — увеличиваем на единицу и дописываем 0. Таким образом мы избавляемся от префиксов, то есть мы уверены, что ни один из кодов не является подстрокой для другого. А это позволяет интерпретатору однозначно декодировать значения. Удобно, правда?

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

Коды и команды следуют в следующем порядке: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15.
Здесь:
0-15 — длины непосредственно кодов.
16 — длина команды, которая говорит интерпретатору повторить предыдущее значение n раз. Следующие 2 бита как раз являются этим n.
17 — повторить значение 0 n раз. 3 бита являются значением n.
18 — повторить значение 0 n раз. 8 битов являются значением n.

2. Далее идёт последовательность из HLIT + 257 команд и значений закодированных символов, которые можно найти, исходя из их позиции в потоке данных (на примере я объясню этот момент). В предыдущем блоке мы получили их длины. Теперь же мы сможем сопоставить распакованное значение и длину кода, которым оно закодировано. Используя приведённый выше алгоритм, зная длины кодов и их значения, мы без проблем найдем сами коды.

3. Последним идёт блок со сжатыми данными. На этом этапе мы уже знаем коды и их значения (или длины и смещения). Поэтому без проблем можем декодировать строку.

Если у вас каша в голове, то не переживайте, сейчас на примере мы всё разберём. Поехали!

Итак, берём HCLEN + 4 (15) трёхбитовых значений:

Отбросим все значение, где длина равна 0 и переведём в десятичную систему:

Теперь восстанавливаем коды длин:

Затем у нас следуют 257 длин и команд. Здесь мы и применяем наши длины символов и команд. Давайте я покажу как найти значение.

Допустим, возьмём первый код. Благодаря тому, что у нас отсутствуют префиксы, мы можем правильно определить коды. Первый код в нашем потоке — это 111. Смотрим выше и понимаем, что 111 соответствует 18. Смотрим еще выше и вспоминаем, что 18 это команда. Нам требуется еще 7 битов, возьмем же их — 0100000 (32). Это значит, что нам нужно повторить значение 0 32 раза. Самый первый символ имеет позицию 0. Если мы «передвинемся» по нашей последовательности на 32 бита вправо (включая 0), то окажемся на 31 бите. Это всё.
Дальше берём следующую порцию битов — 101. 101 соответствует длине 4. Запоминаем этот код и делаем еще один шаг — 32. Это значит, что первые код с длиной, равной 4, имеет значение 32. Возможно, это не совсем корректное объяснение, но так проще всего понять. Всё остальное делаем точно так же:

Восстанавливаем коды и значения. Всё последовательно.

Источник