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

Метод сжатия данных без потерь

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

Кодирование риса

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

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

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

Обзор

Пример кодирования Голомба для источника x с геометрическим распределением, с параметром p (0) = 0,2 , с использованием кода Голомба с M = 3 . 2-битный код 00 используется в 20% случаев; 3-битные коды 010, 011 и 100 используются более 38% времени; 4 бита и более необходимы в меньшинстве случаев. Для этого источника энтропия = 3,610 бит; для этого кода с этим источником скорость = 3,639 бит; следовательно, избыточность = 0,030 бит или эффективность = 0,992 бит на бит.

Построение кодов

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

Коды Голомба-Райса можно рассматривать как коды, которые указывают число по положению ячейки ( q ) и смещению внутри ячейки ( r ). На рисунке в качестве примера показаны позиция q и смещение r для кодирования целого числа x с использованием параметра Голомба-Райса M = 3 с вероятностями источника, следующими за геометрическим распределением с p (0) = 0,2 .

Формально эти две части задаются следующим выражением, где x — кодируемое неотрицательное целое число:

${\displaystyle q=\left\lfloor {\frac {x}{M}}\right\rfloor }$

и

${\displaystyle r=x-qM}$.

На этом изображении показана избыточность кода Голомба в битах при оптимальном выборе M для 1 − p (0) ≥ 0,45.

И q , и r будут закодированы с использованием переменного числа битов: q - унарным кодом, а r - b битами для кода Райса или выбором между b и b +1 битами для кода Голомба (т. е. M не является степенью 2) . ), с . Если , то используйте b бит для кодирования r ; в противном случае используйте b +1 бит для кодирования r . Очевидно, что если M — степень двойки и мы можем закодировать все значения r b битами. ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$ ${\displaystyle r<2^{b+1}-M}$ ${\displaystyle b=\log _{2}(M)}$

Целое число x , рассматриваемое Голомбом, было длиной прогона процесса Бернулли , который имеет геометрическое распределение, начинающееся с 0. Лучший выбор параметра M - это функция соответствующего процесса Бернулли, который параметризуется вероятностью успеха в данном Суд Бернулли . M — это либо медиана распределения, либо медиана ±1. Его можно определить с помощью неравенств: ${\displaystyle p=P(x=0)}$

${\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 }$.

Для примера с p (0) = 0,2 :

${\displaystyle M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3}$.

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

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

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

Простой алгоритм

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

1. Присвойте параметру M целочисленное значение.
2. Для N числа, которое нужно закодировать, найдите
   1. частное = q = пол( N / M )
   2. остаток = r = N по модулю M
3. Создать кодовое слово
   1. Формат кода: <Код частного><Код остатка>, где
   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}$

Расшифровка:

1. Декодируйте унарное представление q (подсчитайте число 1 в начале кода)
2. Пропустить разделитель 0
3. Позволять ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
   1. Интерпретируйте следующие b бит как двоичное число r' . Если держится, то напоминание ${\displaystyle r'<2^{b+1}-M}$ ${\displaystyle r=r'}$
   2. В противном случае интерпретируйте b + 1 бит как двоичное число r' , напоминание будет выглядеть так: ${\displaystyle r=r'-2^{b+1}+M}$
4. Вычислить ${\displaystyle N=q*M+r}$

Пример

Установите М = 10 . Таким образом . Отрезок есть . ${\displaystyle b=\lfloor \log _{2}(10)\rfloor =3}$ ${\displaystyle 2^{b+1}-M=16-10=6}$

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

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

Обратите внимание, что p и 1 – p в этом разделе поменяны местами по сравнению с использованием в предыдущих разделах.

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

Рассмотрите возможность использования кода Райса с двоичной частью, имеющей b бит, для кодирования последовательностей серий, где P имеет вероятность p . Если - вероятность того, что бит будет частью k -битной серии ( P s и один Q ), и - степень сжатия этой серии, то ожидаемая степень сжатия равна ${\displaystyle \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]}$ ${\displaystyle k-1}$ ${\displaystyle ({\text{compression ratio of }}k{\text{-run}})}$

${\displaystyle {\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-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} [{\text{compression ratio}}]}$ ${\displaystyle p\approx 1}$ ${\displaystyle b=6}$ ${\displaystyle p=0.99}$Сжатие 91,89% , а предел энтропии равен91,92% .

Адаптивное кодирование Голомба – Райса

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

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

Приложения

Эксперимент по коэффициентам сжатия алгоритма Райса, закодированного Голомбом

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

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

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

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

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

Смотрите также

• Дельта-кодирование Элиаса
• Код переменной длины

Рекомендации

1. Галлагер, Р.Г.; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». Транзакции IEEE по теории информации . 21 (2): 228–230. дои : 10.1109/тит.1975.1055357.
2. Мерхав, Н.; Серусси, Г.; Вайнбергер, MJ (2000). «Кодирование источников с двусторонними геометрическими распределениями и неизвестными параметрами». Транзакции IEEE по теории информации . 46 (1): 229–236. дои : 10.1109/18.817520.
3. Кили, А. (2004). Выбор параметра Голомба при кодировании Райса (технический отчет). Лаборатория реактивного движения . 42-159.
4. "Человек сокращается" . Архивировано из оригинала 30 января 2014 г. Проверено 7 декабря 2008 г.
5. «FLAC — Обзор формата» . xiph.org .

дальнейшее чтение

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