Кодирование Голомба

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

Кодирование риса [ править ]

Кодирование Райса (изобретенное Робертом Ф. Райсом ) означает использование подмножества семейства кодов Голомба для создания более простого (но, возможно, субоптимального) префиксного кода. Райс использовал этот набор кодов в адаптивной схеме кодирования ; «Кодирование Райса» может относиться либо к этой адаптивной схеме, либо к использованию этого подмножества кодов Голомба. В то время как код Голомба имеет настраиваемый параметр, который может быть любым положительным целым числом, коды Райса - это те, в которых настраиваемый параметр является степенью двойки. Это делает коды Райса удобными для использования на компьютере, поскольку умножение и деление на 2 можно более эффективно реализовать в двоичной арифметике .

Райс был мотивирован предложить это более простое подмножество из-за того, что геометрические распределения часто меняются со временем, точно не известны или и того, и другого, поэтому выбор кажущегося оптимальным кода может быть не очень выгодным.

Кодирование Райса используется в качестве этапа энтропийного кодирования в ряде методов сжатия изображений без потерь и аудиоданных .

Обзор [ править ]

Построение кодов [ править ]

Кодирование Голомба использует настраиваемый параметр для разделения входного значения на две части: результат деления на и остаток. Частное передается в унарном кодировании , а остаток - в усеченном двоичном кодировании . Когда кодирование Голомба эквивалентно унарному кодированию.${\ displaystyle M}$${\ displaystyle N}$${\ displaystyle q}$${\ displaystyle M}$${\ displaystyle r}$${\ displaystyle M = 1}$

Коды Голомба – Райса можно рассматривать как коды, указывающие число по положению ячейки ( q ) и смещению внутри ячейки ( r ). На рисунке выше показано положение Q и смещение г для кодирования целого числа N , используя Голомбу-Райс параметр M .

Формально две части задаются следующим выражением, где - кодируемое число:${\ displaystyle x}$

${\ displaystyle q = \ left \ lfloor {\ frac {\ left (x-1 \ right)} {M}} \ right \ rfloor}$

и

${\ Displaystyle г = х-1-qM}$.

Окончательный результат выглядит следующим образом : .${\ Displaystyle \ влево (д + 1 \ вправо) г}$

Это изображение показывает избыточность кода Голомба, когда M выбирается оптимально для p  ≥ 1/2.

Обратите внимание, что это может быть разное количество бит. В частности, это только b бит для кода Райса и переключение между b -1 и b битами для кода Голомба (т. Е. M не является степенью 2). Пусть . Если , то используйте биты b -1 для кодирования r . Если , то используйте биты b для кодирования r . Ясно, что если M - степень двойки, и мы можем кодировать все значения r с помощью b битов.${\ displaystyle r}$${\ displaystyle r}$${\ Displaystyle B = \ lceil \ log _ {2} (M) \ rceil}$${\ displaystyle 0 \ leq r <2 ^ {b} -M}$${\ displaystyle 2 ^ {b} -M \ leq r <M}$${\ displaystyle b = \ log _ {2} (M)}$

Параметр M является функцией соответствующего процесса Бернулли , который параметризуется вероятностью успеха в данном испытании Бернулли . является либо медианой распределения, либо медианой +/− 1. Его можно определить с помощью следующих неравенств:${\ displaystyle p = P (X = 0)}$${\ displaystyle M}$

${\ Displaystyle (1-p) ^ {M} + (1-p) ^ {M + 1} \ leq 1 <(1-p) ^ {M-1} + (1-p) ^ {M}, }$

которые решаются

${\ displaystyle M = \ left \ lceil - {\ frac {\ log (2-p)} {\ log (1-p)}} \ right \ rceil}$.

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

Использовать с целыми числами со знаком [ править ]

Схема Голомба была разработана для кодирования последовательностей неотрицательных чисел. Однако его легко расширить, чтобы принимать последовательности, содержащие отрицательные числа, используя схему перекрытия и чередования , в которой все значения переназначаются на некоторое положительное число уникальным и обратимым способом. Последовательность начинается: 0, -1, 1, -2, 2, -3, 3, -4, 4 ... n- ^е отрицательное значение (т.е. -n) отображается на n- ^е нечетное число (2n- 1), а m- ^е положительное значение отображается на m- ^е четное число (2m). Математически это можно выразить следующим образом: положительное значение отображается в ( ), а отрицательное значение отображается в (${\ displaystyle x}$${\ displaystyle x ^ {\ prime} = 2 | x | = 2x, x \ geq 0}$${\ displaystyle y}$${\ displaystyle y ^ {\ prime} = 2 | y | -1 = -2y-1, y <0}$). Такой код можно использовать для простоты, даже если он неоптимален. Истинно оптимальные коды для двусторонних геометрических распределений включают несколько вариантов кода Голомба, в зависимости от параметров распределения, включая этот. ^[2]

