[Перевод] Zip-файлы: история, объяснение и реализация

botwdrbtegpbnpnwmy7id56fbaa.jpeg

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

В статье очень подробно объясняется, как работают Zip-файлы и схема сжатия: LZ77-сжатие, алгоритм Хаффмана, алгоритм Deflate и прочее. Вы узнаете историю развития технологии и посмотрите довольно эффективные примеры реализации, написанные с нуля на С. Исходный код лежит тут: hwzip-1.0.zip.
Я очень благодарен Ange Albertini, Gynvael Coldwind, Fabian Giesen, Jonas Skeppstedt (web), Primiano Tucci и Nico Weber, которые дали ценные отзывы на черновики этой статьи.

Содержание


История


PKZip


В восьмидесятых и начале девяностых, до широкого распространения интернета, энтузиасты-компьютерщики использовали dial-up-модемы для подключения через телефонную сеть к сети Bulletin Board Systems (BBS). BBS представляла собой интерактивную компьютерную систему, которая позволяла пользователям отправлять сообщения, играть в игры и делиться файлам. Для выхода в онлайн достаточно было компьютера, модема и телефонного номера хорошей BBS. Номера публиковались в компьютерных журналах и на других BBS.

Важным инструментом, облегчающим распространение файлов, был архиватор. Он позволяет сохранять один или несколько файлов в едином файле-архиве, чтобы удобнее хранить или передавать информацию. А в иделе архив ещё и сжимал файлы для экономии места и времени на передачу по сети. Во времена BBS был популярен архиватор Arc, написанный Томом Хендерсоном из System Enhancement Associates (SEA), маленькой компании, которую он основал со своим шурином.

В конце 1980-х программист Фил Катц выпустил собственную версию Arc — PKArc. Она была совместима с SWA Arc, но работала быстрее благодаря подпрограммам, написанным на ассемблере, и использовала новый метод сжатия. Программа стала популярной, Катц ушёл с работы и создал компанию PKWare, чтобы сосредоточиться на дальнейшей разработке. Согласно легенде, большая часть работы проходила на кухне его матери в Глендейле, штат Висконсин.

b1e50a990a86a05045dde9d2a819fbf0.jpg


Фотография Фила Катца из статьи в Milwaukee Sentinel, 19 сентября 1994.

Однако SEA не устраивала инициатива Катца. Компания обвинила его в нарушении торгового знака и авторских прав. Разбирательства и споры в сети BBS и мире ПК стали известны как Arc-войны. В конце концов, спор был урегулирован в пользу SEA.

Отказавшись от Arc, Катц в 1989 создал новый формат архивирования, который он назвал Zip и передал в общественное пользование:

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

Программа Катца для создания таких файлов получила название PKZip и скоро распространилась в мире BBS и ПК.

Одним из аспектов, который с наибольшей вероятность поспособствовал успеху Zip-формата, является то, что с PKZip шла документация, Application Note, в которой подробно объяснялось, как работает формат. Это позволило другим изучить формат и создать программы, которые генерируют, извлекают или как-то иначе взаимодействуют с Zip-файлами.

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

PKZip распространялась как Shareware: её можно было свободно использовать и копировать, но автор предлагал пользователям «зарегистрировать» программу. За $47 можно было получить распечатанную инструкцию, премиальную поддержку и расширенную версию приложения.

0315094fc6917b61db8f78b2f776ce13.jpg


Одной из ключевых версий PKZip стала 2.04c, вышедшая 28 декабря 1992 (вскоре после неё вышла версия 2.04g). В ней по умолчанию использовался алгоритм сжатия Deflate. Версия определила дальнейший путь развития сжатия в Zip-файлах (статья, посвящённая релизу).

58ebd369bf36c272d0c8c7c9515fc670.png


С тех пор Zip-формат используется во многих других форматах файлов. Например, Java-архивы (.jar), Android Application Packages (.apk) и .docx-файлы Microsoft Office используют Zip-формат. Во многих форматах и протоколах применяется тот же алгоритм сжатия, Deflate. Скажем, веб-страницы наверняка передаются в ваш браузер в виде gzip-файла, формат которого использует Deflate-сжатие.

