Кодирование Хаффмана: алгоритм сжатия данных

Введение

Техника сжатия данных

В информатике и теории информации код Хаффмана — это особый тип оптимального префиксного кода, который обычно используется для сжатия данных без потерь. Процесс поиска или использования такого кода называется кодированием Хаффмана — алгоритмом, разработанным Дэвидом А. Хаффманом во время обучения в аспирантуре (Sc. D.) в MIT и опубликованным в 1952 году в статье «Метод построения кодов с минимальной избыточностью». Результат работы алгоритма Хаффмана можно рассматривать как таблицу кодов переменной длины для кодирования исходного символа (например, символа в файле). Алгоритм выводит эту таблицу на основе оценочной вероятности или частоты появления (веса) каждого возможного значения исходного символа. Как и в других методах энтропийного кодирования, более часто встречающиеся символы обычно представляются меньшим количеством бит, чем менее часто встречающиеся. Метод Хаффмана может быть эффективно реализован, находя код за время, линейное от количества входных весов, при условии, что эти веса отсортированы. Однако, хотя он оптимален среди методов, кодирующих символы по отдельности, кодирование Хаффмана не всегда оптимально среди всех методов сжатия — его заменяют арифметическим кодированием или асимметричными численными системами, если требуется более высокая степень сжатия.

История

В 1951 году Дэвиду А. Хаффману и его однокурсникам по теории информации в Массачусетском технологическом институте (МТИ) предоставили выбор между курсовой работой и итоговым экзаменом. Профессор Роберт М. Фано предложил тему курсовой работы, посвященную задаче поиска наиболее эффективного двоичного кода. Хаффман, не сумев доказать, что какие-либо коды являются наиболее эффективными, почти сдался и начал готовиться к экзамену, но внезапно ему пришла в голову идея использовать двоичное дерево, упорядоченное по частоте, и он быстро доказал, что этот метод является самым эффективным. Таким образом, Хаффман превзошел Фано, который работал с Клодом Шенноном над разработкой аналогичного кода. Построение дерева снизу вверх гарантировало оптимальность, в отличие от подхода сверху вниз, используемого в кодировании Шеннона-Фано.

Терминология

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

Неофициальное описание

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

Официальное описание

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

Декомпрессия

Вообще говоря, процесс декомпрессии – это просто преобразование потока префиксных кодов в отдельные значения байтов, обычно путем последовательного прохода по узлам дерева Хаффмана по мере чтения каждого бита из входного потока (достижение листового узла обязательно завершает поиск соответствующего значения байта). Однако, прежде чем это станет возможным, дерево Хаффмана должно быть каким-то образом восстановлено. В простейшем случае, когда частоты символов достаточно предсказуемы, дерево может быть предварительно построено (и даже статистически скорректировано на каждом цикле сжатия) и, таким образом, повторно использовано, ценой некоторой потери эффективности сжатия. В противном случае, информация, необходимая для восстановления дерева, должна быть передана заранее. Наивный подход может заключаться в добавлении к потоку сжатых данных счетчиков частот каждого символа. К сожалению, накладные расходы в этом случае могут достигать нескольких килобайт, поэтому этот метод практически бесполезен. Если данные сжаты с использованием канонического кодирования, модель сжатия может быть точно восстановлена всего лишь с помощью *B* бит информации (где *B* – количество бит на символ). Другой метод – просто добавить дерево Хаффмана, бит за битом, к выходному потоку. Например, если предположить, что значение 0 представляет родительский узел, а 1 – листовой узел, то при встрече последнего, процедура построения дерева просто считывает следующие 8 бит для определения значения символа этого конкретного листа. Процесс продолжается рекурсивно до тех пор, пока не будет достигнут последний листовой узел; в этот момент дерево Хаффмана будет достоверно восстановлено. Накладные расходы при использовании такого метода варьируются примерно от 2 до 320 байтов (при условии 8-битного алфавита). Возможны и другие методы. В любом случае, поскольку сжатые данные могут содержать неиспользуемые "хвостовые биты", декомпрессор должен уметь определять, когда прекратить выдачу выходных данных. Этого можно достичь либо путем передачи длины декомпрессированных данных вместе с моделью сжатия, либо путем определения специального кодового символа, обозначающего конец входных данных (последний метод, однако, может негативно повлиять на оптимальность длины кода).

