Кодирование Хаффмана

Дерево Хаффмана, сформированное из точных частот текста «это пример дерева Хаффмана». Ниже приведены частоты и коды каждого символа. Для кодирования предложения этим кодом требуется 135 (или 147) бит, в отличие от 288 (или 180) бит, если использовалось 36 символов из 8 (или 5) бит. (Это предполагает, что структура кодового дерева известна декодеру, и поэтому ее не нужно учитывать как часть передаваемой информации.)

В информатике и теории информации , код Хаффмана является конкретным типом оптимального кода префикса , который обычно используется для сжатия данных без потерь . Процесс поиска или использования такого кода происходит с помощью кодирования Хаффмана , алгоритма, разработанного Дэвидом А. Хаффманом, когда он был доктором наук. студент Массачусетского технологического института , и опубликованный в статье 1952 года «Метод построения кодов с минимальной избыточностью». ^[1]

Выходные данные алгоритма Хаффмана можно рассматривать как кодовую таблицу переменной длины для кодирования исходного символа (например, символа в файле). Алгоритм выводит эту таблицу из оцененной вероятности или частоты появления ( веса ) для каждого возможного значения исходного символа. Как и в других методах энтропийного кодирования , более общие символы обычно представляются с использованием меньшего количества битов, чем менее распространенные символы. Метод Хаффмана можно эффективно реализовать, найдя код во времени, линейный по отношению к количеству входных весов, если эти веса отсортированы. ^[2] Однако, несмотря на то, что среди методов кодирования символов по отдельности оптимально, кодирование Хаффмана не всегда оптимально.среди всех методов сжатия - заменяется арифметическим кодированием или асимметричными системами счисления, если требуется более высокая степень сжатия.

История [ править ]

В 1951 году Дэвид А. Хаффман и его одноклассники из Массачусетского технологического института по теории информации получили выбор между курсовой работой или выпускным экзаменом . Профессор Роберт М. Фано дал курсовую работу по проблеме поиска наиболее эффективного двоичного кода. Хаффман, не сумевший доказать, что какой-либо код является наиболее эффективным, собирался сдаться и начать подготовку к финалу, когда ему пришла в голову идея использовать двоичное дерево с частотной сортировкой и быстро доказал, что этот метод является наиболее эффективным. ^[3]

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

Терминология [ править ]

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

Определение проблемы [ править ]

Неофициальное описание [ править ]

Данный

Набор символов и их веса (обычно пропорциональные вероятностям).

Находить

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

Формализованное описание [ править ]

Вход .
Алфавит , который является символом алфавита размера . Кортеж , который является кортежем весов (положительные) символов ( как правило , пропорциональной вероятность), то есть . Выход . Код , который представляет собой набор (двоичных) кодовых слов, где - кодовое слово для . Цель . Позвольте быть взвешенной длиной пути кода . Состояние: для любого кода .${\ Displaystyle А = (а_ {1}, а_ {2}, \ точки, а_ {п})}$${\ displaystyle n}$
${\ displaystyle W = (w_ {1}, w_ {2}, \ dots, w_ {n})}$${\ displaystyle w_ {i} = \ mathrm {вес} \ left (a_ {i} \ right), \, i \ in \ {1,2, ..., n \}}$


${\ displaystyle C \ left (W \ right) = (c_ {1}, c_ {2}, \ dots, c_ {n})}$${\ displaystyle c_ {i}}$${\ Displaystyle а_ {я}, \, я \ в \ {1,2, ..., п \}}$


${\ displaystyle L \ left (C \ left (W \ right) \ right) = \ sum _ {i = 1} ^ {n} {w_ {i} \ times \ mathrm {length} \ left (c_ {i} \верно)}}$${\ displaystyle C}$${\ Displaystyle L \ влево (С \ влево (W \ вправо) \ вправо) \ Leq L \ влево (Т \ влево (W \ вправо) \ вправо)}$${\ Displaystyle Т \ влево (W \ вправо)}$

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

Мы приводим пример результата кодирования Хаффмана для кода с пятью символами и заданными весами. Мы не будем проверять, что он минимизирует L по всем кодам, но мы вычислим L и сравним его с энтропией Шеннона H данного набора весов; результат почти оптимальный.

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

Как определено Шенноном (1948) , информационное содержание h (в битах) каждого символа a _i с ненулевой вероятностью равно