Фил Катц умер в 2000-м. PKWare всё ещё существует и поддерживает Zip-формат, хотя компания сосредоточена в основном на ПО для защиты данных.

Info-ZIP и zlib


Вскоре после выхода PKZip в 1989-м начали появляться другие программ для распаковки Zip-файлов. Например, программа unzip, которая могла распаковывать на Unix-системах. В марте 1990-го был создан список рассылки под названием Info-ZIP.

Группа Info-ZIP выпустила бесплатные программы с открытым исходным кодом unzip и zip, которые использовались для распаковки и создания Zip-файлов. Код портировали во многие системы, и он до сих пор является стандартом для Zip-программ под Unix-системы. Позднее это помогло росту популярности Zip-файлов.

Однажды код Info-ZIP, который выполнял Deflate-сжатие и распаковку, был вынесен в отдельную библиотеку zlib, которую написали Jean-loup Gailly (сжатие) и Mark Adler (распаковка).

68b216d1debaffdb2d890067e38bed47.jpg


Jean-loup Gailly (слева) и Mark Adler (справа) на вручении им премии USENIX STUG Award в 2009-м.

Одна из причин создания библиотеки заключалась в том, что это обеспечивало удобство использования Deflate-сжатия в других приложениях и форматах, например, в новых gzip и PNG. Эти новые форматы были призваны заменить Compress и GIF, в которых применялся защищённый патентом алгоритм LZW.

В рамках создания этих форматов Питер Дойч написал спецификацию Deflate и опубликовал под названием Internet RFC 1951 в мае 1996-го. Это оказалось более доступное описание по сравнению с исходным PKZip Application Note.

Сегодня zlib используется повсеместно. Возможно, он сейчас отвечает за сжатие этой страницы на веб-сервере и её распаковки в вашем браузере. Сегодня сжатие и распаковка большинства Zip-файлов выполняется с помощью zlib.

WinZip


Многие из тех, кто не застал PKZip, пользовались WinZip. Пользователи ПК перешли как с DOS на Windows, так и с PKZip на WinZip.

Всё началось с проекта программиста Нико Мака, который создавал ПО для OS/2 в компании Mansfield Software Group в городе Сторрс-Мансфилд, штат Коннектикут. Нико использовал Presentation Manager, это графический пользовательский интерфейс в OS/2, и его расстраивало, что приходится переходить от файлового менеджера к DOS-командам каждый раз, когда он хотел создать Zip-файлы.

Мак написал простую программу с графическим интерфейсом, которая работала с Zip-файлами прямо в Presentation Manager, назвал её PMZip и выпустил в качестве shareware в 1990-м.

OS/2 так и не добилась успеха, а мир ПК захватывала Microsoft Windows. В 1991-м Мак решил научиться писать Windows-программы, и его первым проектом стало портирование своего Zip-приложения под новую ОС. В апреле 1991-го вышла WinZip 1.00. Она распространялась в качестве shareware с 21-дневным пробным периодом и стоимостью регистрации $29. Выглядела она так:

0b12f4bcd048691aa0487b9d3a445b39.png


В первых версиях WinZip под капотом использовалась PKZip. Но с версии 5.0 в 1993-м для прямой обработки Zip-файлов стал использоваться код из Info-ZIP. Пользовательский интерфейс тоже постепенно эволюционировал.

bf427396212f63fba9c80db12fdd2132.png


WinZip 6.3 под Windows 3.11 for Workgroups.

WinZip была одной из самых популярных shareware-программ в 1990-е. Но в конце концов она потеряла актуальность из-за встраивания поддержки Zip-файлов в операционные системы. Windows работает с ними как со «сжатыми папками» начиная с 2001-го (Windows XP), для этого используется библиотека DynaZip.

Изначально компания Мака называлась Nico Mak Computing. В 2000-м её переименовали в WinZip Computing, и примерно в те годы Мак её покинул. В 2005-м компанию продали Vector Capital, и в конце концов ею стала владеть Corel, которая до сих пор выпускает WinZip в качестве продукта.

Сжатие Lempel-Ziv (LZ77)


Zip-сжатие состоит из двух основных ингредиентов: сжатия Lempel-Ziv и кода Хаффмана.