Generally speaking, the process of decompression is simply a matter of translating the stream of prefix codes to individual byte values, usually by traversing the Huffman tree node by node as each bit is read from the input stream (reaching a leaf node necessarily terminates the search for that particular byte value). Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori. A naive approach might be to prepend the frequency count of each character to the compression stream. Unfortunately, the overhead in such a case could amount to several kilobytes, so this method has little practical use. If the data is compressed using canonical encoding, the compression model can be precisely reconstructed with just bits of information (where B is the number of bits per symbol). Another method is to simply prepend the Huffman tree, bit by bit, to the output stream. For example, assuming that the value of 0 represents a parent node and 1 a leaf node, whenever the latter is encountered the tree building routine simply reads the next 8 bits to determine the character value of that particular leaf. The process continues recursively until the last leaf node is reached; at that point, the Huffman tree will thus be faithfully reconstructed. The overhead using such a method ranges from roughly 2 to 320 bytes (assuming an 8 bit alphabet). Many other techniques are possible as well. In any case, since the compressed data can include unused "trailing bits" the decompressor must be able to determine when to stop producing output. This can be accomplished by either transmitting the length of the decompressed data along with the compression model or by defining a special code symbol to signify the end of input (the latter method can adversely affect code length optimality, however).

Основные свойства

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

Оптимальность

Оригинальный алгоритм Хаффмана оптимален для кодирования символов по одному при известном распределении вероятностей входных данных, то есть для раздельного кодирования независимых символов в потоке данных. Однако он не является оптимальным, если отменяется требование кодирования по одному символу, или если функции распределения вероятностей неизвестны. Кроме того, если символы не являются независимыми и одинаково распределенными, одного кода может быть недостаточно для достижения оптимальности. Другие методы, такие как арифметическое кодирование, часто обладают лучшими возможностями сжатия. Хотя оба вышеупомянутых метода могут объединять произвольное количество символов для более эффективного кодирования и, как правило, адаптируются к фактической статистике входных данных, арифметическое кодирование делает это без существенного увеличения вычислительной или алгоритмической сложности (хотя простейшая версия медленнее и сложнее, чем кодирование Хаффмана). Такая гибкость особенно полезна, когда входные вероятности неизвестны точно или значительно меняются в потоке. Однако кодирование Хаффмана обычно быстрее, а арифметическое кодирование исторически вызывало опасения по поводу патентных прав. Поэтому многие технологии исторически избегали арифметического кодирования в пользу кодирования Хаффмана и других методов кодирования префиксов. По состоянию на середину 2010 года наиболее часто используемые методы, альтернативные кодированию Хаффмана, перешли в общественное достояние, поскольку срок действия ранних патентов истек. Для набора символов с равномерным распределением вероятностей и количеством элементов, являющимся степенью двойки, кодирование Хаффмана эквивалентно простому блочному бинарному кодированию, например, кодированию ASCII. Это отражает тот факт, что сжатие невозможно при таких входных данных, независимо от используемого метода сжатия, то есть оптимальным решением является не изменять данные. Кодирование Хаффмана оптимально среди всех методов в любом случае, когда каждый входной символ является известной, независимой и одинаково распределенной случайной величиной с вероятностью, являющейся диaдической. Префиксные коды, и, следовательно, кодирование Хаффмана в частности, как правило, неэффективны для небольших алфавитов, где вероятности часто попадают между этими оптимальными (диадическими) значениями. Наихудший случай для кодирования Хаффмана может возникнуть, когда вероятность наиболее вероятного символа значительно превышает 2−1 = 0,5, что делает верхнюю границу неэффективности неограниченной. Существует два связанных подхода для обхода этой конкретной неэффективности при сохранении использования кодирования Хаффмана. Объединение фиксированного числа символов вместе ("блокирование") часто увеличивает (и никогда не уменьшает) степень сжатия. По мере увеличения размера блока кодирование Хаффмана теоретически приближается к пределу энтропии, то есть к оптимальному сжатию. Однако блокирование произвольно больших групп символов непрактично, поскольку сложность кода Хаффмана линейно зависит от количества возможностей, которые необходимо закодировать, а это число экспоненциально зависит от размера блока. Это ограничивает степень блокирования, применяемую на практике. Практической альтернативой, широко используемой, является кодирование длин серий. Этот метод добавляет один шаг перед энтропийным кодированием, а именно подсчет (серий) повторяющихся символов, которые затем кодируются. Для простого случая процессов Бернулли кодирование Голомба оптимально среди префиксных кодов для кодирования длин серий, что было доказано с использованием методов кодирования Хаффмана. Аналогичный подход используется в факсимильных аппаратах с использованием модифицированного кодирования Хаффмана. Однако кодирование длин серий не так хорошо адаптируется к различным типам входных данных, как другие технологии сжатия.