${\ displaystyle h (a_ {i}) = \ log _ {2} {1 \ over w_ {i}}.}$

Энтропия Н (в битах) является взвешенной суммой, по всем символам _я с ненулевой вероятностью ш _I , информационного содержания каждого символа:

${\ displaystyle H (A) = \ sum _ {w_ {i}> 0} w_ {i} h (a_ {i}) = \ sum _ {w_ {i}> 0} w_ {i} \ log _ { 2} {1 \ over w_ {i}} = - \ sum _ {w_ {i}> 0} w_ {i} \ log _ {2} {w_ {i}}.}$

(Примечание: символ с нулевой вероятностью имеет нулевой вклад в энтропию, поскольку для простоты символы с нулевой вероятностью могут быть исключены из приведенной выше формулы.)${\ displaystyle \ lim _ {w \ to 0 ^ {+}} w \ log _ {2} w = 0}$

Как следствие теоремы Шеннона о кодировании источника энтропия - это мера наименьшей длины кодового слова, которая теоретически возможна для данного алфавита с соответствующими весами. В этом примере средневзвешенная длина кодового слова составляет 2,25 бита на символ, лишь немного больше, чем вычисленная энтропия, равная 2,205 бит на символ. Таким образом, этот код не только оптимален в том смысле, что никакой другой возможный код не работает лучше, но и очень близок к теоретическому пределу, установленному Шенноном.

В общем, код Хаффмана не обязательно должен быть уникальным. Таким образом, набор кодов Хаффмана для данного распределения вероятностей является непустым подмножеством кодов, минимизирующих это распределение вероятностей. (Однако для каждого минимизирующего назначения длины кодового слова существует по крайней мере один код Хаффмана с такой длиной.)${\displaystyle L(C)}$

Базовая техника [ править ]

Сжатие [ править ]

Источник с вероятностью генерирует 4 разных символа . Бинарное дерево генерируется слева направо, беря два наименее вероятных символа и складывая их вместе, чтобы сформировать другой эквивалентный символ, имеющий вероятность, равную сумме двух символов. Процесс повторяется до тех пор, пока не останется только один символ. Затем дерево можно читать в обратном направлении, справа налево, назначая разные биты разным ветвям. Окончательный код Хаффмана:${\displaystyle \{a_{1},a_{2},a_{3},a_{4}\}}$${\displaystyle \{0.4;0.35;0.2;0.05\}}$

Символ	Код
а1	0
а2	10
а3	110
а4	111

Стандартный способ представить сигнал, состоящий из 4 символов, - использовать 2 бита / символ, но энтропия источника составляет 1,74 бита / символ. Если этот код Хаффмана используется для представления сигнала, то средняя длина снижается до 1,85 бит / символ; это все еще далеко от теоретического предела, потому что вероятности символов отличаются от отрицательных степеней двойки.

Этот метод работает путем создания двоичного дерева узлов. Их можно хранить в обычном массиве , размер которого зависит от количества символов . Узел может быть либо листовым, либо внутренним узлом . Изначально все узлы являются листовыми узлами, которые содержат сам символ , вес (частоту появления) символа и, необязательно, ссылку на родительский узел, что упрощает чтение кода (в обратном направлении), начиная с листового узла. . Внутренние узлы содержат вес , ссылки на два дочерних узла и дополнительную ссылку на родительский${\displaystyle n}$узел. По общепринятому соглашению бит «0» представляет собой следующий за левым дочерним элементом, а бит «1» - за правым дочерним элементом. Готовое дерево имеет до листовых узлов и внутренних узлов. Дерево Хаффмана, в котором не используются неиспользуемые символы, дает наиболее оптимальную длину кода.${\displaystyle n}$${\displaystyle n-1}$

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

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

1. Создайте листовой узел для каждого символа и добавьте его в приоритетную очередь.
2. Пока в очереди более одного узла:
   1. Удалите из очереди два узла с наивысшим приоритетом (наименьшей вероятностью)
   2. Создайте новый внутренний узел с этими двумя узлами как дочерними и с вероятностью, равной сумме вероятностей двух узлов.
   3. Добавьте новый узел в очередь.
3. Оставшийся узел является корневым узлом, и дерево завершено.