Один из способов сжатия текста заключается в создании списка частых слов или фраз с заменой разновидностей этих слов в рамках текста ссылками на словарь. Например, длинное слово «compression» в исходном тексте можно представить как #1234, где 1234 ссылается на позицию слова в списке. Это называется сжатием с использованием словаря.

Но с точки зрения сжатия универсального назначения у такого метода есть несколько недостатков. Во-первых, что именно должно попасть в словарь? Исходные данные могут быть на разных языках, это может быть даже не человеко читаемый текст. И если заранее не согласовать словарь между сжатием и распаковкой, то его придётся хранить и передавать вместе со сжатыми данными, что снижает выгоду от сжатия.

Элегантным решением этой проблемы является использование в качестве словаря самих исходных данных. В работе «A Universal Algorithm for Sequential Data Compression» 1977 года Якоб Зив и Абрахам Лемпел (работавшие в компании Technion), предложили схему сжатия, при которой исходные данные представляются в виде последовательности триплетов:

(указатель, длина, следующий)


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

5e521efdb5649015f685e26ab308d1b9.jpg
2cecfa2e39798ce3302ff4b48e1a62ef.jpg


Абрахам Лемпел и Якоб Зив.

Рассмотрим такие строки:

It was the best of times,
it was the worst of times,


Во второй строке последовательность «t was the w» можно представить как (26, 10, w), поскольку она воссоздаётся копированием 10 символов с позиции в 26 символов назад и до буквы «w». Для символов, которые до этого ещё не появлялись, используются обратные ссылки нулевой длины. Например, начальная «I» может быть представлена как (0, 0, I).

Эта схема получила название сжатие Lempel-Ziv, или сжатие LZ77. Однако в практических реализациях алгоритма обычно не используется часть триплета следующий. Вместо этого символы генерируются по-одиночке, а для обратных ссылок используются пары (расстояние, длина) (этот вариант называется сжатием LZSS). Как кодируются литералы и обратные ссылки — это отдельный вопрос, мы рассмотрим его ниже, когда будем разбирать алгоритм Deflate.

Этот текст:

It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,
we had everything before us,
we had nothing before us,
we were all going direct to Heaven,
we were all going direct the other way


Можно сжать в такой:

It was the best of times,
i(26,10)wor(27,24)age(25,4)wisdom(26,20)
foolishnes(57,14)epoch(33,4)belief(28,22)incredulity
(33,13)season(34,4)Light(28,23)Dark(120,17)
spring(31,4)hope(231,14)inter(27,4)despair,
we had everyth(57,4)before us(29,9)no(26,20)
we(12,3)all go(29,4)direct to Heaven
(36,28)(139,3)(83,3)(138,3)way


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

Fa-la-la-la-la


Можно сжать в:

Fa-la(3,9)


Вам это может показаться странным, но метод работает: после того, как скопированы байты первых трёх »-la», копирование продолжается уже с использованием недавно сгенерированных байтов.

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

Интерактивный пример использования сжатия Lempel-Ziv для текстов песен показан в статье Колина Морриса Are Pop Lyrics Getting More Repetitive?.

Ниже приведён пример копирования обратных ссылок на языке С. Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove.

/* Output the (dist,len) backref at dst_pos in dst. */
static inline void lz77_output_backref(uint8_t *dst, size_t dst_pos,
                                       size_t dist, size_t len)
{
        size_t i;

        assert(dist <= dst_pos && "cannot reference before beginning of dst");

        for (i = 0; i < len; i++) {
                dst[dst_pos] = dst[dst_pos - dist];
                dst_pos++;
        }
}


Генерировать литералы легко, но для полноты воспользуемся вспомогательной функцией:

/* Output lit at dst_pos in dst. */
static inline void lz77_output_lit(uint8_t *dst, size_t dst_pos, uint8_t lit)
{
        dst[dst_pos] = lit;
}


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

Сложно не генерировать данные с помощью обратных ссылок в ходе распаковки, а создавать их первым делом при сжатии исходных данных. Это можно сделать по-разному, но мы воспользуемся методикой на основе хэш-таблиц из zlib, который предлагается в RFC 1951.

