Пытаясь понять взаимосвязи между кодированием Хаффмана, арифметическим кодированием и дистанционным кодированием, я начал думать о недостатках кодирования Хаффмана, связанных с проблемой дробной битовой упаковки .
То есть, предположим, что у вас есть 240 возможных значений для символа, и вам необходимо закодировать его в биты, вы застряли бы с 8 битами на символ, даже если вам не нужно "полное" 8, так как 8 может выразить 256 возможных значений за символ Решение этой проблемы - это то, что я видел как «дробная битовая упаковка», где вы можете «сдвигать биты» без умножения на два, используя умножение. Подобно тому, как умножение степеней двух сдвигается x * 2 == x << 1
и x * 4 == x << 2
так далее для всех степеней двойки, вы также можете «сдвигать» с не степенью 2, умножая взамен, и упаковывать в символы дробных битов ,
Проблема схожа с кодированием Хаффмана: в конечном итоге вы получите коды, длина которых должна быть не дробно-битной, и, следовательно, она имеет такую неэффективность упаковки. Тем не менее, вы не можете просто использовать решение fracitonal-битовой упаковки, потому что это решение предполагает символы фиксированного размера.
Вопрос заключается в том, существуют ли какие-либо документы или решения для улучшения кодирования Хаффмана с аналогичной идеей дробной битовой упаковки для достижения чего-то похожего на арифметическое кодирование? (или любые результаты наоборот).
Ответы:
Давайте посмотрим на немного другой способ мышления о кодировании Хаффмана.
Предположим, у вас есть алфавит из трех символов, A, B и C, с вероятностями 0,5, 0,25 и 0,25. Поскольку вероятности - все обратные степени двойки, у этого есть код Хаффмана, который является оптимальным (то есть это идентично арифметическому кодированию). Мы будем использовать канонический код 0, 10, 11 для этого примера.
Предположим, что наше состояние - большое целое число, которое мы будем называть . Вы можете думать о кодировании как о функции, которая принимает текущее состояние и символ для кодирования и возвращает новое состояние:s
Итак, давайте начнем с состояния 11 (которое 1011 в двоичном виде), закодируем символ B. Новое состояние 46, что в 101110 двоично. Как видите, это «старое» состояние с добавленной в конец последовательностью 10. По сути, мы «вывели» битовую последовательность 10.
Все идет нормально.
Теперь немного подумайте о том, как работает арифметическое кодирование. Если вы положите вероятности над общим знаменателем, символ A фактически представляет диапазон символ B представляет диапазон[2[ 04, 24) и символ C представляет диапазон[3[ 24, 34) .[ 34, 44)
По сути, мы здесь умножаем все на общий знаменатель. Представьте, что состояние фактически было в базе 4. Кодирование символа B действительно выводит цифру 2 в этой базе, а кодирование символа C выводит цифру 3 в этой базе.
Тем не менее, символ A немного отличается, потому что это не целая цифра в базе 4.
Вместо этого мы можем думать об алфавите как о множестве символов A_0, A_1, B, C с равной вероятностью. Это, опять же, имеет оптимальный код Хаффмана 00, 01, 10, 11. Или, опять же, мы можем думать об этом в базе 4. Чтобы кодировать символ, мы просто делаем:
а затем .encode(s′,Ai)
Используя наш предыдущий пример, , мы находим, что и , а затем . Новое состояние - 10101 в двоичном виде.s=11 s′=5 i=1 encode(5,A1)=4×5+1=21
Теперь это не дает точно такой же битовый вывод, как при кодировании Хаффмана, но он генерирует вывод такой же длины. И я надеюсь, что вы можете видеть, что это также уникально декодируемый. Чтобы декодировать символ, мы берем остаток от деления на 4. Если значение равно 2 или 3, то символ B или C соответственно. Если это 0 или 1, то символом является A, а затем мы можем вернуть бит информации, умножив состояние на 2 и добавив либо 0, либо 1.
Приятной особенностью этого подхода является то, что он естественным образом распространяется на дробно-битовое кодирование, когда числитель и / или знаменатель вероятностей не являются степенями двух. Предположим, у нас есть два символа, A и B, где вероятность A равна а вероятность B равна . Тогда мы можем закодировать символ с помощью:35 25
Для кодирования символа A мы берем и , а затем .i=smod3кодировать(s′,Ai)s′=⌊s3⌋ i=smod3 encode(s′,Ai)
Это эквивалентно арифметическому кодированию. На самом деле это семейство методов, известных как асимметричные системы счисления , и было разработано за последние несколько лет Яреком Дудой. Значение имени должно быть очевидным: чтобы кодировать символ с вероятностью , вы концептуально крадете цифру base-p из состояния, а затем добавляете цифру base-q. Асимметрия возникает из-за интерпретации состояния как числа в двух разных основах.pq
Причина, по которой это семейство методов кодирования, заключается в том, что то, что мы видели здесь, само по себе нецелесообразно; необходимо несколько модификаций, чтобы учесть тот факт, что у вас, вероятно, нет целых чисел с бесконечной точностью, чтобы эффективно манипулировать переменной состояния, и существуют различные способы, которыми вы можете достичь этого. Конечно, у арифметического кодирования есть аналогичная проблема с точностью для его состояния.
Практические варианты включают RANS («r» означает «соотношение») и tANS («управляемый таблицей»).
У ANS есть несколько интересных преимуществ перед арифметическим кодированием, как практическим, так и теоретическим:
Я не думаю, что когда-нибудь снова буду заниматься арифметическим кодированием.
источник
В качестве простого примера, если бы у вас было три символа с вероятностью 1/3 каждый, оптимальное кодирование Хаффмана будет использовать три символа 0, 10 и 11 со средним значением 5/3-го бита.
Существует 243 символа, созданных путем объединения 5 исходных символов, каждый с вероятностью 1/243. Что намного ближе к 1/256. Оптимальное кодирование Хаффмана будет кодировать 13 из этих групп в 7 битах и 230 групп в 8 битах, в среднем 7,9465 битов на группу или 1,5893 битов на исходный символ, по сравнению с 1,6667 битов для исходного кодирования Хаффмана, а арифметическое кодирование занимает 1,5850. биты.
Таким образом, теоретически вы можете просто объединить два символа каждый в один больший символ или три символа каждый в один больший символ и использовать кодирование Хафмана для комбинаций.
источник