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

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

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

История

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

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

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

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

Определение проблемы

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

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

Формализованное описание

Вход .
Алфавит $A=(a_{1},a_{2},\dots ,a_{n})$ , который является символом алфавита размера $n$ .
Кортеж $W=(w_{1},w_{2},\dots ,w_{n})$ , который представляет собой кортеж (положительных) весов символов (обычно пропорциональных вероятностям), т.е. $w_{i}=\operatorname {weight} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}$ .

Выход .
Код $C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})$ , который представляет собой кортеж (двоичных) кодовых слов, где $c_{i}$ это кодовое слово для $a_{i},\,i\in \{1,2,\dots ,n\}$ .

Цель .
Позволять ${\textstyle L\left(C\left(W\right)\right)=\sum _{i=1}^{n}{w_{i}\operatorname {length} \left(c_{i}\right)}}$ быть взвешенной длиной пути кода $C$ . Состояние: $L\left(C\left(W\right)\right)\leq L\left(T\left(W\right)\right)$ для любого кода $T\left(W\right)$ .

Пример

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

Вход ( А , Вт )	Символ ( $а я$ )	а	б	с	д	и	Сумма
Вход ( А , Вт )	Вес ( $w я$ )	0.10	0.15	0.30	0.16	0.29	= 1
Выход С	Кодовые слова ( $c я$ )	`010`	`011`	`11`	`00`	`10`
	Длина кодового слова (в битах) ( $я)$	3	3	2	2	2
	Вклад во взвешенную длину пути ( $л я$ $ш я$ )	0.30	0.45	0.60	0.32	0.58	Л ( С ) = 2,25
Оптимальность	Вероятностный бюджет ( $2 - я$ )	1/8	1/8	1/4	1/4	1/4	= 1.00
	Информационное содержание (в битах) ( $-log 2 ш я$ ) ≈	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	Ч ( А ) = 2,205

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

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

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

Энтропия (в битах H ) — это взвешенная сумма по всем символам $a i$ с ненулевой вероятностью $w i$ информационного содержания каждого символа:

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}}.

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

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

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

Основная техника

Сжатие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

Ссылки

^ Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. дои : 10.1109/JRPROC.1952.273898 .
^ Ван Леувен, Ян (1976). «О построении деревьев Хаффмана» (PDF) . ICALP : 382–410 . Проверено 20 февраля 2014 г.
^ Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .
^ Дж. Дуда, К. Тахбуб, Н. Дж. Гадил, Э. Дж. Дельп, Использование асимметричных систем счисления в качестве точной замены кодирования Хаффмана , Симпозиум по кодированию изображений, 2015.
^ Хаффман, Кен (1991). «Профиль: Дэвид А. Хаффман: Кодирование «аккуратности» единиц и нулей» . Научный Американ : 54–58.
^ Грибов, Александр (10 апреля 2017 г.). «Оптимальное сжатие полилинии с сегментами и дугами». arXiv : 1604.07476 [ cs.CG ].
^ Галлагер, Р.Г.; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». Транзакции IEEE по теории информации . 21 (2): 228–230. дои : 10.1109/TIT.1975.1055357 .
^ Абрахамс, Дж. (11 июня 1997 г.). «Деревья кода и синтаксического анализа для кодирования источника без потерь». Написано в Арлингтоне, штат Вирджиния, США. Слушания. Сжатие и сложность ПОСЛЕДОВАТЕЛЬНОСТЕЙ 1997 (Кат. № 97TB100171) . Отдел математики, компьютерных и информационных наук Управления военно-морских исследований (ONR). Салерно: IEEE . стр. 145–171. CiteSeerX 10.1.1.589.4726 . дои : 10.1109/SEQUEN.1997.666911 . ISBN 0-8186-8132-2 . S2CID 124587565 .
^ Ху, ТЦ ; Такер, AC (1971). «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины». SIAM Journal по прикладной математике . 21 (4): 514. дои : 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.

Внешние ссылки

[1] Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. дои : 10.1109/JRPROC.1952.273898 .

[2] Ван Леувен, Ян (1976). «О построении деревьев Хаффмана» (PDF) . ICALP : 382–410 . Проверено 20 февраля 2014 г.

[LiDrew2014-3] Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

[PCS2015-4] Дж. Дуда, К. Тахбуб, Н. Дж. Гадил, Э. Дж. Дельп, Использование асимметричных систем счисления в качестве точной замены кодирования Хаффмана , Симпозиум по кодированию изображений, 2015.

[5] Хаффман, Кен (1991). «Профиль: Дэвид А. Хаффман: Кодирование «аккуратности» единиц и нулей» . Научный Американ : 54–58.

[6] Грибов, Александр (10 апреля 2017 г.). «Оптимальное сжатие полилинии с сегментами и дугами». arXiv : 1604.07476 [ cs.CG ].

[7] Галлагер, Р.Г.; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». Транзакции IEEE по теории информации . 21 (2): 228–230. дои : 10.1109/TIT.1975.1055357 .

[8] Абрахамс, Дж. (11 июня 1997 г.). «Деревья кода и синтаксического анализа для кодирования источника без потерь». Написано в Арлингтоне, штат Вирджиния, США. Слушания. Сжатие и сложность ПОСЛЕДОВАТЕЛЬНОСТЕЙ 1997 (Кат. № 97TB100171) . Отдел математики, компьютерных и информационных наук Управления военно-морских исследований (ONR). Салерно: IEEE . стр. 145–171. CiteSeerX 10.1.1.589.4726 . дои : 10.1109/SEQUEN.1997.666911 . ISBN 0-8186-8132-2 . S2CID 124587565 .

[9] Ху, ТЦ ; Такер, AC (1971). «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины». SIAM Journal по прикладной математике . 21 (4): 514. дои : 10.1137/0121057 . JSTOR 2099603 .

[10] Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа – Вакса для оптимальных двоичных деревьев)», Искусство компьютерного программирования, Vol. 3: Сортировка и поиск (2-е изд.), Аддисон – Уэсли, стр. 451–453 . См. также «История и библиография», стр. 453–454.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Чар	Частота	Код
космос	7	111
а	4	010
и	4	000
ж	3	1101
час	2	1010
я	2	1000
м	2	0111
н	2	0010
с	2	1011
т	2	0110
л	1	11001
тот	1	00110
п	1	10011
р	1	11000
в	1	00111
х	1	10010

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