Будем применять хэш-таблицу с позициями трёхсимвольных префиксов, которые ранее встречались в строке (более короткие обратные ссылки пользы не приносят). В Deflate допускаются обратные ссылки в рамках предыдущих 32 768 символов — это называется окном. Это обеспечивает потоковое сжатие: входные данные подвергаются небольшой обработке за раз, при условии, что окно с последними байтами хранится в памяти. Однако наша реализация предполагает, что нам доступны все входные данные и мы можем обработать их целиком за раз. Это позволяет сосредоточиться на сжатии, а не на учёте, который необходим для потоковой обработки.

Воспользуемся двумя массивами: в head содержится хэш-значение трёхсимвольного префикса для позиции во входных данных, а в prev содержится позиция предыдущей позиции с этим хэш-значением. По сути, head[h] — это заголовок связного списка позиций префиксов с хэшем h, а prev[x] получает элемент, предшествующий x в списке.

#define LZ_WND_SIZE 32768
#define LZ_MAX_LEN  258

#define HASH_SIZE 15
#define NO_POS    SIZE_MAX

/* Perform LZ77 compression on the len bytes in src. Returns false as soon as
   either of the callback functions returns false, otherwise returns true when
   all bytes have been processed. */
bool lz77_compress(const uint8_t *src, size_t len,
                   bool (*lit_callback)(uint8_t lit, void *aux),
                   bool (*backref_callback)(size_t dist, size_t len, void *aux),
                   void *aux)
{
        size_t head[1U << HASH_SIZE];
        size_t prev[LZ_WND_SIZE];

        uint16_t h;
        size_t i, j, dist;
        size_t match_len, match_pos;
        size_t prev_match_len, prev_match_pos;

        /* Initialize the hash table. */
        for (i = 0; i < sizeof(head) / sizeof(head[0]); i++) {
                head[i] = NO_POS;
        }


Для вставки в хэш-таблицу новой строковой позиции prev обновляется, чтобы указывать на предыдущую head, а затем обновляется сама head:

static void insert_hash(uint16_t hash, size_t pos, size_t *head, size_t *prev)
{
        prev[pos % LZ_WND_SIZE] = head[hash];
        head[hash] = pos;
}


Обратите внимание на операцию по модулю при индексировании в prev: нас интересуют только те позиции, которые попадают в текущее окно.

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

static uint16_t update_hash(uint16_t hash, uint8_t c)
{
        hash <<= 5;                     /* Shift out old bits. */
        hash ^= c;                      /* Include new bits. */
        hash &= (1U << HASH_SIZE) - 1;  /* Mask off excess bits. */

        return hash;
}


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

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

/* Find the longest most recent string which matches the string starting
 * at src[pos]. The match must be strictly longer than prev_match_len and
 * shorter or equal to max_match_len. Returns the length of the match if found
 * and stores the match position in *match_pos, otherwise returns zero. */
static size_t find_match(const uint8_t *src, size_t pos, uint16_t hash,
                         size_t prev_match_len, size_t max_match_len,
                         const size_t *head, const size_t *prev,
                         size_t *match_pos)
{
        size_t max_match_steps = 4096;
        size_t i, l;
        bool found;

        if (prev_match_len == 0) {
                /* We want backrefs of length 3 or longer. */
                prev_match_len = 2;
        }

        if (prev_match_len >= max_match_len) {
                /* A longer match would be too long. */
                return 0;
        }

        if (prev_match_len >= 32) {
                /* Do not try too hard if there is already a good match. */
                max_match_steps /= 4;
        }

        found = false;
        i = head[hash];

        while (max_match_steps != 0) {
                if (i == NO_POS) {
                        /* No match. */
                        break;
                }

                assert(i < pos && "Matches should precede pos.");
                if (pos - i > LZ_WND_SIZE) {
                        /* The match is outside the window. */
                        break;
                }

                l = cmp(src, i, pos, prev_match_len, max_match_len);

                if (l != 0) {
                        assert(l > prev_match_len);
                        assert(l <= max_match_len);

                        found = true;
                        *match_pos = i;
                        prev_match_len = l;

                        if (l == max_match_len) {
                                /* A longer match is not possible. */
                                return l;
                        }
                }

                /* Look further back in the prefix list. */
                i = prev[i % LZ_WND_SIZE];
                max_match_steps--;
        }

        if (!found) {
                return 0;
        }

        return prev_match_len;
}

/* Compare the substrings starting at src[i] and src[j], and return the length
 * of the common prefix. The match must be strictly longer than prev_match_len
 * and shorter or equal to max_match_len. */
static size_t cmp(const uint8_t *src, size_t i, size_t j,
                  size_t prev_match_len, size_t max_match_len)
{
        size_t l;

        assert(prev_match_len < max_match_len);

        /* Check whether the first prev_match_len + 1 characters match. Do this
         * backwards for a higher chance of finding a mismatch quickly. */
        for (l = 0; l < prev_match_len + 1; l++) {
                if (src[i + prev_match_len - l] !=
                    src[j + prev_match_len - l]) {
                        return 0;
                }
        }

        assert(l == prev_match_len + 1);

        /* Now check how long the full match is. */
        for (; l < max_match_len; l++) {
                if (src[i + l] != src[j + l]) {
                        break;
                }
        }

        assert(l > prev_match_len);
        assert(l <= max_match_len);
        assert(memcmp(&src[i], &src[j], l) == 0);

        return l;
}


Можно завершить функцию lz77_compress этим кодом для поиска предыдущих совпадений:

       /* h is the hash of the three-byte prefix starting at position i. */
        h = 0;
        if (len >= 2) {
                h = update_hash(h, src[0]);
                h = update_hash(h, src[1]);
        }

        prev_match_len = 0;
        prev_match_pos = 0;

        for (i = 0; i + 2 < len; i++) {
                h = update_hash(h, src[i + 2]);

                /* Search for a match using the hash table. */
                match_len = find_match(src, i, h, prev_match_len,
                                       min(LZ_MAX_LEN, len - i), head, prev,
                                       &match_pos);

                /* Insert the current hash for future searches. */
                insert_hash(h, i, head, prev);

                /* If the previous match is at least as good as the current. */
                if (prev_match_len != 0 && prev_match_len >= match_len) {
                        /* Output the previous match. */
                        dist = (i - 1) - prev_match_pos;
                        if (!backref_callback(dist, prev_match_len, aux)) {
                                return false;
                        }
                        /* Move past the match. */
                        for (j = i + 1; j < min((i - 1) + prev_match_len,
                                                len - 2); j++) {
                                h = update_hash(h, src[j + 2]);
                                insert_hash(h, j, head, prev);
                        }
                        i = (i - 1) + prev_match_len - 1;
                        prev_match_len = 0;
                        continue;
                }

                /* If no match (and no previous match), output literal. */
                if (match_len == 0) {
                        assert(prev_match_len == 0);
                        if (!lit_callback(src[i], aux)) {
                                return false;
                        }
                        continue;
                }

                /* Otherwise the current match is better than the previous. */

                if (prev_match_len != 0) {
                        /* Output a literal instead of the previous match. */
                        if (!lit_callback(src[i - 1], aux)) {
                                return false;
                        }
                }

                /* Defer this match and see if the next is even better. */
                prev_match_len = match_len;
                prev_match_pos = match_pos;
        }

        /* Output any previous match. */
        if (prev_match_len != 0) {
                dist = (i - 1) - prev_match_pos;
                if (!backref_callback(dist, prev_match_len, aux)) {
                        return false;
                }
                i = (i - 1) + prev_match_len;
        }

        /* Output any remaining literals. */
        for (; i < len; i++) {
                if (!lit_callback(src[i], aux)) {
                        return false;
                }
        }

        return true;
}


