В информатике и теории информации , код Хаффмана является конкретным типом оптимального кода префикса , который обычно используется для сжатия данных без потерь . Процесс поиска или использования такого кода осуществляется с помощью кодирования Хаффмана , алгоритма, разработанного Дэвидом А. Хаффманом, когда он был доктором наук. студент Массачусетского технологического института , и опубликованный в статье 1952 года «Метод построения кодов с минимальной избыточностью». [1]
Char | Частота | Код |
---|---|---|
космос | 7 | 111 |
а | 4 | 010 |
е | 4 | 000 |
ж | 3 | 1101 |
час | 2 | 1010 |
я | 2 | 1000 |
м | 2 | 0111 |
п | 2 | 0010 |
s | 2 | 1011 |
т | 2 | 0110 |
л | 1 | 11001 |
о | 1 | 00110 |
п | 1 | 10011 |
р | 1 | 11000 |
ты | 1 | 00111 |
Икс | 1 | 10010 |
Выходные данные алгоритма Хаффмана можно рассматривать как кодовую таблицу переменной длины для кодирования исходного символа (например, символа в файле). Алгоритм выводит эту таблицу из оцененной вероятности или частоты появления ( веса ) для каждого возможного значения исходного символа. Как и в других методах энтропийного кодирования , более общие символы обычно представляются с использованием меньшего количества битов, чем менее распространенные символы. Метод Хаффмана можно эффективно реализовать, найдя код во времени, линейный по количеству входных весов, если эти веса отсортированы. [2] Однако, несмотря на то, что кодирование символов по отдельности является оптимальным среди методов кодирования символов, кодирование Хаффмана не всегда оптимально среди всех методов сжатия - оно заменяется арифметическим кодированием [3] или асимметричными системами счисления [4], если требуется более высокая степень сжатия.
История
В 1951 году Дэвид А. Хаффман и его одноклассники из Массачусетского технологического института по теории информации получили выбор между курсовой работой или выпускным экзаменом . Профессор Роберт М. Фано дал курсовую работу по проблеме поиска наиболее эффективного двоичного кода. Хаффман, не сумевший доказать, что какой-либо код является наиболее эффективным, собирался сдаться и начать подготовку к финалу, когда ему пришла в голову идея использовать двоичное дерево с частотной сортировкой и быстро доказал, что этот метод является наиболее эффективным. [5]
При этом Хаффман превзошел Фано, который работал с изобретателем теории информации Клодом Шенноном над разработкой аналогичного кода. Построение дерева снизу вверх гарантирует оптимальность, в отличие от нисходящего подхода кодирования Шеннона – Фано .
Терминология
Кодирование Хаффмана использует определенный метод для выбора представления для каждого символа, в результате чего получается префиксный код (иногда называемый «кодами без префикса», то есть битовая строка, представляющая какой-либо конкретный символ, никогда не является префиксом битовой строки, представляющей любой другой символ). Кодирование Хаффмана является настолько распространенным методом создания префиксных кодов, что термин «код Хаффмана» широко используется как синоним «префиксного кода», даже если такой код не создается алгоритмом Хаффмана.
Определение проблемы
Неформальное описание
- Дано
- Набор символов и их веса (обычно пропорциональные вероятностям).
- Находить
- Префикс свободного двоичный код (набор кодовых слов) с минимумом ожидается длиной кодового слова ( то же самое, дерево с минимальной взвешенной длиной пути от корня ).
Формализованное описание
Вход .
Алфавит, который представляет собой алфавит символов размера .
Кортеж, который представляет собой набор (положительных) весов символов (обычно пропорциональных вероятностям), т. е. .
Выход .
Код, который представляет собой набор (двоичных) кодовых слов, где это кодовое слово для .
Цель .
Позволять быть взвешенной длиной пути кода . Условие: для любого кода .
Пример
Приведем пример результата кодирования Хаффмана для кода с пятью символами и заданными весами. Мы не будем проверять, что он минимизирует L по всем кодам, но мы вычислим L и сравним его с энтропией Шеннона H данного набора весов; результат почти оптимальный.
Вход ( А , Вт ) | Символ ( a i ) | а | б | c | d | е | Сумма |
---|---|---|---|---|---|---|---|
Вес ( w i ) | 0,10 | 0,15 | 0,30 | 0,16 | 0,29 | = 1 | |
Выход C | Кодовые слова ( c i ) | 010 | 011 | 11 | 00 | 10 | |
Длина кодового слова (в битах) ( l i ) | 3 | 3 | 2 | 2 | 2 | ||
Вклад в взвешенную длину пути ( l i w i ) | 0,30 | 0,45 | 0,60 | 0,32 | 0,58 | L ( C ) = 2,25 | |
Оптимальность | Бюджет вероятности (2 - l i ) | 1/8 | 1/8 | 1/4 | 1/4 | 1/4 | = 1,00 |
Информационное содержание (в битах) (- log 2 w i ) ≈ | 3,32 | 2,74 | 1,74 | 2,64 | 1,79 | ||
Вклад в энтропию (- w i log 2 w i ) | 0,332 | 0,411 | 0,521 | 0,423 | 0,518 | H ( А ) = 2,205 |
Для любого кода, который является взаимно уникальным , что означает, что код однозначно декодируется , сумма бюджетов вероятностей по всем символам всегда меньше или равна единице. В этом примере сумма строго равна единице; в результате код называется полным кодом. Если это не так, всегда можно получить эквивалентный код, добавив дополнительные символы (с соответствующими нулевыми вероятностями), чтобы сделать код законченным, сохраняя при этом его уникальность .
Как определено Шенноном (1948) , информационное содержание h (в битах) каждого символа a i с ненулевой вероятностью равно
Энтропия Н (в битах) является взвешенной суммой, по всем символам я с ненулевой вероятностью ш I , информационного содержания каждого символа:
(Примечание: символ с нулевой вероятностью имеет нулевой вклад в энтропию, поскольку Поэтому для простоты символы с нулевой вероятностью можно исключить из приведенной выше формулы.)
Как следствие теоремы Шеннона о кодировании источника энтропия является мерой наименьшей длины кодового слова, которая теоретически возможна для данного алфавита с соответствующими весами. В этом примере средневзвешенная длина кодового слова составляет 2,25 бита на символ, что лишь немного превышает вычисленную энтропию, равную 2,205 бит на символ. Таким образом, этот код не только оптимален в том смысле, что никакой другой возможный код не работает лучше, но и очень близок к теоретическому пределу, установленному Шенноном.
В общем, код Хаффмана не обязательно должен быть уникальным. Таким образом, набор кодов Хаффмана для данного распределения вероятностей является непустым подмножеством кодов, минимизирующихдля этого распределения вероятностей. (Однако для каждого минимизирующего назначения длины кодового слова существует по крайней мере один код Хаффмана с такой длиной.)
Базовая техника
Сжатие
Этот метод работает путем создания двоичного дерева узлов. Их можно хранить в обычном массиве , размер которого зависит от количества символов,. Узел может быть либо листовым, либо внутренним узлом . Первоначально все узлы являются листовыми узлами, которые содержат сам символ , вес (частоту появления) символа и, необязательно, ссылку на родительский узел, что упрощает чтение кода (в обратном направлении), начиная с листового узла. . Внутренние узлы содержат вес , ссылки на два дочерних узла и дополнительную ссылку на родительский узел. По общепринятому соглашению бит «0» представляет следующий за левым потомком, а бит «1» - за правым дочерним элементом. Готовое дерево имеет до листовые узлы и внутренние узлы. Дерево Хаффмана, в котором не используются неиспользуемые символы, дает наиболее оптимальную длину кода.
Процесс начинается с листовых узлов, содержащих вероятности символа, который они представляют. Затем процесс берет два узла с наименьшей вероятностью и создает новый внутренний узел, имеющий эти два узла в качестве дочерних. Вес нового узла устанавливается равным сумме веса дочерних элементов. Затем мы снова применяем этот процесс к новому внутреннему узлу и к оставшимся узлам (т. Е. Мы исключаем два листовых узла), мы повторяем этот процесс до тех пор, пока не останется только один узел, который является корнем дерева Хаффмана.
В простейшем алгоритме построения используется приоритетная очередь, в которой узел с наименьшей вероятностью получает высший приоритет:
- Создайте листовой узел для каждого символа и добавьте его в очередь приоритетов.
- Пока в очереди более одного узла:
- Удалите из очереди два узла с наивысшим приоритетом (наименьшей вероятностью)
- Создайте новый внутренний узел с этими двумя узлами в качестве дочерних и с вероятностью, равной сумме вероятностей двух узлов.
- Добавьте новый узел в очередь.
- Оставшийся узел является корневым узлом, и дерево завершено.
Поскольку эффективные структуры данных очереди приоритетов требуют времени O (log n ) на вставку, а дерево с n листьями имеет 2 n -1 узлов, этот алгоритм работает за время O ( n log n ), где n - количество символов.
Если символы отсортированы по вероятности, существует метод линейного времени (O ( n )) для создания дерева Хаффмана с использованием двух очередей , первая из которых содержит начальные веса (вместе с указателями на связанные листья) и комбинированные веса. (вместе с указателями на деревья) помещается в конец второй очереди. Это гарантирует, что самый низкий вес всегда сохраняется в начале одной из двух очередей:
- Начните с того количества листьев, которое есть символов.
- Поместите все листовые узлы в первую очередь (по вероятности в возрастающем порядке, чтобы наименее вероятный элемент оказался в начале очереди).
- Пока в очередях более одного узла:
- Удалите из очереди два узла с наименьшим весом, исследуя фронты обеих очередей.
- Создайте новый внутренний узел с двумя только что удаленными узлами в качестве дочерних (любой узел может быть либо дочерним) и суммой их весов в качестве нового веса.
- Поместите новый узел в конец второй очереди.
- Оставшийся узел является корневым узлом; теперь дерево сгенерировано.
После того, как дерево Хаффмана было сгенерировано, оно просматривается для создания словаря, который отображает символы в двоичные коды следующим образом:
- Начните с текущего узла, установленного в корень.
- Если узел не является листовым узлом, пометьте край левого дочернего элемента как 0, а край правого дочернего элемента как 1 . Повторите процесс как для левого, так и для правого ребенка.
Окончательное кодирование любого символа затем считывается путем конкатенации меток на краях по пути от корневого узла к символу.
Во многих случаях временная сложность здесь не очень важна при выборе алгоритма, поскольку n - это количество символов в алфавите, которое обычно является очень маленьким числом (по сравнению с длиной сообщения, которое нужно закодировать); тогда как анализ сложности касается поведения, когда n становится очень большим.
Обычно полезно минимизировать вариацию длины кодового слова. Например, буфер связи, принимающий данные в кодировке Хаффмана, может нуждаться в большем размере, чтобы иметь дело с особенно длинными символами, если дерево особенно несбалансировано. Чтобы минимизировать дисперсию, просто разорвите связи между очередями, выбрав элемент в первой очереди. Эта модификация сохранит математическую оптимальность кодирования Хаффмана, одновременно минимизируя дисперсию и минимизируя длину самого длинного кода символа.
Декомпрессия
Вообще говоря, процесс распаковки - это просто вопрос преобразования потока префиксных кодов в отдельные байтовые значения, обычно путем обхода узла дерева Хаффмана за узлом, когда каждый бит считывается из входного потока (достижение конечного узла обязательно завершает поиск для этого конкретного байтового значения). Однако, прежде чем это может произойти, дерево Хаффмана должно быть каким-то образом реконструировано. В простейшем случае, когда частота символов достаточно предсказуема, дерево можно предварительно построить (и даже статистически отрегулировать для каждого цикла сжатия) и, таким образом, повторно использовать каждый раз за счет, по крайней мере, некоторой степени эффективности сжатия. В противном случае информация для восстановления дерева должна быть отправлена априори. Наивный подход может заключаться в добавлении счетчика частоты каждого символа к потоку сжатия. К сожалению, накладные расходы в таком случае могут составить несколько килобайт, поэтому практического применения этот метод не имеет. Если данные сжаты с использованием канонического кодирования , модель сжатия может быть точно восстановлена с помощью всего лишь бит информации (где это количество бит на символ). Другой метод - просто добавить дерево Хаффмана побитно к выходному потоку. Например, предполагая, что значение 0 представляет родительский узел, а 1 - листовой узел, всякий раз, когда последний встречается, процедура построения дерева просто считывает следующие 8 бит, чтобы определить символьное значение этого конкретного листа. Процесс продолжается рекурсивно до тех пор, пока не будет достигнут последний листовой узел; в этот момент дерево Хаффмана будет точно реконструировано. Накладные расходы при использовании такого метода составляют примерно от 2 до 320 байтов (при использовании 8-битного алфавита). Возможны и многие другие техники. В любом случае, поскольку сжатые данные могут включать в себя неиспользуемые «конечные биты», декомпрессор должен иметь возможность определять, когда прекратить выдачу вывода. Это может быть достигнуто либо путем передачи длины распакованных данных вместе с моделью сжатия, либо путем определения специального символа кода для обозначения конца ввода (однако последний метод может отрицательно повлиять на оптимальность длины кода).
Основные свойства
Используемые вероятности могут быть общими для области приложения, основанными на среднем опыте, или они могут быть фактическими частотами, найденными в сжимаемом тексте. Для этого необходимо, чтобы частотная таблица сохранялась со сжатым текстом. См. Раздел «Декомпрессия» выше для получения дополнительной информации о различных методах, используемых для этой цели.
Оптимальность
Исходный алгоритм Хаффмана оптимален для посимвольного кодирования с известным распределением входных вероятностей, т. Е. Раздельного кодирования несвязанных символов в таком потоке данных. Однако это не оптимально, когда ограничение на посимвольное снятие ограничения или когда функции вероятностных масс неизвестны. Кроме того, если символы не являются независимыми и одинаково распределенными , одного кода может быть недостаточно для оптимальности. Другие методы, такие как арифметическое кодирование, часто имеют лучшую способность к сжатию.
Хотя оба вышеупомянутых метода могут комбинировать произвольное количество символов для более эффективного кодирования и, как правило, адаптироваться к фактической статистике ввода, арифметическое кодирование делает это без значительного увеличения вычислительной или алгоритмической сложности (хотя простейшая версия медленнее и сложнее, чем кодирование Хаффмана) . Такая гибкость особенно полезна, когда входные вероятности точно не известны или значительно варьируются в пределах потока. Однако кодирование Хаффмана обычно быстрее, и арифметическое кодирование исторически было предметом некоторой озабоченности в связи с патентными проблемами. Таким образом, многие технологии исторически избегали арифметического кодирования в пользу метода Хаффмана и других методов префиксного кодирования. По состоянию на середину 2010 года наиболее часто используемые методы для этой альтернативы кодированию Хаффмана перешли в общественное достояние, поскольку истек срок действия ранних патентов.
Для набора символов с равномерным распределением вероятностей и числом членов , равным степени двойки , кодирование Хаффмана эквивалентно простому двоичному блочному кодированию , например, кодированию ASCII . Это отражает тот факт, что сжатие невозможно с таким вводом, независимо от метода сжатия, т. Е. Ничего не делать с данными является оптимальным решением.
Кодирование Хаффман является оптимальным среди всех методов в любом случае , где каждый входной символ является известным независимым и одинаково распределенным случайной величиной , имеющей вероятность того, что является диадическим . Коды префикса и, следовательно, кодирование Хаффмана, в частности, имеют тенденцию неэффективно работать с маленькими алфавитами, где вероятности часто находятся между этими оптимальными (диадическими) точками. Наихудший случай для кодирования Хаффмана может произойти, когда вероятность наиболее вероятного символа намного превышает 2 -1 = 0,5, что делает верхний предел неэффективности неограниченным.
Есть два связанных подхода, позволяющих обойти эту конкретную неэффективность, продолжая использовать кодирование Хаффмана. Объединение фиксированного количества символов вместе («блокирование») часто увеличивает (и никогда не уменьшает) сжатие. Поскольку размер блока приближается к бесконечности, кодирование Хаффмана теоретически приближается к пределу энтропии, то есть к оптимальному сжатию. [6] Однако блокирование произвольно больших групп символов непрактично, поскольку сложность кода Хаффмана линейна по отношению к количеству возможностей, которые необходимо кодировать, а это число экспоненциально зависит от размера блока. Это ограничивает количество блокировок, которое выполняется на практике.
Практической альтернативой, которая широко используется, является кодирование длин серий . Этот метод добавляет один шаг перед энтропийным кодированием, в частности подсчет (запусков) повторяющихся символов, которые затем кодируются. Для простого случая процессов Бернулли , Голомба кодирование является оптимальным среди префиксных кодов для кодирования длины серии, факт доказан с помощью методов кодирования по алгоритму Хаффмана. [7] Аналогичный подход используется факсимильными аппаратами, использующими модифицированное кодирование Хаффмана . Однако кодирование длин серий не так легко адаптируется к такому количеству типов ввода, как другие технологии сжатия.
Вариации
Существует множество вариантов кодирования Хаффмана [8], некоторые из которых используют алгоритм, подобный Хаффману, а другие находят оптимальные префиксные коды (при этом, например, устанавливают различные ограничения на вывод). Обратите внимание, что в последнем случае метод не обязательно должен быть похожим на Хаффмана, и, действительно, даже не обязательно должен быть полиномиальным временем .
n -арное кодирование Хаффмана
П -ичного Хаффман алгоритм использует {0, 1, ..., п - 1} алфавит для кодирования сообщения и построить п -ичного дерева. Этот подход был рассмотрен Хаффманом в его оригинальной статье. Применяется тот же алгоритм, что и для двоичных ( n равно 2) кодов, за исключением того, что n наименее вероятных символов взяты вместе, а не только 2 наименее вероятных. Обратите внимание, что для n больше 2 не все наборы исходных слов могут правильно сформировать n- мерное дерево для кодирования Хаффмана. В этих случаях должны быть добавлены дополнительные заполнители с нулевой вероятностью. Это потому, что дерево должно формировать подрядчика n к 1; для двоичного кодирования это подрядчик 2: 1, и набор любого размера может образовать такого подрядчика. Если количество исходных слов сравнимо с 1 по модулю n -1, то набор исходных слов сформирует собственное дерево Хаффмана.
Адаптивное кодирование Хаффмана
Вариант, называемый адаптивным кодированием Хаффмана, включает динамическое вычисление вероятностей на основе последних фактических частот в последовательности исходных символов и изменение структуры дерева кодирования для соответствия обновленным оценкам вероятности. На практике он используется редко, поскольку стоимость обновления дерева делает его медленнее, чем оптимизированное адаптивное арифметическое кодирование , которое является более гибким и имеет лучшее сжатие.
Алгоритм шаблона Хаффмана
Чаще всего веса, используемые в реализациях кодирования Хаффмана, представляют собой числовые вероятности, но приведенный выше алгоритм не требует этого; для этого требуется только, чтобы веса образовывали полностью упорядоченный коммутативный моноид , что означает способ упорядочивания весов и их сложения. Алгоритм шаблона Хаффмана дает возможности использовать любой вид весов (расходы, частоты, пар весов, не-численные веса) и один из многих методов , сочетающих ( а не только сложение). Такие алгоритмы могут решать другие задачи минимизации, такие как минимизация, проблема, впервые относящаяся к схемотехнике.
Кодирование Хаффмана с ограниченной длиной / кодирование Хаффмана с минимальной дисперсией
Кодирование Хаффмана с ограничением длины - это вариант, в котором цель по-прежнему состоит в достижении минимальной взвешенной длины пути, но существует дополнительное ограничение, заключающееся в том, что длина каждого кодового слова должна быть меньше заданной константы. Алгоритм пакета слияния решает эту проблему с помощью простого жадного подхода очень похож на используемом алгоритме Хаффмана. Его временная сложность составляет, где - максимальная длина кодового слова. Неизвестно ни одного алгоритма для решения этой проблемы в О ( п ) {\ Displaystyle О (п)} или же О ( п бревно п ) {\ Displaystyle О (п \ журнал п)} времени, в отличие от предварительно отсортированных и неотсортированных обычных задач Хаффмана соответственно.
Кодирование Хаффмана с неравной стоимостью письма
В стандартной задаче кодирования Хаффмана предполагается, что каждый символ в наборе, из которого построены кодовые слова, имеет одинаковую стоимость для передачи: кодовое слово длиной N цифр всегда будет иметь стоимость N , независимо от того, сколько из этих цифр равны 0, сколько единиц и т. д. При работе в этом предположении минимизация общей стоимости сообщения и минимизация общего количества цифр - одно и то же.
Кодирование Хаффмана с неравной стоимостью букв является обобщением без этого предположения: буквы алфавита кодирования могут иметь неодинаковую длину из-за характеристик среды передачи. Примером может служить алфавит кодирования кода Морзе , где «тире» требуется больше времени для отправки, чем «точка», и, следовательно, стоимость тире во времени передачи выше. Цель по-прежнему состоит в том, чтобы минимизировать средневзвешенную длину кодового слова, но уже недостаточно просто минимизировать количество символов, используемых в сообщении. Ни один алгоритм не известно решить эту проблему таким же образом , или с той же эффективностью , как и обычные кодирования Хаффмана, хотя она была решена Karp , решение которой был усовершенствован для случая целых затрат по Golin .
Оптимальные буквенные двоичные деревья (кодирование Ху – Таккера)
В стандартной задаче кодирования Хаффмана предполагается, что любое кодовое слово может соответствовать любому входному символу. В алфавитной версии алфавитный порядок входов и выходов должен быть идентичным. Так, например, не может быть присвоен код , но вместо этого следует назначить либо или же . Эта проблема также известна как проблема Ху – Таккера в честь Т.С. Ху и Алана Такера , авторов статьи, представляющей первую О ( п бревно п ) {\ Displaystyle О (п \ журнал п)} временное решение этой оптимальной двоичной алфавитной задачи [9], которая имеет некоторое сходство с алгоритмом Хаффмана, но не является разновидностью этого алгоритма. Более поздний метод, то алгоритм Garsia-Вахс из Адриано Гарсия и Мишель L. Wachs (1977), использует простую логику для выполнения того же сравнения в том же общее время , связанное. Эти оптимальные буквенные двоичные деревья часто используются в качестве двоичных деревьев поиска . [10]
Канонический код Хаффмана
Если веса, соответствующие алфавитно упорядоченным входным данным, расположены в числовом порядке, код Хаффмана имеет ту же длину, что и оптимальный буквенный код, который можно найти при вычислении этих длин, что делает кодирование Ху – Таккера ненужным. Код, полученный в результате числового (пере) упорядоченного ввода, иногда называют каноническим кодом Хаффмана и часто используется на практике из-за простоты кодирования / декодирования. Метод нахождения этого кода иногда называют кодированием Хаффмана – Шеннона – Фано , поскольку он оптимален, как кодирование Хаффмана, но имеет буквенное обозначение вероятности веса, как кодирование Шеннона – Фано . Код Хаффмана – Шеннона – Фано, соответствующий примеру, имеет вид, который, имея ту же длину кодового слова, что и исходное решение, также является оптимальным. Но в каноническом коде Хаффмана результат.
Приложения
Арифметическое кодирование и кодирование Хаффмана дают эквивалентные результаты - достижение энтропии - когда каждый символ имеет вероятность формы 1/2 k . В других обстоятельствах арифметическое кодирование может предложить лучшее сжатие, чем кодирование Хаффмана, потому что - интуитивно - его «кодовые слова» могут иметь фактически нецелую длину в битах, тогда как кодовые слова в префиксных кодах, таких как коды Хаффмана, могут иметь только целое число битов. Следовательно, кодовое слово длины k только оптимально соответствует символу с вероятностью 1/2 k, а другие вероятности не представлены оптимально; тогда как длина кодового слова при арифметическом кодировании может быть сделана так, чтобы точно соответствовать истинной вероятности символа. Эта разница особенно заметна для малых размеров алфавита.
Тем не менее префиксные коды по-прежнему широко используются из-за их простоты, высокой скорости и отсутствия патентной защиты . Они часто используются в качестве «основы» для других методов сжатия. Deflate ( алгоритм PKZIP ) и мультимедийные кодеки, такие как JPEG и MP3, имеют интерфейсную модель и квантование, за которым следует использование префиксных кодов; их часто называют «кодами Хаффмана», хотя в большинстве приложений используются заранее определенные коды переменной длины, а не коды, разработанные с использованием алгоритма Хаффмана.
Рекомендации
- ^ Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. DOI : 10.1109 / JRPROC.1952.273898 .
- ^ Ван Леувен, Ян (1976). «О построении деревьев Хаффмана» (PDF) . ICALP : 382-410 . Проверено 20 февраля 2014 .
- ^ Зэ-Нянь Ли; Марк С. Дрю; Цзянчуань Лю (2014-04-09). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8.
- ^ Дж. Дуда, К. Тахбуб, Н. Дж. Гадил, Э. Дж. Делп, Использование асимметричных систем счисления в качестве точной замены кодирования Хаффмана , Симпозиум по кодированию изображений, 2015.
- ^ Хаффман, Кен (1991). "Профиль: Дэвид А. Хаффман: Кодирование" аккуратности "единиц и нулей" . Scientific American : 54–58.
- ^ Грибов, Александр (2017-04-10). «Оптимальное сжатие полилинии с сегментами и дугами». arXiv : 1604.07476 [ cs.CG ].
- ^ Галлагер, Р.Г.; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». IEEE Transactions по теории информации . 21 (2): 228–230. DOI : 10.1109 / TIT.1975.1055357 .
- ^ Абрахамс, Дж. (1997-06-11). Написано в Арлингтоне, штат Вирджиния, США. Отдел математики, компьютерных и информационных наук Управления военно-морских исследований (ONR). «Код и деревья синтаксического анализа для кодирования исходного кода без потерь». Сжатие и сложность последовательностей Труды 1997 года . Салерно: IEEE : 145–171. CiteSeerX 10.1.1.589.4726 . DOI : 10,1109 / SEQUEN.1997.666911 . ISBN 0-8186-8132-2. S2CID 124587565 .
- ^ Ху, ТС; Такер, AC (1971). «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины». Журнал СИАМ по прикладной математике . 21 (4): 514. DOI : 10,1137 / 0121057 . JSTOR 2099603 .
- ^ Кнут, Дональд Э. (1998), "Алгоритм G (алгоритм Гарсиа-Вакса для оптимальных двоичных деревьев)", Искусство компьютерного программирования, Vol. 3: Сортировка и поиск (2-е изд.), Аддисон – Уэсли, стр. 451–453.. См. Также «История и библиография», стр. 453–454.
Библиография
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 16.3, стр. 385–392.
Внешние ссылки
- Кодирование Хаффмана на разных языках в Rosetta Code
- Коды Хаффмана (реализация на Python)
- Визуализация кодирования Хаффмана