Арифметическое кодирование: точный интервал и двоичный префикс

Закодировать короткое сообщение с заданными положительными весами символов, сохранив точные границы и выбрав содержащийся двоичный интервал.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Двоичный префикс: 1001

Проверяемые промежуточные данные
СимволНизВерх
21/21
01/25/8
29/165/8
  1. Итоговый полуоткрытый интервал: [9/16; 5/8).
  2. Двоичный интервал кода целиком содержится в итоговом; длина сообщения должна передаваться отдельно.

Метод и условия расчёта

Каждый символ сужает текущий полуоткрытый интервал по своей накопленной вероятности.

Ищем самый короткий двоичный цилиндр [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. По ссылкам можно сверить определения и условия модели.