Этот код ищет самую длинную обратную ссылку, которая может быть сгенерирована на текущей позиции. Но прежде чем её выдать, программа решает, можно ли на следующей позиции найти ещё более длинное совпадение. В zlib это называется оценкой с помощью ленивого сравнения. Это всё ещё жадный алгоритм: он выбирает самое длинное совпадение, даже если текущее более короткое позволяет позднее получить совпадение ещё длиннее и достичь более сильного сжатия.

Сжатие Lempel-Ziv может работать как быстро, так и медленно. Zopfli потратил много времени на поиски оптимальных обратных ссылок, чтобы выжать дополнительные проценты сжатия. Это полезно для данных, которые сжимаются один и раз и потом многократно используются, например, для статичной информации на веб-сервере. На другой стороне шкалы находятся такие компрессоры, как Snappy и LZ4, которые сравнивают только с последним 4-байтным префиксом и работают очень быстро. Такой тип сжатия полезен в базах данных и RPC-системах, в которых время, потраченное на сжатие, окупается экономией времени при отправке данных по сети или на диск.

Идея использовать исходные данные в качестве словаря очень элегантна, но и от статичного словаря можно получить пользу. Brotli — алгоритм на основе LZ77, но он также использует большой статичный словарь из строковых, которые часто встречаются в сети.