Простой алгоритм [ править ]

Обратите внимание, что это кодирование Райса – Голомба, где в остаточном коде используется простое усеченное двоичное кодирование, также называемое «кодированием Райса» (другие двоичные кодировки переменной длины, такие как арифметические или Хаффмана, возможны для остальных кодов, если статистическое распределение кодов остатка не является плоским, особенно когда используются не все возможные остатки после деления). В этом алгоритме, если параметр M является степенью 2, он становится эквивалентным более простому кодированию Райса.

1. Установите для параметра M целочисленное значение.
2. Для N , числа, которое нужно закодировать, найдите
   1. частное = q = int [ N / M ]
   2. остаток = r = N по модулю M
3. Создать кодовое слово
   1. Формат кода: <Quotient Code> <Remainder Code>, где
   2. Факторный код (в унарном кодировании )
      1. Напишите строку длиной q из 1 бит (альтернативно из 0 бит)
      2. Записать 0 бит (соответственно 1 бит)
   3. Остаточный код (в усеченной двоичной кодировке )
      1. ПОЗВОЛЯТЬ ${\ Displaystyle b = \ lfloor \ log _ {2} (M) \ rfloor}$
         1. Если код r в двоичном представлении с использованием b битов.${\ displaystyle r <2 ^ {b + 1} -M}$
         2. Если кодировать число в двоичном представлении, используя b + 1 бит.${\ displaystyle r \ geq 2 ^ {b + 1} -M}$${\displaystyle r+2^{b+1}-M}$

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

Положим M = 10. Итак . Отсечка${\displaystyle b=\lceil \log _{2}(10)\rceil =4}$${\displaystyle 2^{b}-M=16-10=6}$

Кодирование частной части q выходные биты 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 ${\displaystyle \vdots }$ ${\displaystyle \vdots }$ N ${\displaystyle \underbrace {111\cdots 111} _{N}0}$

Кодирование остальной части р компенсировать двоичный выходные биты 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

Например, при кодировании Райса – Голомба параметра M = 10 десятичное число 42 сначала будет разделено на q = 4, r = 2 и будет закодировано как qcode ( q ), rcode ( r ) = qcode (4 ), rcode (2) = 11110,010 (вам не нужно кодировать разделяющую запятую в выходном потоке, потому что 0 в конце кода q достаточно, чтобы сказать, когда q заканчивается, а r начинается; оба qcode и rcode имеют самостоятельные границы).

Использовать для кодирования длин серий [ править ]

Учитывая алфавит из двух символов или набор из двух событий, P и Q , с вероятностями p и (1 -  p ) соответственно, где p  ≥ 1/2, кодирование Голомба может использоваться для кодирования серий из нуля или более P ' ы разделены одиночными Q «с. В этом приложении наилучшей настройкой параметра M является ближайшее целое число к . Когда p = 1/2, M = 1 и код Голомба соответствует унарному ( n  ≥ 0 P, за которым следует Q , кодируется как n${\displaystyle {\frac {-1}{\log _{2}p}}}$единицы, за которыми следует ноль). Если требуется более простой код, можно присвоить параметр Голомба-Райса (т. Е. Параметр Голомба ) ближайшему к нему целому числу ; хотя это не всегда лучший параметр, обычно это лучший параметр Райса, и его эффективность сжатия довольно близка к оптимальному коду Голомба. (Сам Райс предложил использовать различные коды для одних и тех же данных, чтобы выяснить, какой из них лучше. Более поздний исследователь JPL предложил различные методы оптимизации или оценки параметра кода. ^[3] )${\displaystyle b}$${\displaystyle M=2^{b}}$${\displaystyle -\log _{2}(-\log _{2}p)}$

Рассмотрите возможность использования кода Райса с двоичной частью, имеющей биты для последовательностей кодирования длин серий, где P имеет вероятность . Если вероятность того, что бит будет частью серии битов ( P s и один Q ), и степень сжатия этой серии, то ожидаемая степень сжатия будет${\displaystyle b}$${\displaystyle p}$${\displaystyle \mathbb {P} [\mathbf {bit~is~part~of~} k\mathbf {-run} ]}$${\displaystyle k}$${\displaystyle k-1}$ ${\displaystyle (\mathbf {compression~ratio~of~} k\mathbf {-run} )}$${\displaystyle {\begin{aligned}\mathbb {E} [\mathbf {compression~ratio} ]&=\sum _{k=1}^{\infty }(\mathbf {compression~ratio~of~} k\mathbf {-run} )\cdot \mathbb {P} [\mathbf {bit~is~part~of~} k\mathbf {-run} ]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}}$

