Информатика · объяснение и практика
Сообщение как вложенный интервал: что именно передают биты арифметического кода
Построить точный интервал арифметического кодирования короткого сообщения и найти целиком содержащийся в нём двоичный цилиндр.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта
Главная мысль
Арифметическое кодирование последовательно сужает интервал по накопленным вероятностям символов. Для передачи выбирают двоичный префикс, весь интервал продолжений которого лежит внутри итогового интервала сообщения. Модель и правило завершения передаются отдельно.
Метод и постановка
Закрепите порядок алфавита и положительные веса его символов. Нормировка превращает веса в вероятности, а накопленные суммы разбивают [0,1) на непересекающиеся части. При очередном символе это же разбиение масштабируется на текущий интервал. Новые границы вычисляются по старой ширине; последовательное изменение одной границы до расчёта другой было бы ошибкой.
Полуоткрытость нужна для однозначного выбора символа на общей границе соседних частей. В коротком учебном сообщении рациональная арифметика сохраняет эту договорённость точно. Длина итогового интервала равна произведению вероятностей введённых символов при фиксированной модели. Это независимая проверка последовательных сужений, хотя само произведение не сообщает положение интервала.
Проверка и границы вывода
Двоичный префикс длины b соответствует цилиндру [k/2^b,(k+1)/2^b). Недостаточно, чтобы одна точка k/2^b попала в интервал сообщения: другие продолжения тех же битов могут выйти наружу. Здесь требуется полное включение цилиндра. Самая короткая подходящая длина находится последовательной проверкой ограниченного числа разрядов.
Число битов этого префикса не является готовым размером архива. Декодеру нужны модель, порядок символов и длина сообщения либо специальный символ конца. Без завершения код короткого сообщения может также описывать начало более длинного. При очень неравных весах даже двадцать символов могут потребовать слишком много точных разрядов; ограничение вычисления нужно понимать как границу учебного инструмента, а не как доказательство невозможности сжатия.
Перед сравнением длин проверьте один и тот же порядок алфавита. Перестановка символов сохраняет произведение вероятностей и ширину интервала, но меняет его положение и полученные биты. Поэтому совпадающая длина не подтверждает совместимость двух кодеров; нужен также общий накопленный порядок символов.
Пример
У символов 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. Четыре бита описывают интервал, но сведения о модели и трёх символах длины в эту цифру не включены.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно передавать длину сообщения?
Да, либо специальный символ конца. Сам интервал не определяет произвольную длину сообщения без дополнительной договорённости.
Логические биты — готовый архив?
Нет. Не включены описание модели, длина, формат контейнера и упаковка.
Углублённый разбор
Завершение арифметического кода и длина сообщения
Символ конца превращает модель потока в модель конечных сообщений. Его интервал тоже кодируется, поэтому остановка декодера становится частью вероятностной спецификации и имеет собственную цену.
Перед началом: Арифметический интервал; Условие завершения.
Конец сообщения должен иметь положительную долю модели
Добавим специальный символ#с вероятностью q>0, не являющийся обычными данными. Кодер после последнего символа данных кодирует#по той же модели и останавливается. Декодер извлекает символы до первого#;знание длины исходного текста ему тогда не требуется, но модель и точный алфавит всё равно должны совпадать.
Интервал завершённого сообщения включает вклад#в своё сужение. Нельзя просто вывести условный значок конца рядом с кодом, оставив арифметическую вероятность прежней. Если у#нулевая частота, непустого подынтервала для него нет и такое завершение не определено. В адаптивной модели ненулевая поддержка терминатора должна сохраняться отдельно.
Все конечные сообщения получают общую массу один
Пусть суммарная вероятность обычных символов равна 1−q. Общая вероятность сообщений из ровно n данных с последующим#равна(1−q)ⁿq: сумма по всем словам длины n раскрывает n-йстепенью сумму их символьных вероятностей. Суммируя по n≥0, получаем геометрическую сумму 1.
Это доказывает почти наверное конечную остановку для независимой фиксированной модели. Без#или при q=0 такого распределения по конечным словам нет. При этом арифметические кодовые точки требуют ещё правил выдачи конечных битов: обычно выбирают двоичный цилиндр, целиком лежащий внутри завершённого интервала, чтобы все его продолжения декодировались одинаково.
Терминатор исключает продолжение, но добавляет информацию
Интервалы разных законченных сообщений не пересекаются: либо первые различающиеся данные выбирают разные подынтервалы, либо один путь выбирает#, когда другой выбирает продолжение данных. Это позволяет отличить короткое сообщение от начала длинного без внешней длины. Сам#не возвращается как пользовательский символ.
Вклад терминатора в идеальную информационную длину равен−log₂q бит. Это не обязательно отдельное целое число выведенных битов из-за совместного размещения цилиндра. Сравнивая эффективность с вариантом известной длины, нужно учитывать и вероятность#, и стоимость внешнего заголовка альтернативного формата, а не только ширину интервала данных.
Один символ и явная остановка
Условие. Порядок A,B,#, вероятности 1/2,1/4,1/4. Закодируйте сообщение B с последующим#и найдите полностью включённый двоичный цилиндр.
- После B текущий интервал равен[1/2,3/4), его ширина 1/4. Терминатор занимает последнюю четверть этого интервала.
- Нижняя граница становится 1/2+(1/4)(3/4)=11/16, верхняя 3/4=12/16. Ширина 1/16 равна p(B)p(#).
- Биты 1011 задают цилиндр[11/16,12/16), точно совпадающий с завершённым интервалом. Любое его продолжение декодирует B, затем#и остановку.
- Вероятность всех конечных сообщений равна Σₙ≥0(3/4)ⁿ(1/4)=1. Идеальная цена одного терминатора составляет 2 бита.
Ответ. Завершённый интервал[11/16,3/4), цилиндр 1011;терминатор добавляет идеальный вклад 2 бита.
Проверка. Точное декодирование точки 11/16 сначала выбирает B, а после нормировки получает 3/4, начало подынтервала#. Полуоткрытые границы однозначно относят его к терминатору.
Где легко ошибиться. Символ конца должен действительно участвовать в модели и сужении интервала. Одно предупреждение «нужен конец»не создаёт декодируемый формат само по себе.
Проверьте понимание
Вопросы к этой главе
Пустое сообщение разрешено?
Да. Оно кодируется одним#без данных и получает вероятность q. Его нужно учитывать в сумме масс, иначе общая вероятность конечных сообщений станет меньше 1.
Можно продолжать декодирование после#?
В данном формате нет: первый#завершает сообщение. Иной формат многокадрового потока должен отдельно определить начало следующей модели и границу следующего кода.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Project Nayuki: arithmetic-compress.py
Первичный исходник автора: прочитаны отдельный EOF символ и запись его после данных. Собственная трёхсимвольная вероятностная модель и доказательство суммарной массы конечных сообщений не копируют байтовый формат программы.
Перенормировка интервала и выдача общих битов
Арифметический интервал можно растягивать, постепенно выдавая уже определённые биты. Попадание в среднюю половину требует отложенного решения: следующие определённые биты разрешат накопленное противоположное продолжение.
Перед началом: Двоичный цилиндр; Полуоткрытый арифметический интервал.
Две крайние половины сразу определяют старший бит
Пусть текущий интервал[L,H) содержится в[0,1). Если H≤1/2, все кодовые точки начинаются с 0;выдаём 0 и заменяем границы на 2L,2H. Если L≥1/2, выдаём 1 и применяем x→2x−1. Так удаляется общий определённый старший бит, а интервал снова занимает большую часть единичного диапазона.
Эти преобразования аффинны и обратимы на выбранной половине. Поэтому декодер может поддерживать то же растяжение кодовой точки и границ. Границы обе вычисляются из старых значений;изменение одной до расчёта другой способно испортить ширину. Здесь описана идеальная рациональная модель, без округления конечного машинного диапазона.
Средняя половина хранит противоположные отложенные биты
Если L≥1/4 и H≤3/4, но общий старший бит ещё не определён, применяют x→2x−1/2 и увеличивают счётчик pending. В двоичной записи это соответствует неопределённому первому биту с противоположным следующим. Окончательный выбор первого ещё впереди, поэтому немедленно выдавать фиксированную пару нельзя.
Когда позже крайняя половина разрешит бит b, выдают b и pending копий противоположного 1−b, затем обнуляют счётчик. Несколько средних растяжений могут накопиться подряд. Это явление часто называют underflow, но математически интервал не пуст и информация не потеряна: она хранится в отложенном счётчике.
Нормировка не заменяет окончание сообщения
Каждое растяжение удваивает ширину рабочего интервала и переносит уже определённую информацию в битовый вывод либо pending. Оно не выбирает само по себе момент конца сообщения. В конце нужен согласованный формат завершения, разрешающий и оставшиеся неопределённые биты, иначе декодер может ждать продолжения.
Для независимой проверки можно собрать исходный цилиндр всех выданных битов и сравнить его с интервалом до растяжений. В коротком точном примере равенство рациональных границ показывает корректность всей цепочки. Перенос формул в целочисленный код требует отдельной проверки включённого верхнего конца, разрядности и правил округления;дробные границы не являются готовой реализацией этих соглашений.
Два отложенных бита
Условие. Начальный интервал[3/8,5/8). Выполните средние растяжения, затем в полученном рабочем интервале выберите нижнюю половину и выведите разрешённые биты.
- Первое среднее преобразование 2x−1/2 даёт[1/4,3/4),pending=1. Старший бит ещё не выдан.
- Второе такое же преобразование даёт[0,1),pending=2. Составное соответствие рабочего значения t исходному x имеет вид t=4x−3/2.
- Выбор нижней половины t∈[0,1/2) разрешает бит 0. После него выдаются две противоположные единицы: получаем 011.
- Обратное преобразование даёт исходный интервал x∈[3/8,1/2), а цилиндр 011 равен именно[3/8,4/8). Совпадение границ проверяет отложенный вывод.
Ответ. После двух средних шагов pending=2;разрешённый вывод 011 задаёт[3/8,1/2).
Проверка. Прямая двоичная интерпретация 011 как числа 3/8 и ширины 1/8 совпадает с решением 0≤4x−3/2<1/2. Эта проверка не использует повторно правило pending.
Где легко ошибиться. При среднем растяжении нельзя сразу выдать 0 или 1 как уже определённый старший бит. Сохраните pending и дождитесь крайнего случая, который разрешит весь блок.
Проверьте понимание
Вопросы к этой главе
Почему после 0 идут единицы?
Средний случай сохранил условие противоположности следующего бита первому. Поэтому окончательное 0 разрешает все накопленные продолжения как 1;для 1 они стали бы 0.
Число pending означает число потерянных битов?
Нет. Это отложенные, но полностью учитываемые биты. Потеря возникла бы только при забытом счётчике или несовместимом правиле его разрешения у кодера и декодера.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Project Nayuki: arithmeticcoding.py
Первичный исходник автора: прочитаны shift/underflow и накопление отложенных противоположных битов. Глава использует идеальную рациональную полуоткрытую модель, а не утверждает побитовое совпадение с целочисленными включёнными границами реализации.
rANS: сообщение в целочисленном состоянии вместо вложенного интервала
rANS хранит накопленную информацию в одном целом состоянии. Символ задаёт класс остатков, а частота определяет обратимое преобразование частного и остатка. Извлечение последнего добавленного символа точно восстанавливает прежнее состояние, поэтому порядок обработки сообщения требует явной договорённости.
Перед началом: Деление целых с остатком; Частотная модель конечного алфавита.
Частоты разбивают остатки на непересекающиеся блоки
Пусть каждому символу s назначена положительная целая частота fs, их сумма равна M, а cs — сумма частот предыдущих символов в фиксированном порядке. Интервалы остатков [cs,cs+fs) разбивают целые числа от 0 до M−1. По остатку r можно однозначно определить символ и его локальный номер r−cs.
Кодирующий шаг для неотрицательного состояния x задаётся формулой Cs(x)=M·floor(x/fs)+(x mod fs)+cs. Сначала x делится по размеру частотного блока, затем частное помещается в более широкую систему с основанием M, а остаток — в блок конкретного символа. Положительность частот необходима: нулевая частота не допускает ни деления, ни кодирования такого символа.
Декодирование одновременно возвращает символ и прежнее состояние
Для состояния y вычислим r=y mod M и найдём содержащий его частотный блок s. Тогда прежнее состояние равно fs·floor(y/M)+(r−cs). Действительно, локальная добавка в кодировании лежала от нуля до fs−1, а весь выбранный блок — внутри одного периода M. Поэтому деление y на M восстанавливает исходное частное без переноса.
Полученная пара «символ, прежнее состояние» однозначна. Декодирование извлекает символы в порядке, обратном их добавлению. Чтобы получить исходный текст слева направо, кодировщик добавляет его символы справа налево. Частоты, их порядок, начальное состояние и длина либо другое правило завершения должны быть известны декодеру; одно голое целое число не описывает весь формат сообщения.
Целочисленное ядро отделяется от ограниченного машинного буфера
Приведённые формулы работают с неограниченными целыми и непосредственно показывают обратимость. По мере добавления символов состояние растёт. Практический rANS удерживает его в ограниченном диапазоне, выдавая младшие разряды при кодировании и возвращая их при декодировании. Правила такой нормализации должны быть согласованы с частотами и основанием вывода.
В этой задаче исследуется именно целочисленное ядро: оно ещё не является готовым байтовым форматом и не обещает самозавершения. Сумма частот для математической обратимости не обязана быть степенью двойки. Степень двойки часто выбирают в реализации, чтобы заменить некоторые деления и остатки сдвигами и масками, но это отдельное инженерное решение.
Четыре обратимых добавления и четыре извлечения
Условие. Алфавит A,B,C имеет частоты 3,2,1, поэтому M=6 и накопленные начала cA=0,cB=3,cC=5. Начальное состояние равно 10, длина сообщения ABCA известна и равна 4. Найдите итоговое состояние и восстановите сообщение.
- Кодируем справа налево, то есть A,C,B,A. Для первого A получаем 6·floor(10/3)+(10 mod 3)=18+1=19.
- Для C частота равна 1: состояние становится 6·19+5=119. Для B получаем 6·floor(119/2)+(119 mod 2)+3=354+1+3=358.
- Последнее добавление A даёт 6·floor(358/3)+(358 mod 3)=714+1=715. Это итоговое целое состояние.
- Декодируем 715: остаток 1 указывает A, предыдущее состояние 3·119+1=358. Остаток 358 по модулю 6 равен 4, это B, восстановленное состояние 2·59+(4−3)=119.
- Из 119 остаток 5 указывает C и возвращает 19. Из 19 остаток 1 указывает A и возвращает 10. Четыре извлечённых символа дают ABCA и исходное состояние.
Ответ. Итоговое состояние равно 715; декодирование четырёх символов даёт ABCA и возвращает 10.
Проверка. Независимый перебор состояний 0,…,100 и всех трёх символов подтверждает обратный шаг. Перебор сообщений длины до пяти проверяет обратный порядок добавления и восстановление начального состояния.
Где легко ошибиться. Не кодируйте слева направо, ожидая затем обычный прямой порядок извлечения. Целочисленное ядро rANS действует как стек символов, а не как очередь.
Проверьте понимание
Вопросы к этой главе
Зачем сообщать длину сообщения?
В целочисленном ядре нет автоматически распознаваемого конца текста. Здесь декодер обязан сделать ровно четыре шага; иначе он продолжил бы интерпретировать начальное состояние как ещё закодированные символы.
Можно ли частоту C сделать нулевой?
Тогда C не имеет блока остатков и не может быть закодирован. Для символов, реально встречающихся в сообщении, модель должна задавать строго положительные частоты.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Jarek Duda: Asymmetric numeral systems
Раздел о range ANS: частотные блоки, обратимые целочисленные функции кодирования и декодирования; нормализация состояния рассматривается отдельно от ядра.
LZ77 разрешает копирование из уже восстанавливаемого фрагмента
Ссылка длиной семь может быть корректной, даже если в словаре перед ней лежат всего три символа. В LZ77 новые символы сразу становятся доступными следующему шагу той же ссылки. Проследим это правило на коротком потоке и разберём ошибку, возникающую при копировании неизменяемого среза.
Перед началом: Индексы массива с нуля; Буквальный символ и словарная ссылка.
Источник существует перед каждым отдельным чтением
Учебный поток буквальных ASCII-символов и пар (distance,length). Расстояние отсчитывается назад от текущего конца уже восстановленного текста.
Пусть перед ссылкой уже восстановлено m символов. Пара (d,l) означает l последовательных действий: взять символ на расстоянии d назад от текущего конца и добавить его в конец. Требуются целые d≥1, l≥1 и d≤m. На шаге j источник имеет индекс m+j−d, а записываемая позиция — m+j; источник всегда строго раньше назначения.
Неравенство d≤m гарантирует, что самый первый индекс неотрицателен. На остальных шагах источник может лежать уже внутри нового фрагмента, но этот символ к тому времени был записан. Поэтому условие l≤d не нужно. Ссылка не использует неизвестное будущее: она опирается на расширяющийся доступный префикс. Это и есть инвариант корректного декодирования.
Почему один срез не заменяет последовательное копирование
При l>d часть ответа определяется повторением начального фрагмента периода d. Копирование исходного среза длины не более d только один раз выдаст слишком короткий результат. Другая ошибка — заранее выделить незаполненную область и читать её содержимое до записи. Реализация обязана воспроизвести последовательную семантику, даже если затем оптимизирует повторяющиеся блоки.
В скользящем словаре дополнительно действует предел допустимого расстояния. Отброшенный префикс не может использоваться, если формат не предусматривает внешний словарь. При этом граница блока сжатых данных не обязательно очищает словарь: такое правило определяется форматом. Здесь словарь сохраняется на протяжении всего нашего короткого сообщения.
Самая длинная ссылка ещё не определяет цену в битах
При поиске совпадения кодер тоже может проверять перекрывающуюся ссылку: дальнейшие символы должны согласовываться с периодическим продолжением доступного образца. Для фиксированной позиции выбирается допустимое расстояние и проверяется весь заявленный фрагмент. Одного совпадения начальных трёх букв недостаточно, чтобы без проверки приписать ссылке произвольную длину.
Длина совпадения и экономия битов различаются. Формат отдельно кодирует буквальные значения, длины и расстояния, может ограничивать их диапазоны и платить дополнительные биты за большое расстояние. Наш поток показывает только обратимость словарных токенов; он не является готовым DEFLATE-файлом и не доказывает оптимальность жадного разбора по итоговому размеру.
Три буквы запускают семисимвольное самокопирование
Условие. Декодируйте токены literal(t), literal(e), literal(a), copy(distance=3,length=7), literal(!). Покажите, какие символы добавляет ссылка.
- После трёх буквальных токенов буфер равен tea, m=3. Расстояние d=3 допустимо; длина семь превышает и расстояние, и исходную длину буфера.
- Первые три шага читают индексы 0,1,2 и добавляют t,e,a. Получается teatea. При каждом шаге источник на три позиции раньше нового конца.
- Следующие три шага читают индексы 3,4,5 — уже восстановленные буквы той же ссылки. Они опять добавляют t,e,a; буфер равен teateatea.
- Седьмой шаг читает индекс 6 и добавляет t. В результате одной ссылки получено teateateat, всего десять символов.
- Последний буквальный токен добавляет восклицательный знак. Полный ответ teateateat! имеет длину 3+7+1=11.
Ответ. teateateat!
Проверка. Добавленный семисимвольный фрагмент равен teateat. Для j=0,…,6 проверены источники m+j−d=j и назначения m+j=3+j; ни одно чтение не обращается к ещё не записанной позиции.
Где легко ошибиться. Не запрещайте ссылку только из-за length>distance и не копируйте исходный фрагмент одним неизменяемым срезом. Проверять нужно доступность источника на каждом шаге расширения буфера.
Проверьте понимание
Вопросы к этой главе
Может ли первая ссылка иметь ненулевое расстояние при пустом словаре?
В данной модели нет: при m=0 условие 1≤d≤m невыполнимо. Предварительно заданный внешний словарь изменил бы начальный доступный префикс, но он должен быть явно согласован с декодером.
Где расположена граница символа в словарной ссылке?
Здесь ссылка — уже распознанный токен с двумя целыми параметрами. Выделение этих параметров из битового потока относится к отдельному уровню формата. Само словарное копирование не задаёт ни их код, ни маркер конца сообщения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- RFC 1951, §3.2.3: backward references and overlapping copies
Прочитаны граница допустимого расстояния и последовательное копирование перекрывающейся ссылки. Наш поток с tea и отдельным буквальным ! задан и проверен самостоятельно; битовый контейнер DEFLATE здесь не воспроизводится.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Из таблицы истинности в XOR-многочлен: сначала закрепите порядок переменных
Построить единственную алгебраическую нормальную форму булевой функции преобразованием Мёбиуса и подтвердить её подстановкой на всех наборах.
Открыть темуБлижайшее кодовое слово и гарантированное исправление — разные утверждения
Перечислить малый двоичный линейный код, установить минимальное расстояние и показать все ближайшие к принятому слову варианты без скрытого выбора.
Открыть темуКороткая рекурсия объясняет префикс, но не доказывает неизвестное продолжение
Найти минимальную линейную рекурсию конечной последовательности над малым простым полем, проверить знаки коэффициентов и границу прогноза.
Открыть тему