Код LZ77 можно посмотреть в lz77.h и lz77.c.

Код Хаффмана


Вторым алгоритмом Zip-сжатия является код Хаффмана.

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

Традиционно англоязычный текст представляют с помощью American Standard Code for Information Interchange (ASCII). Эта система присваивает каждому символу число, которые обычно хранятся в 8-битном представлении. Вот ASCII-коды для прописных букв английского алфавита:


Один байт на символ — это удобный способ хранения текста. Он позволяет легко обращаться к частям текста или изменять их, и всегда понятно, сколько байтов требуется для хранения N символов, или сколько символов хранится в N байтов. Однако это не самый эффективный способ с точки зрения занимаемого объёма. Например, в английском языке буква E используется чаще всего, а Z — реже всего. Поэтому с точки зрения объёма эффективнее использовать более короткое битовое представление для E и более длинное для Z, а не присваивать каждому символу одинаковое количество битов.

Код, который разным исходным символам задаёт кодировки разной длины, называется кодом переменной длины. Самый известный пример — азбука Морзе, в которой каждый символ кодируется точками и тире, изначально передававшимися по телеграфу короткими и длинными импульсами:


Одним из недостатков азбуки Морзе является то, что одно кодовое слово может быть префиксом другого. Например, • • − • не имеет уникального декодирования: это может быть F или ER. Это решается с помощью пауз (длиной в три точки) между буквами в ходе передачи. Однако было бы лучше, если бы кодовые слова не могли являться префиксами других слов. Такой код называется беспрефиксным. ASCII-код фиксированной длины является беспрефиксным, потому что кодовые слова всегда одной длины. Но коды переменной длины тоже могут быть беспрефиксными. Телефонные номера чаще всего беспрефиксные. Прежде чем в Швеции ввели телефон экстренной помощи 112, пришлось поменять все номера, начинавшиеся со 112. А в США нет ни одного телефонного номера, начинающегося с 911.

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

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


Изучая материалы для написания своей докторской диссертации по электронной инженерии в MIT, Дэвид Хаффман прослушал курс по теории информации, который читал Роберт Фано. Согласно легенде, Фано позволил своим слушателям выбирать: писать финальный экзамен или курсовую. Хаффман выбрал последнее, и ему дали тему поиска беcпрефиксных кодов с минимальной избыточностью. Предполагается, что он не знал о том, что над этой задачей в то время работал сам Фано (самым известный методом в те годы был алгоритм Шеннона-Фано). Работа Хаффмана была опубликована в 1952-м под названием A Method for the Construction of Minimum-Redundancy Codes in 1952. И с тех пор его алгоритм получил широкое распространение.

cf04fe00303a663594eea8e8db063002.jpg


Дэвид Хаффман пресс-релиз UC Santa Cruz.

Алгоритм Хаффмана создаёт беспрефиксный код с минимальной избыточностью для набора символов и их частоты использования. Алгоритм многократно выбирает два символа, которые реже всего встречаются в исходных данных, — допустим, Х и Y — и заменяет их на составной символ, означающий «X или Y». Частотой появления составного символа является сумма частот двух исходных символов. Кодовые слова для X и Y могут быть любыми кодовыми словами, которые присвоены составному символу «X или Y», за которым идёт 0 или 1, чтобы отличать друг от друга исходные символы. Когда входные данные уменьшаются до одного символа, алгоритм прекращает работу (видеообъяснение).

