> rice | адаптивное | сжатие <
// Кодирование Rice — адаптивное сжатие целых чисел с настраиваемым параметром
>> возможности
Настраиваемый параметр
Настраивайте k, чтобы оптимизировать сжатие для разных распределений данных.
Геометрические данные
Оптимально для данных с геометрическим или экспоненциальным распределением.
Быстрое кодирование
Простые операции деления и остатка обеспечивают высокую скорость.
>> техническая информация
Как работает кодирование Rice:
Кодирование Rice делит каждое целое число n на 2^k, получая частное q и остаток r. Частное кодируется унарно (q единиц, за которыми следует ноль), а остаток — в k двоичных битах. Это создаёт код переменной длины, который адаптируется к распределению данных через параметр k.
Пример кодирования Rice (k=2):
k=2, M=2^2=4 0 → q=0, r=0 → 0|00 → 000 1 → q=0, r=1 → 0|01 → 001 2 → q=0, r=2 → 0|10 → 010 3 → q=0, r=3 → 0|11 → 011 4 → q=1, r=0 → 10|00 → 1000 5 → q=1, r=1 → 10|01 → 1001 6 → q=1, r=2 → 10|10 → 1010 7 → q=1, r=3 → 10|11 → 1011 8 → q=2, r=0 → 110|00 → 11000 Большее k: меньше унарных бит, больше двоичных Меньшее k: больше унарных бит, меньше двоичных
Зачем использовать кодирование Rice?:
- ▸Адаптируется к распределению данных
- ▸Простая реализация
- ▸Быстрое кодирование и декодирование
- ▸Подходит для данных датчиков
- ▸Эффективно для малых целых чисел
>> часто задаваемые вопросы
Что такое кодирование Rice?
Кодирование Rice — это метод энтропийного кодирования переменной длины, особенно эффективный для геометрических распределений. Это частный случай кодирования Голомба, где делитель M ограничен степенями двойки (M = 2^k), что позволяет использовать быстрые реализации на основе побитовых операций.
Как выбрать параметр k?
Оптимальное значение k зависит от распределения данных. Для данных со средним значением μ приблизительно выполняется k ≈ log₂(μ × ln(2)). Малые значения k (0–2) хорошо подходят для очень малых чисел, а большие (4–8) лучше для данных с более крупными значениями. Используйте функцию анализа, чтобы подобрать оптимальное k для ваших данных.
Rice против кодирования Голомба?
Кодирование Rice — это подмножество кодирования Голомба, в котором M = 2^k. Такое ограничение делает Rice быстрее (сдвиги битов вместо деления), но иногда немного менее оптимальным. Голомб-кодирование позволяет выбирать произвольные значения M для лучшей компрессии, тогда как Rice жертвует частью эффективности ради скорости.
Где используется кодирование Rice?
Кодирование Rice широко применяется в без потерь сжатии аудио (FLAC, ALAC), сжатии изображений (JPEG-LS) и для данных датчиков с геометрическими распределениями. Особенно эффективно для малых неотрицательных целых чисел с экспоненциально убывающей вероятностью.
// Разобранный пример
| n | q | r | k=2 |
|---|---|---|---|
| 0 | 0 | 00 | 000 |
| 1 | 0 | 01 | 001 |
| 2 | 0 | 10 | 010 |
| 3 | 0 | 11 | 011 |
| 4 | 1 | 00 | 1000 |
| 5 | 1 | 01 | 1001 |
| 6 | 1 | 10 | 1010 |
| 7 | 1 | 11 | 1011 |
| 8 | 2 | 00 | 11000 |
// Примеры кода
Rice code with parameter k (Golomb code with M = 2^k) q = n >> k quotient, written as q ones followed by a zero r = n & (2^k - 1) remainder, written as k plain bits code = unary(q) + r k = 2, n = 9 -> q = 2, r = 01 -> 110 01 Decode: count the leading 1s (q), skip the 0, read k bits (r), n = (q << k) | r Choose k about log2(mean value): small values -> small k
>> Другие вопросы
В: Чем код Райса отличается от кода Голомба?
О: Код Райса — частный случай кода Голомба, где параметр M — степень двойки (M = 2^k). Сдвиг и маска заменяют деление, что очень быстро.
В: Как выбрать параметр k?
О: k должен быть примерно log2 от среднего значения. Слишком малый k даёт длинные унарные части, слишком большой тратит биты на остаток. Кодеки вроде FLAC выбирают k для каждого блока.
В: Для чего подходит код Райса?
О: Для неотрицательных целых с геометрическим распределением, где малые значения встречаются намного чаще. Типично — остатки предсказания в сжатии аудио без потерь (FLAC) и изображений (JPEG-LS).