Сжатие часто выражается в пропорции сжатого. Для подхода кодирования длин серий приводит к степени сжатия, близкой к энтропии . Например, использование кода Райса для сжатия дает сжатие, а предел энтропии равен .${\displaystyle 1-\mathbb {E} [\mathbf {compression~ratio} ]}$${\displaystyle p\approx 1}$${\displaystyle b=6}$${\displaystyle p=0.99}$${\displaystyle 91.89\%}$${\displaystyle 91.92\%}$

Адаптивное кодирование длин серий Голомба-Райса [ править ]

Когда распределение вероятностей для целых чисел неизвестно, оптимальный параметр для кодировщика Голомба-Райса не может быть определен. Таким образом, во многих приложениях используется двухпроходный подход: сначала блок данных сканируется для оценки функции плотности вероятности (PDF) для данных. Затем из этой оцененной PDF определяется параметр Голомба-Райса. Более простой вариант этого подхода - предположить, что PDF принадлежит параметризованному семейству, оценить параметры PDF на основе данных, а затем определить вычисление оптимального параметра Голомба-Райса. Этот подход используется в большинстве приложений, обсуждаемых ниже.

Альтернативный подход к эффективному кодированию целочисленных данных, PDF которых неизвестен или изменяется, заключается в использовании обратно адаптивного кодировщика. Метод Голомба-Райса (RLGR) достигает этого с помощью очень простого алгоритма, который регулирует параметр Голомба-Райса вверх или вниз, в зависимости от последнего кодированного символа. Декодер может следовать тому же правилу, чтобы отслеживать изменение параметров кодирования, поэтому не нужно передавать дополнительную информацию, а только закодированные данные. Предполагая, что обобщенный гауссовский PDF, который охватывает широкий диапазон статистических данных, наблюдаемых в данных, таких как ошибки предсказания или коэффициенты преобразования в мультимедийных кодеках, алгоритм кодирования RLGR может очень хорошо работать в таких приложениях.

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

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

Некоторые аудиокодеки без потерь , такие как Shorten , ^[4] FLAC , ^[5] Apple Lossless и MPEG-4 ALS , используют код Райса после шага линейного прогнозирования (называемого «адаптивным FIR-фильтром» в Apple Lossless). Кодирование Райса также используется в кодеке изображений без потерь FELICS .

Кодер Голомба – Райса используется на этапе энтропийного кодирования кодеков изображений без потерь, основанных на алгоритме Райса . Один из таких экспериментов дает график степени сжатия, приведенный ниже. Смотрите другие записи в этой категории внизу этой страницы. При таком сжатии данные прогрессивной пространственной разницы дают чередующийся набор положительных и отрицательных значений около 0, которые преобразуются в только положительные целые числа (путем удвоения абсолютного значения и добавления единицы, если входной сигнал отрицательный), а затем Райса – Голомба кодирование применяется путем изменения делителя, который остается малым. ^{[ необходима цитата ]}

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

Схема JPEG-LS использует Райса – Голомба для кодирования остатков предсказания.

Упомянутая выше адаптивная версия кодирования Голомба-Райса (RLGR) длиной прогона используется для кодирования содержимого экрана в виртуальных машинах в компоненте RemoteFX протокола удаленного рабочего стола Microsoft.

См. Также [ править ]

• Дельта (δ) код Элиаса

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

Дальнейшее чтение [ править ]

• Голомб, Соломон В. (1966). Кодировки длин серий. IEEE Transactions по теории информации, ИТ - 12 (3): 399-401
• Райс, Роберт Ф .; Plaunt, R. (1971). «Адаптивное кодирование переменной длины для эффективного сжатия телевизионных данных космических аппаратов». IEEE Transactions on Communications . 16 (9): 889–897. DOI : 10.1109 / TCOM.1971.1090789 .
• Роберт Ф. Райс (1979), «Некоторые практические универсальные методы бесшумного кодирования», Лаборатория реактивного движения, Пасадена, Калифорния, JPL Publication 79-22, март 1979 года.
• Виттен, Ян Моффат, Алистер Белл, Тимоти. «Управление гигабайтами: сжатие и индексирование документов и изображений». Второе издание. Издательство Morgan Kaufmann Publishers, Сан-Франциско, Калифорния. 1999 ISBN 1-55860-570-3 
• Дэвид Саломон. «Сжатие данных», ISBN 0-387-95045-1 . 
• HS Malvar, Адаптивное кодирование длин серий / Голомба-Райса квантованных обобщенных гауссовских источников с неизвестной статистикой , Proc. Конференция по сжатию данных, 2006 г.
• Кодирование энтропии RLGR, открытая спецификация Microsoft MS-RDPRFX, кодек RemoteFX для протокола удаленного рабочего стола.
• С. Бюттчер, Кларк Кларк и Г.В. Кормак. Поиск информации: внедрение и оценка поисковых систем . MIT Press, Кембридж, Массачусетс, 2010.

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

• веб-страница с коротко проработанным примером кодирования и декодирования Голомба.