Huffman's original algorithm is optimal for a symbol by symbol coding with a known input probability distribution, i. e., separately encoding unrelated symbols in such a data stream. However, it is not optimal when the symbol by symbol restriction is dropped, or when the probability mass functions are unknown. Also, if symbols are not independent and identically distributed, a single code may be insufficient for optimality. Other methods such as arithmetic coding often have better compression capability. Although both aforementioned methods can combine an arbitrary number of symbols for more efficient coding and generally adapt to the actual input statistics, arithmetic coding does so without significantly increasing its computational or algorithmic complexities (though the simplest version is slower and more complex than Huffman coding). Such flexibility is especially useful when input probabilities are not precisely known or vary significantly within the stream. However, Huffman coding is usually faster and arithmetic coding was historically a subject of some concern over patent issues. Thus many technologies have historically avoided arithmetic coding in favor of Huffman and other prefix coding techniques. As of mid 2010, the most commonly used techniques for this alternative to Huffman coding have passed into the public domain as the early patents have expired. For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding, e. g., ASCII coding. This reflects the fact that compression is not possible with such an input, no matter what the compression method, i. e., doing nothing to the data is the optimal thing to do. Huffman coding is optimal among all methods in any case where each input symbol is a known independent and identically distributed random variable having a probability that is dyadic. Prefix codes, and thus Huffman coding in particular, tend to have inefficiency on small alphabets, where probabilities often fall between these optimal (dyadic) points. The worst case for Huffman coding can happen when the probability of the most likely symbol far exceeds 2−1 = 0.5, making the upper limit of inefficiency unbounded. There are two related approaches for getting around this particular inefficiency while still using Huffman coding. Combining a fixed number of symbols together ("blocking") often increases (and never decreases) compression. As the size of the block approaches infinity, Huffman coding theoretically approaches the entropy limit, i. e., optimal compression. However, blocking arbitrarily large groups of symbols is impractical, as the complexity of a Huffman code is linear in the number of possibilities to be encoded, a number that is exponential in the size of a block. This limits the amount of blocking that is done in practice. A practical alternative, in widespread use, is run length encoding. This technique adds one step in advance of entropy coding, specifically counting (runs) of repeated symbols, which are then encoded. For the simple case of Bernoulli processes, Golomb coding is optimal among prefix codes for coding run length, a fact proved via the techniques of Huffman coding. A similar approach is taken by fax machines using modified Huffman coding. However, run length coding is not as adaptable to as many input types as other compression technologies.

Вариации

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

n-ary кодирование Хаффмана

Алгоритм n-арного кодирования Хаффмана использует алфавит {0, 1, ..., n − 1} для кодирования сообщений и построения n-арного дерева. Этот подход был рассмотрен Хаффманом в его оригинальной работе. Тот же алгоритм применяется, что и для двоичных кодов, за исключением того, что n наименее вероятных символов объединяются вместе, а не только 2 наименее вероятных. Следует отметить, что при n больше 2 не все наборы исходных слов могут корректно сформировать n-арное дерево для кодирования Хаффмана. В таких случаях необходимо добавлять дополнительные фиктивные элементы с нулевой вероятностью. Это связано с тем, что дерево должно обеспечивать сжатие n к 1; для двоичного кодирования это сжатие 2 к 1, и любой набор данных может обеспечить такое сжатие. Если количество исходных слов дает остаток 1 при делении на n−1, то набор исходных слов сформирует корректное дерево Хаффмана.

Адаптированное кодирование Хаффмана

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

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

Чаще всего веса, используемые в реализациях кодирования Хаффмана, представляют собой числовые вероятности, но описанный выше алгоритм этого не требует; ему необходимо лишь, чтобы веса образовывали полностью упорядоченный коммутативный моноид, то есть предоставляли способ упорядочивания весов и их сложения. Алгоритм-шаблон Хаффмана позволяет использовать любые типы весов (стоимости, частоты, пары весов, нечисловые веса) и один из множества методов объединения (не только сложение). Такие алгоритмы могут решать и другие задачи минимизации, например, минимизацию , которая впервые была применена в области проектирования электронных схем.

Кодирование Хэфмана с ограниченной длиной/минимальная дисперсия

Кодирование Хаффмана с ограничением длины — это вариант, в котором целью по-прежнему является достижение минимальной взвешенной длины пути, но добавляется дополнительное ограничение: длина каждого кодового слова должна быть меньше заданной константы. Алгоритм объединения пакетов решает эту задачу с помощью простого жадного подхода, очень похожего на используемый в алгоритме Хаффмана. Его временная сложность составляет O(n*l), где l — максимальная длина кодового слова. Неизвестно алгоритмов, решающих эту задачу за время O(n log n) или O(n), в отличие от задач классического кодирования Хаффмана с предварительной и без предварительной сортировки соответственно.

