Арифметическое кодирование: точный интервал и двоичный префикс
Закодировать короткое сообщение с заданными положительными весами символов, сохранив точные границы и выбрав содержащийся двоичный интервал.
Ваш пример
Разбор примера
Двоичный префикс: 1001
| Символ | Низ | Верх |
|---|---|---|
| 2 | 1/2 | 1 |
| 0 | 1/2 | 5/8 |
| 2 | 9/16 | 5/8 |
- Итоговый полуоткрытый интервал: [9/16; 5/8).
- Двоичный интервал кода целиком содержится в итоговом; длина сообщения должна передаваться отдельно.
Метод и условия расчёта
Каждый символ сужает текущий полуоткрытый интервал по своей накопленной вероятности.
Ищем самый короткий двоичный цилиндр [k/2ᵇ,(k+1)/2ᵇ), целиком лежащий в итоговом интервале.
Теория к методу
Арифметическое кодирование последовательно сужает интервал по накопленным вероятностям символов. Для передачи выбирают двоичный префикс, весь интервал продолжений которого лежит внутри итогового интервала сообщения. Модель и правило завершения передаются отдельно.
Закрепите порядок алфавита и положительные веса его символов. Нормировка превращает веса в вероятности, а накопленные суммы разбивают [0,1) на непересекающиеся части. При очередном символе это же разбиение масштабируется на текущий интервал. Новые границы вычисляются по старой ширине; последовательное изменение одной границы до расчёта другой было бы ошибкой.
Пример: У символов 0,1,2 веса 1,1,2. Сообщение 2,0,2 сужает интервал до [9/16,5/8). Префикс 1001 задаёт [9/16,10/16), то есть ровно этот итоговый интервал.
Ширина равна 1/16 и отдельно проверяется произведением 1/2·1/4·1/2. Четыре бита описывают интервал, но сведения о модели и трёх символах длины в эту цифру не включены.
Вопросы по теме
Нужно передавать длину сообщения?
Да, либо специальный символ конца. Сам интервал не определяет произвольную длину сообщения без дополнительной договорённости.
Логические биты — готовый архив?
Нет. Не включены описание модели, длина, формат контейнера и упаковка.
Кодирование чисел, текста, изображения и звука: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.