Поскольку эффективные структуры данных очереди приоритетов требуют времени O (log n ) на вставку, а дерево с n листьями имеет 2 n -1 узлов, этот алгоритм работает за время O ( n log n ), где n - количество символов.

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

1. Начните с того количества листьев, которое есть символов.
2. Поместите все листовые узлы в первую очередь (по вероятности в порядке возрастания, чтобы наименее вероятный элемент оказался в начале очереди).
3. Пока в очередях более одного узла:
   1. Удалите из очереди два узла с наименьшим весом, исследуя фронты обеих очередей.
   2. Создайте новый внутренний узел с двумя только что удаленными узлами в качестве дочерних (любой узел может быть либо дочерним) и суммой их весов в качестве нового веса.
   3. Поместите новый узел в конец второй очереди.
4. Оставшийся узел - корневой узел; теперь дерево создано.

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

1. Начните с текущего узла, установленного в корень.
2. Если узел не является листовым узлом, пометьте край левого дочернего элемента как 0, а край правого дочернего элемента как 1 . Повторите процесс как для левого, так и для правого ребенка.

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

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

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

Декомпрессия [ править ]

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

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

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

Оптимальность [ править ]

См. Также Арифметическое кодирование # Кодирование Хаффмана

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

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

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

Кодирование Хаффмана является оптимальным среди всех методов в любом случае, когда каждый входной символ является известной независимой и одинаково распределенной случайной величиной, имеющей диадическую вероятность . Коды префикса и, следовательно, кодирование Хаффмана в частности, имеют тенденцию неэффективно работать с маленькими алфавитами, где вероятности часто находятся между этими оптимальными (диадическими) точками. Худший случай для кодирования Хаффмана может произойти, когда вероятность наиболее вероятного символа намного превышает 2 ^-1 = 0,5, что делает верхний предел неэффективности неограниченным.

Есть два связанных подхода для обхода этой конкретной неэффективности при использовании кодирования Хаффмана. Объединение фиксированного количества символов вместе («блокирование») часто увеличивает (и никогда не уменьшает) сжатие. Поскольку размер блока приближается к бесконечности, кодирование Хаффмана теоретически приближается к пределу энтропии, то есть к оптимальному сжатию. ^[4] Однако блокирование произвольно больших групп символов непрактично, поскольку сложность кода Хаффмана линейна по отношению к количеству возможностей, которые необходимо кодировать, а это число экспоненциально зависит от размера блока. Это ограничивает количество блокировок, которое выполняется на практике.

Практической альтернативой, которая широко используется, является кодирование длин серий . Этот метод добавляет один шаг перед энтропийным кодированием, в частности подсчет (запусков) повторяющихся символов, которые затем кодируются. Для простого случая процессов Бернулли , Голомба кодирование является оптимальным среди префиксных кодов для кодирования длины серии, факт доказан с помощью методов кодирования по алгоритму Хаффмана. ^[5] Аналогичный подход используется факсимильными аппаратами, использующими модифицированное кодирование Хаффмана . Однако кодирование длин серий не так легко адаптируется к такому количеству типов ввода, как другие технологии сжатия.

Варианты [ править ]

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

n -арное кодирование Хаффмана [ править ]

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

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

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

Алгоритм шаблона Хаффмана [ править ]

Чаще всего веса, используемые в реализациях кодирования Хаффмана, представляют собой числовые вероятности, но приведенный выше алгоритм не требует этого; для этого требуется только, чтобы веса образовывали полностью упорядоченный коммутативный моноид , то есть способ упорядочить веса и сложить их. Алгоритм шаблона Хаффмана дает возможности использовать любой вид весов (расходы, частоты, пар весов, не-численные веса) и один из многих методов , сочетающих ( а не только сложение). Такие алгоритмы могут решать другие задачи минимизации, такие как минимизация - проблема, которая впервые применяется при проектировании схем.${\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}$

Кодирование Хаффмана с ограниченной длиной / кодирование Хаффмана с минимальной дисперсией [ править ]