Кодирование Хаффмана с неравными расходами на письма

В стандартной задаче кодирования Хаффмана предполагается, что стоимость передачи каждого символа в наборе, из которого строятся кодовые слова, одинакова: кодовое слово длиной N всегда имеет стоимость N, независимо от количества нулей и единиц в нём. При таком предположении, минимизация общей стоимости сообщения эквивалентна минимизации общего числа символов. Кодирование Хаффмана с неравными стоимостями символов является обобщением, снимающим это предположение: символы кодирующего алфавита могут иметь разную длину из-за особенностей среды передачи. Примером служит алфавит кода Морзе, где "тире" занимает больше времени на передачу, чем "точка", и, следовательно, стоимость "тире" по времени передачи выше. Цель остаётся прежней – минимизация средневзвешенной длины кодового слова, но теперь недостаточно просто минимизировать количество символов в сообщении. Не существует алгоритма, решающего эту задачу так же эффективно, как стандартное кодирование Хаффмана, хотя решение было найдено Карпом, а затем усовершенствовано Голиным для случая целочисленных стоимостей.

Оптимальные алфавиты двоичных деревьев (кодирование HuTucker)

В стандартной задаче кодирования Хаффмана предполагается, что любое кодовое слово может соответствовать любому входному символу. В алфавитной версии алфавитный порядок входных и выходных символов должен совпадать. Таким образом, например, символу нельзя присвоить код , а вместо этого ему следует присвоить либо или . Эта задача также известна как задача Ху–Таккера, по имени Т. С. Ху и Алана Таккера, авторов статьи, впервые представившей решение этой оптимальной бинарной алфавитной задачи, которая имеет некоторое сходство с алгоритмом Хаффмана, но не является его вариантом. Более поздний метод, алгоритм Гарсии–Вачса, разработанный Адриано Гарсией и Мишель Л. Вачс (1977), использует более простую логику для выполнения тех же сравнений за то же время. Эти оптимальные алфавитные двоичные деревья часто используются в качестве двоичных деревьев поиска.

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

Если веса, соответствующие входным символам, упорядоченным в алфавитном порядке, расположены в числовом порядке, код Хаффмана имеет ту же длину, что и оптимальный алфавитный код, который можно найти, вычислив эти длины, что делает кодирование Hu–Tucker излишним. Код, полученный из входных символов, упорядоченных по числовому значению (повторно упорядоченных), иногда называют каноническим кодом Хаффмана и часто используют на практике из-за простоты кодирования и декодирования. Метод нахождения этого кода иногда называют кодированием Хаффмана–Шеннона–Фано, поскольку он оптимален, как и кодирование Хаффмана, но упорядочен по весам, как и в кодировании Шеннона–Фано. Код Хаффмана–Шеннона–Фано, соответствующий примеру, равен , который, имея те же длины кодовых слов, что и исходное решение, также является оптимальным. Однако в каноническом коде Хаффмана результат равен .

Приложения

Арифметическое кодирование и кодирование Хаффмана дают эквивалентные результаты – достижение энтропии – когда каждый символ имеет вероятность вида 1/2k. В иных случаях арифметическое кодирование может обеспечить лучшее сжатие, чем кодирование Хаффмана, поскольку – интуитивно – его "кодовые слова" могут иметь фактически нецелочисленную длину в битах, в то время как кодовые слова в префиксных кодах, таких как коды Хаффмана, могут иметь только целое число бит. Следовательно, кодовое слово длиной k оптимально соответствует символу с вероятностью 1/2k, а другие вероятности представлены не оптимально; тогда как длина кодового слова в арифметическом кодировании может быть точно подобрана под истинную вероятность символа. Эта разница особенно заметна при небольшом размере алфавита. Тем не менее, префиксные коды остаются широко используемыми благодаря их простоте, высокой скорости и отсутствию патентных ограничений. Они часто используются как "бэкэнд" для других методов сжатия. Алгоритм Deflate (используемый в PKZIP) и мультимедийные кодеки, такие как JPEG и MP3, используют фронтенд-модель и квантование, за которыми следует применение префиксных кодов; их часто называют "кодами Хаффмана", хотя в большинстве приложений используются предварительно определенные коды переменной длины, а не коды, разработанные с помощью алгоритма Хаффмана.