Вот пример работы алгоритма на маленьком наборе символов:


Первая итерация обработки:

e90a8f4e47c49cd14ca3a55f884d55e3.png


Два самых редких символа, C и D, убираются из набора и заменяются составным символом, частота которого является суммой частот C и D:

7e9b0baeda34fc4d368c933bed7e1d15.png


Теперь самыми редкими символами стали B и составной символ с частотой 5. Они убираются из набора и заменяются составным символом с частотой 9:

bca94bad698775402e8bab2c6a20f664.png


Наконец, A и составной символ с частотой 9 объединяются в новый символ с частотой 15:

260aa38005cf701421881214915d859a.png


Весь набор свёлся к одному символу, обработка завершена.

Алгоритм создал структуру, которая называется деревом Хаффмана. Входные символы — это листья, а чем больше частота у символа, тем выше он расположен. Начиная от корня дерева можно сгенерировать кодовые слова для символов, добавляя 0 или 1, когда переходим влево или вправо соответственно. Получится так:


Ни одно кодовое слово не является префиксом для какого-то другого. Чем чаще встречается символ, тем короче его кодовое слово.

Дерево можно использовать и для декодирования: начинаем с корня и идём направо или налево для значение с 0 или 1 перед символом. Например, строка 010100 декодируется в ABBA.

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

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

/* Swap the 32-bit values pointed to by a and b. */
static void swap32(uint32_t *a, uint32_t *b)
{
        uint32_t tmp;

        tmp = *a;
        *a = *b;
        *b = tmp;
}

/* Move element i in the n-element heap down to restore the minheap property. */
static void minheap_down(uint32_t *heap, size_t n, size_t i)
{
        size_t left, right, min;

        assert(i >= 1 && i <= n && "i must be inside the heap");

        /* While the ith element has at least one child. */
        while (i * 2 <= n) {
                left = i * 2;
                right = i * 2 + 1;

                /* Find the child with lowest value. */
                min = left;
                if (right <= n && heap[right] < heap[left]) {
                        min = right;
                }

                /* Move i down if it is larger. */
                if (heap[min] < heap[i]) {
                        swap32(&heap[min], &heap[i]);
                        i = min;
                } else {
                        break;
                }
        }
}

/* Establish minheap property for heap[1..n]. */
static void minheap_heapify(uint32_t *heap, size_t n)
{
        size_t i;

        /* Floyd's algorithm. */
        for (i = n / 2; i >= 1; i--) {
                minheap_down(heap, n, i);
        }
}


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

Для хранения n-элементной кучи и n элементов связи будем использовать массив из n * 2 + 1 элементов. Когда два символа в куче заменяются одним, мы будем использовать второй элемент для сохранения ссылки на новый символ. Этот подход основан на реализации Managing Gigabytes Уиттена, Моффата и Белла.

В каждом узле куче мы будем использовать 16 старших битов для хранения частоты символа, а 16 младших — для хранения индекса элемента связи символа. За счёт использования старших битов разница частот будет определяться результатом 32-битного сравнения между двумя элементами кучи.

Из-за такого представления нам нужно удостовериться, что частота символов всегда укладывается в 16 битов. После завершения работы алгоритма финальный составной символ будет иметь частоту всех объединённых символов, то есть эта сумма должна помещаться в 16 битов. Наша реализация Deflate будет проверять это с помощью одновременной обработки до 64 535 символов.

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

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

#define MAX_HUFFMAN_SYMBOLS 288      /* Deflate uses max 288 symbols. */

/* Construct a Huffman code for n symbols with the frequencies in freq, and
 * codeword length limited to max_len. The sum of the frequencies must be <=
 * UINT16_MAX. max_len must be large enough that a code is always possible,
 * i.e. 2 ** max_len >= n. Symbols with zero frequency are not part of the code
 * and get length zero. Outputs the codeword lengths in lengths[0..n-1]. */