Кодирование Хаффмана с ограничением длины - это вариант, в котором цель по-прежнему состоит в достижении минимальной взвешенной длины пути, но существует дополнительное ограничение, заключающееся в том, что длина каждого кодового слова должна быть меньше заданной константы. Алгоритм пакета слияния решает эту проблему с помощью простого жадного подхода очень похож на используемом алгоритме Хаффмана. Его временная сложность равна , где - максимальная длина кодового слова. Алгоритм не известен , чтобы решить эту проблему или время, в отличии от предварительно отсортированных и неупорядоченных обычных проблем Хаффмана соответственно.${\displaystyle O(nL)}$${\displaystyle L}$ O ( n ) {\displaystyle O(n)} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

Кодирование Хаффмана с неравной стоимостью букв [ править ]

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

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

Оптимальные буквенные двоичные деревья (кодирование Ху – Таккера) [ править ]

В стандартной задаче кодирования Хаффмана предполагается, что любое кодовое слово может соответствовать любому входному символу. В алфавитной версии алфавитный порядок входов и выходов должен быть идентичным. Таким образом, например, не может быть назначен код , вместо этого следует назначить либо или . Эта проблема также известна как проблема Ху – Таккера после TC Hu и Alan Tucker , авторов статьи, впервые представляющей решение этой оптимальной двоичной алфавитной задачи ^[7], которая имеет некоторое сходство с алгоритмом Хаффмана, но не является вариант этого алгоритма. Более поздний метод, то алгоритм-Гарсиа Вахс из Адриано Гарсия${\displaystyle A=\left\{a,b,c\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}$${\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}$ O ( n log ⁡ n ) {\displaystyle O(n\log n)} и Мишель Л. Вакс (1977) использует более простую логику для выполнения тех же сравнений с той же временной границей. Эти оптимальные буквенные двоичные деревья часто используются в качестве двоичных деревьев поиска . ^[8]

Канонический код Хаффмана [ править ]

Если веса, соответствующие алфавитно упорядоченным входным данным, расположены в числовом порядке, код Хаффмана имеет ту же длину, что и оптимальный буквенный код, который можно найти при вычислении этих длин, что делает кодирование Ху – Такера ненужным. Код, полученный в результате числового (пере-) упорядоченного ввода, иногда называют каноническим кодом Хаффмана и часто используется на практике из-за простоты кодирования / декодирования. Метод нахождения этого кода иногда называют кодированием Хаффмана – Шеннона – Фано , поскольку он оптимален, как кодирование Хаффмана, но имеет буквенное обозначение вероятности веса, как кодирование Шеннона – Фано . Код Хаффмана – Шеннона – Фано, соответствующий примеру, имеет вид${\displaystyle \{000,001,01,10,11\}}$, который, имея ту же длину кодового слова, что и исходное решение, также является оптимальным. Но в каноническом коде Хаффмана результат такой .${\displaystyle \{110,111,00,01,10\}}$

Приложения [ править ]

Арифметическое кодирование и кодирование Хаффмана дают эквивалентные результаты - достижение энтропии - когда каждый символ имеет вероятность формы 1/2 ^k . В других обстоятельствах арифметическое кодирование может предложить лучшее сжатие, чем кодирование Хаффмана, потому что - интуитивно - его «кодовые слова» могут иметь фактически нецелую длину в битах, тогда как кодовые слова в префиксных кодах, таких как коды Хаффмана, могут иметь только целое число битов. Следовательно, кодовое слово длины k только оптимально соответствует символу с вероятностью 1/2 ^k, а другие вероятности не представлены оптимально; тогда как длина кодового слова при арифметическом кодировании может быть сделана так, чтобы она точно соответствовала истинной вероятности символа. Эта разница особенно заметна для маленьких букв.

Тем не менее префиксные коды по-прежнему широко используются из-за их простоты, высокой скорости и отсутствия патентной защиты . Они часто используются в качестве «основы» для других методов сжатия. Deflate ( алгоритм PKZIP ) и мультимедийные кодеки, такие как JPEG и MP3, имеют интерфейсную модель и квантование, за которым следует использование префиксных кодов; их часто называют «кодами Хаффмана», хотя в большинстве приложений используются заранее определенные коды переменной длины, а не коды, разработанные с использованием алгоритма Хаффмана.

Ссылки [ править ]

Викискладе есть медиафайлы, связанные с кодированием Хаффмана .

Библиография [ править ]

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 16.3, стр. 385–392. 

Внешние ссылки [ править ]

• Кодирование Хаффмана на разных языках в Rosetta Code
• Коды Хаффмана (реализация на Python)
• Визуализация кодирования Хаффмана