> golomb | оптимальное | сжатие <
// Кодирование Голомба – оптимальное сжатие целых чисел с гибким делителем
>> возможности
Гибкий делитель
Выбирайте любое значение M для максимальной эффективности сжатия.
Усечённый двоичный код
Использует минимальное количество бит для кодирования остатка.
Общее назначение
Работает с любым распределением неотрицательных целых чисел.
>> техническая информация
Как работает кодирование Голомба
При кодировании Голомба каждое целое число n делится на делитель M, получаются частное q и остаток r. Частное кодируется унарно, а остаток – усечённым двоичным кодом, который использует минимальное число бит для M возможных значений. Это создаёт оптимальный код для геометрических распределений с параметром p = 1/M.
Пример кодирования Голомба (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 бита для r<3) 1 → q=0, r=1 → 0|01 → 001 (2 бита для r<3) 2 → q=0, r=2 → 0|10 → 010 (2 бита для r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 бита для r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 бита для r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Усечённый двоичный код: r<3 использует 2 бита, r≥3 использует 3 бита
Зачем использовать кодирование Голомба
- Оптимально для геометрических распределений
- Гибкий параметр M
- Минимальное количество бит
- Простая реализация
- Доказанная оптимальность
>> часто задаваемые вопросы
Что такое кодирование Голомба?
Кодирование Голомба — это оптимальный, префикс‑свободный код переменной длины для геометрических распределений. Целые числа делятся с помощью настраиваемого параметра M, частное кодируется унарно, а остаток усечённым двоичным кодом, что обеспечивает оптимальное сжатие данных с P(n) = (1-p)^n × p.
Как выбрать параметр M?
Оптимальное M зависит от геометрического параметра p ваших данных. Для данных со средним значением μ приблизительно M ≈ μ + 1. Для экспоненциально убывающих вероятностей с параметром p оптимальное M равно ⌈-1/log₂(1-p)⌉. Используйте функцию анализа, чтобы подобрать лучшее M для ваших данных.
Что такое усечённое двоичное кодирование?
Усечённое двоичное кодирование минимизирует число бит при кодировании одного из M возможных значений. Если M — степень двойки, используется стандартный двоичный код. В противном случае часть значений использует ⌊log₂M⌋ бит, а часть — ⌈log₂M⌉ бит, обеспечивая однозначную декодировку при минимальной средней длине.
Где используется кодирование Голомба?
Кодирование Голомба применяется в сжатии изображений JPEG-LS, видеокодировании H.264 (как Exp-Golomb) и в lossless‑аудиоформатах. Оно идеально подходит для кодирования длин серий, остатков после предсказания и любых данных с геометрическими или экспоненциальными распределениями.