Я не получаю кодирование Голомба / Райса: оно делает больше битов ввода или нет?

Question

Или, может быть, я не получаю унарное кодирование :

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

В википедии пример они используют 42 как N и 10 как M, поэтому мы получаем коэффициент q из 4 (в унарном виде: 1110) и остаток r из 2 (в двоичном 010), так что результирующее сообщение будет 1110,010, или 8 бит (запятая может быть пропущена). Простое двоичное представление 42 равно 101010 или 6 битам.

Мне кажется, это связано с унарным представлением q, которое всегда должно быть больше битов, чем двоичное.

Очевидно, я упускаю здесь важный момент. Что это?

Answer 1

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

Например, если вы должны были передавать целые числа в диапазоне от 0 до 1000, но подавляющее большинство фактических значений было в диапазоне от 0 до 10, в кодировке с фиксированной шириной, большинство передаваемых кодов будет иметь начальные 0, которые не содержат информации:

Чтобы охватить все значения от 0 до 1000, вам необходимо 10-битное кодирование в двоичном коде с фиксированной шириной. Теперь, поскольку большинство ваших значений будет меньше 10, по крайней мере, первые 6 битов большинства чисел будут равны 0 и будут содержать мало информации.

Чтобы исправить это с помощью кодов Голомба, вы делите числа, деля их на 10 и кодируя частное и остальное отдельно. Для большинства значений все, что должно быть передано, - это остаток, который может быть закодирован с использованием максимум 4 битов (если вы используете усеченный двоичный код для остатка, он может быть меньше). Затем частное передается в унарном формате, который кодируется как один 0 бит для всех значений ниже 10, как 10 для 10..19, 110 для 20..29 и т. Д.

Теперь для большинства ваших значений вы уменьшили размер сообщения до 5 бит максимум, но вы все равно можете передавать все значения однозначно без разделителей.

Это связано с довольно высокой стоимостью для больших значений (например, значения в диапазоне 990..999 требуют 100 бит для частного), поэтому кодирование является оптимальным для двусторонних геометрических распределений.

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

Answer 2

Одно из различий между кодированием Голомба и двоичным кодом состоит в том, что двоичный код не является префиксным кодом, который не допускается для кодирования строк произвольно больших чисел (вы не можете решить, является ли 1010101010101010 конкатенацией 10101010 и 10101010 или чем-то другим еще). Следовательно, они не так легко сопоставимы.

Во-вторых, код Голомба оптимален для геометрического распределения, в данном случае с параметром 2 ^ (- 1/10). Вероятность 42 составляет около 0,3%, поэтому вы получите представление о том, насколько это важно для длины выходной строки.