static void compute_huffman_lengths(const uint16_t *freqs, size_t n,
                                    uint8_t max_len, uint8_t *lengths)
{
        uint32_t nodes[MAX_HUFFMAN_SYMBOLS * 2 + 1], p, q;
        uint16_t freq;
        size_t i, h, l;
        uint16_t freq_cap = UINT16_MAX;

#ifndef NDEBUG
        uint32_t freq_sum = 0;
        for (i = 0; i < n; i++) {
                freq_sum += freqs[i];
        }
        assert(freq_sum <= UINT16_MAX && "Frequency sum too large!");
#endif

        assert(n <= MAX_HUFFMAN_SYMBOLS);
        assert((1U << max_len) >= n && "max_len must be large enough");

try_again:
        /* Initialize the heap. h is the heap size. */
        h = 0;
        for (i = 0; i < n; i++) {
                freq = freqs[i];

                if (freq == 0) {
                        continue; /* Ignore zero-frequency symbols. */
                }
                if (freq > freq_cap) {
                        freq = freq_cap; /* Enforce the frequency cap. */
                }

                /* High 16 bits: Symbol frequency.
                   Low 16 bits:  Symbol link element index. */
                h++;
                nodes[h] = ((uint32_t)freq << 16) | (uint32_t)(n + h);
        }
        minheap_heapify(nodes, h);

        /* Special case for less than two non-zero symbols. */
        if (h < 2) {
                for (i = 0; i < n; i++) {
                        lengths[i] = (freqs[i] == 0) ? 0 : 1;
                }
                return;
        }

        /* Build the Huffman tree. */
        while (h > 1) {
                /* Remove the lowest frequency node p from the heap. */
                p = nodes[1];
                nodes[1] = nodes[h--];
                minheap_down(nodes, h, 1);

                /* Get q, the next lowest frequency node. */
                q = nodes[1];

                /* Replace q with a new symbol with the combined frequencies of
                   p and q, and with the no longer used h+1'th node as the
                   link element. */
                nodes[1] = ((p & 0xffff0000) + (q & 0xffff0000))
                           | (uint32_t)(h + 1);

                /* Set the links of p and q to point to the link element of
                   the new node. */
                nodes[p & 0xffff] = nodes[q & 0xffff] = (uint32_t)(h + 1);

                /* Move the new symbol down to restore heap property. */
                minheap_down(nodes, h, 1);
        }

        /* Compute the codeword length for each symbol. */
        h = 0;
        for (i = 0; i < n; i++) {
                if (freqs[i] == 0) {
                        lengths[i] = 0;
                        continue;
                }
                h++;

                /* Link element for the i'th symbol. */
                p = nodes[n + h];

                /* Follow the links until we hit the root (link index 2). */
                l = 1;
                while (p != 2) {
                        l++;
                        p = nodes[p];
                }

                if (l > max_len) {
                        /* Lower freq_cap to flatten the distribution. */
                        assert(freq_cap != 1 && "Cannot lower freq_cap!");
                        freq_cap /= 2;
                        goto try_again;
                }

                assert(l <= UINT8_MAX);
                lengths[i] = (uint8_t)l;
        }
}


Элегантной альтернативой варианту с двоичной кучей является сохранение символов в двух очередях. Первая содержит исходные символы, отсортированные по частоте. Когда создаётся составной символ, он добавляется во вторую очередь. Таким образом символ с наименьшей частотой всегда будет на первой позиции одной из очередей. Этот подход описан Jan van Leeuwen в On the Construction of Huffman Trees (1976).

Кодирование Хаффмана оптимально для беспрефиксных кодов, но в других случаях есть более эффективные способы: арифметическое кодирование и асимметричные системы счисления.

Канонические коды Хаффмана


В примере выше мы построили дерево Хаффмана:

260aa38005cf701421881214915d859a.png


Если идти от корня и использовать 0 для левой ветки и 1 для правой, то мы получим такие коды:
Решение об использовании 0 для левой ветки и 1 для правой выглядит произвольным. Если сделать наоборот, то получим:
Мы можем произвольно помечать две ветки, исходящие из ноды, нулём и единицей (главное, чтобы метки были разными), и всё равно получим эквивалентный код:

29bacb4999e9a3f530f22634846a97b7.png


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

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

© Habrahabr.ru