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

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

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

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

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

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

Обзор

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

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

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

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

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

и

r=x-qM

.

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

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

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

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

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

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

.

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

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

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

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

Присвойте параметру M целочисленное значение.
Для N числа, которое нужно закодировать, найдите
1. частное = q = пол( N / M )
2. остаток = r = N по модулю M
Создать кодовое слово
1. Формат кода: <Код частного><Код остатка>, где
2. Частный код (в унарном кодировании )
  1. Запишите строку длиной q из 1 бита (или из 0 бит).
  2. Запишите 0 бит (соответственно 1 бит)
3. Код остатка (в усеченной двоичной кодировке )
  1. Позволять $b=\lfloor \log _{2}(M)\rfloor$ $b=\lfloor \log _ {2}(M)\rfloor$
    1. Если $r<2^{b+1}-M$ код r в двоичном представлении с использованием b бит.
    2. Если $r\geq 2^{b+1}-M$ закодируйте номер $r+2^{b+1}-M$ в двоичном представлении с использованием b + 1 бит.

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

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

Пример

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

Кодирование частной части
$д$	выходные биты
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110
$\vdots$	$\vdots$
Н	$\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$ и $1 - p$ в этом разделе поменяны местами по сравнению с использованием в предыдущих разделах.

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

См. также

Ссылки

^ Галлагер, Р.Г.; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». Транзакции IEEE по теории информации . 21 (2): 228–230. дои : 10.1109/тит.1975.1055357 .
^ Мерхав, Н.; Серусси, Г.; Вайнбергер, MJ (2000). «Кодирование источников с двусторонними геометрическими распределениями и неизвестными параметрами». Транзакции IEEE по теории информации . 46 (1): 229–236. дои : 10.1109/18.817520 .
^ Кили, А. (2004). Выбор параметра Голомба при кодировании Райса (технический отчет). Лаборатория реактивного движения . 42-159.
^ «Человек укорачивается» . Архивировано из оригинала 30 января 2014 г. Проверено 7 декабря 2008 г.
^ «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, Сан-Франциско, Калифорния. 1999 год ISBN 1-55860-570-3
Дэвид Саломон. «Сжатие данных», ISBN 0-387-95045-1 .
Х. С. Малвар, Адаптивное кодирование по длинам серий/Голомба – Райса квантованных обобщенных гауссовских источников с неизвестной статистикой , Proc. Конференция по сжатию данных, 2006 г.
Энтропийное кодирование RLGR , открытая спецификация Microsoft MS-RDPRFX, кодек RemoteFX для протокола удаленного рабочего стола.
С. Бютчер, CLA Кларк и Г. В. Кормак. Поиск информации: внедрение и оценка поисковых систем. Архивировано 5 октября 2020 г. в Wayback Machine . MIT Press, Кембридж, Массачусетс, 2010.

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

[1]

[2]

[3]

[4]

[5]