Информатика · объяснение и практика

Почему префиксный код читается без разделителей

Расшифровываем поток по дереву кодов, проверяем отсутствие одного слова в начале другого и различаем мгновенное и просто однозначное декодирование.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта

Главная мысль

Префиксный код устроен так, что ни одно кодовое слово не является началом другого. Поэтому поток можно читать слева направо и завершать символ сразу после распознавания его слова. Разделители между словами при таком согласованном коде не нужны.

Отмечайте только законченные кодовые слова

Зададим коды трёх знаков: А=00, Б=01, В=1. Слова 00 и 01 имеют одинаковую длину, а одноразрядное 1 не является их началом. Этот набор префиксный. Поток 0010101 читаем как 00 | 1 | 01 | 01, то есть АВББ. После каждого законченного слова начинаем читать следующее от корня.

В дереве по первому нулю ещё нельзя назвать знак: продолжение может быть нулём или единицей. Но по первой единице сразу известно В. Кодовые слова соответствуют листьям, а не внутренним развилкам. Поэтому одно сообщение можно читать постепенно без ожидания следующего знака после каждого распознанного листа.

Пример

Поток 0010101 единственным образом делится на АВББ по заданной таблице.

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

Нарушение префиксности видно на паре слов

Если взять А=0 и Б=01, то слово 0 является началом 01. После первого нуля нельзя немедленно выдать А: следующая единица могла завершать Б. Значит, код не префиксный. Для проверки достаточно найти любую пару разных слов, где одно начинается с другого.

Однако отсутствие префиксности не всегда означает неоднозначность всей конечной записи. Набор {0,01} допускает однозначное декодирование с ожиданием, если известны границы сообщения: каждая единица может завершить только 01. Иное дело {0,01,1}: поток 01 означает либо одно слово 01, либо два слова 0 и 1. Здесь уже есть действительная неоднозначность.

Конец сообщения тоже должен быть корректным

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

Таблица кодирования должна быть известна обеим сторонам. Передача самой таблицы, количества знаков или длины полезной части добавляет служебные расходы, которые учитывают отдельно. Префиксность решает задачу выделения границ кодовых слов; она не шифрует данные и не исправляет повреждённые биты. Одну неверную цифру иногда можно прочитать как другое допустимое слово без заметного сигнала ошибки.

От чтения к действию

А теперь — вы

Какой набор разных двоичных кодовых слов является префиксным?

Частые вопросы

Любой код с одинаковой длиной слов префиксный?

Если все слова различны и имеют одну положительную длину, да: ни одно не может быть собственным началом другого той же длины.

Префиксный код обязательно самый короткий?

Нет: префиксность обеспечивает способ декодирования. Эффективность длины зависит от частот символов и выбора кодовых слов; для оптимального выбора есть отдельные методы.

Углублённый разбор

Ограниченная длина префиксного кода меняет оптимум

Оптимальный префиксный код может иметь слишком длинное слово для протокола с ограниченной задержкой. Ограничение максимальной длины меняет допустимые деревья и иногда увеличивает среднюю стоимость. Обычный результат Хаффмана нельзя просто обрезать: нужен новый допустимый профиль глубин.

Перед началом: Префиксный код; Неравенство Крафта.

Жёсткий предел меняет множество оптимизации

Для N символов с положительными частотами w₁,…,w_N ищем бинарные кодовые длины ℓᵢ от1 до L, удовлетворяющие Σ2^(−ℓᵢ)≤1, и минимизируем Σwᵢℓᵢ. Неравенство Крафта необходимо и достаточно для существования двоичного префиксного кода с этими длинами. Первичная проверка N≤2ᴸ обязательна: больше разных листьев до глубины L не поместится независимо от частот.

Если частоты упорядочены по убыванию, длины в оптимуме можно назначить по возрастанию: обмен более длинного слова тяжёлому символу с более коротким лёгкому не увеличивает стоимость. Поэтому поиск можно вести по числу листьев на каждой глубине, не перебирая все перестановки символов. Положительность позволяет исключить внутренние узлы с одним ребёнком: их сжатие сокращает длины и улучшает цель.

Динамика распределяет доступные узлы по слоям

Состояние хранит текущую глубину d, число уже назначенных наиболее тяжёлых символов j и число доступных узлов s. Выбираем t≤s узлов листьями и назначаем им следующие t частот, добавляя d·Σw к стоимости. Остальные s−t становятся внутренними и создают 2(s−t) узлов следующего слоя. На глубине L все оставшиеся доступные узлы должны стать листьями и число назначенных символов должно оказаться N.

Невозможные состояния отсекаются по оставшемуся числу символов и вместимости глубин. Это простая конечная DP; её не следует путать с более быстрыми специализированными length-limited алгоритмами. Она показывает, почему механическое укорочение длинного слова Хаффмана неверно: освободившиеся и занятые позиции дерева связаны между слоями, и локальное изменение может нарушить Крафта.

Сравниваем ограниченный и обычный оптимумы

Неограниченный оптимум является нижней границей ограниченного, но может быть недопустим. Для сертификата нового оптимума на маленьком алфавите достаточно перечислить все возможные полные профили до L, назначить тяжёлые частоты коротким длинам и сравнить стоимости. Затем нужно предъявить реальные префиксные слова. Это проверяет не только число битов, но и реализуемость выбранного профиля без конфликтов префиксов.

Все полные профили пяти листьев до глубины 3
ДлиныВзвешенная стоимостьМаксимальная длина
1,3,3,3,3623
2,2,2,3,3673

Пять символов при пределе три бита

Условие. Частоты A=17,B=8,C=4,D=2,E=1. Найдите минимальную стоимость бинарного префиксного кода при максимальной длине L=3 и сравните с обычным Хаффманом.

  1. Без ограничения слияния имеют веса 3,7,15,32 и общую стоимость 57. Длины 1,2,3,4,4 содержат слова длины 4, поэтому этот код недопустим при L=3.
  2. Для пяти листьев полного дерева высоты≤3 возможны отсортированные профили(1,3,3,3,3) и(2,2,2,3,3). Они следуют из распределения двух узлов первой глубины и обязательного удвоения внутренних узлов.
  3. Первый профиль имеет стоимость 17+3·(8+4+2+1)=62. Второй даёт 2·(17+8+4)+3·(2+1)=67. Значит оптимум 62.
  4. Код A=0,B=100,C=101,D=110,E=111 реализует лучший профиль. Крафт даёт 1/2+4/8=1, ни одно слово не является префиксом другого.

Ответ. Ограниченный оптимум 62 бита против неограниченных 57; явный допустимый код имеет длины 1,3,3,3,3.

Проверка. Независимый перебор 243 назначений длин из1,2,3 проверяет Крафта и находит минимум 62. Отдельный перебор кодовых слов подтверждает префиксность конструкции; при L=2 задача невозможна, потому что 5>4.

Где легко ошибиться. Не обрезайте слова Хаффмана до нужной длины и не принимайте неограниченную стоимость за достижимую при новом ограничении. Сначала проверьте вместимость и условие Крафта.

Проверьте понимание

Какова минимальная стоимость кода с L=3 для данных частот?

Вопросы к этой главе

Почему более частая B стала длиннее, чем в обычном коде?

Чтобы вместить все пять листьев до глубины 3 и оставить A на глубине 1, четыре остальных должны занять третий слой. Ограничение заставляет пожертвовать коротким словом B ради допустимости всего дерева.

Можно ли убрать редкий символ E?

Только изменив исходный алфавит и задачу кодирования. Положительная частота 1 означает, что E реально встречается и обязана иметь собственное кодовое слово. Исключение ради удобного дерева не решает данную задачу.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Golin, Zhang: Length-Limited Huffman Coding, §I–II

    Прочитаны постановка с пределом глубины, положительные частоты и динамическое описание деревьев. Здесь используется простая учебная DP по доступным узлам, а не заявленный авторами Monge-алгоритм с линейной памятью. Собственные частоты 17,8,4,2,1 проверены перебором всех длин 1..3.

Однозначная декодируемость без префиксности: алгоритм Сардинаса — Паттерсона

Непрефиксный код не обязательно неоднозначен. Алгоритм Сардинаса — Паттерсона проверяет оставшиеся несогласованные хвосты двух возможных разбиений. На двух самостоятельно выбранных кодах получим либо исчезновение хвостов, либо конкретную строку с двумя разбиениями.

Перед началом: Конкатенация строк и отношение префикса; Конечные множества непустых кодовых слов.

Неоднозначность начинается с префиксного перекрытия

Код однозначно декодируем, если каждая составленная из его слов строка имеет единственную последовательность этих слов. Префиксность достаточна: никакое слово не является началом другого. Но её отсутствие ещё не доказывает существование двух полных разбиений. Короткое слово может совпасть с началом длинного, оставив хвост, который никогда не удастся согласовать до конца.

Для множества C непустых различных слов первое множество хвостов U1 состоит из остатков v после равенств a v=b для разных a, b∈C. Затем сравнивают каждый хвост u с каждым кодовым словом c в обоих направлениях: если u v=c или c v=u, новый хвост равен v. Оба направления необходимы, потому что после очередного шага более длинной может стать другая сторона сравнения.

Как алгоритм принимает решение

Если среди новых хвостов появляется пустая строка ε, два разных начальных разбиения полностью согласовались: код неоднозначен. Эквивалентно можно остановиться, когда текущий непустой хвост сам является кодовым словом. Если множество хвостов опустело, продолжать сравнение нечего. Если повторилось уже рассмотренное множество без ε, дальнейшие шаги тоже не приведут к новому исходу.

Все непустые хвосты являются суффиксами конечного набора кодовых слов, поэтому проверка заканчивается. При реализации можно обходить граф отдельных хвостов, помечая уже посещённые, и сохранять предшественников. Тогда отрицательный результат сопровождается не только словом «нет», но и восстановленной строкой с двумя полными последовательностями кодовых слов.

Сравнение двух кодов

Для C={0,001,011} первое множество равно{01,11}. Следующий шаг даёт{1}: хвост 01 сравнивается с 0 и 011. После этого новых хвостов нет, поскольку ни одно кодовое слово не начинается с 1, а 1 не начинается с кодового слова. Поэтому C однозначно декодируем, хотя 0 является префиксом 001 и 011.

Для D={00,001,100} сначала получаем{1}, затем{00}. Хвост 00 сам является словом D, поэтому есть неоднозначность. Строка 00100 имеет разбиения 00|100 и 001|00. Обе суммы Крафта не превышают 1, но это не делает D однозначным: неравенство ограничивает длины, а проверка хвостов использует действительное расположение символов.

Хвост исчез или завершил второе разбиение

Условие. Примените алгоритм к C={0,001,011} и D={00,001,100}. Для неоднозначного случая предъявите два разбиения одной строки.

  1. У C слово 0 перекрывает 001 и 011, поэтому U1={01,11}.
  2. Следующие множества C: U2={1}, U3=∅. Пустая строка ε не возникла; C однозначно декодируем.
  3. У D перекрытие 00 и 001 оставляет 1. Сравнение 1 со 100 даёт хвост 00, который сам является кодовым словом.
  4. Восстанавливаем совпадение 00100=00·100=001·00. Последовательности слов различны, поэтому D неоднозначен.

Ответ. C однозначен, несмотря на непрефиксность. D неоднозначен:00100 имеет два указанных разбиения.

Проверка. Прямая конкатенация проверяет отрицательный свидетель D. Для C конечная цепочка множеств до ∅ доказывает отсутствие любых более длинных неоднозначностей, чего один ограниченный перебор строк не обеспечил бы.

Где легко ошибиться. Не останавливайтесь на одном префиксном перекрытии: решающим является полное согласование оставшихся хвостов.

Проверьте понимание

Какое утверждение верно для рассмотренных кодов?

Вопросы к этой главе

Чем пустое множество отличается от пустого хвоста?

Пустое множество означает отсутствие продолжений перекрытия. Пустой хвост ε означает, что два разбиения согласовались полностью, и служит свидетельством неоднозначности.

Достаточно ли проверить все короткие строки?

Для положительного ответа нет. Алгоритм хвостов даёт конечный критерий для строк любой длины; ограниченный перебор может только найти конкретный отрицательный пример.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Код Райса разделяет целое на унарное частное и фиксированный остаток

Для чисел 0,3,13 параметр k=2 даёт двенадцать полезных битов. При k=1 и k=3 требуется уже тринадцать. Выведем длины из частного и остатка и расшифруем поток без разделителей; подбор параметра здесь проверяется точным подсчётом, а не впечатлением от размера чисел.

Перед началом: Целочисленное деление с остатком; Префиксные кодовые слова.

Два описания одной части числа

Неотрицательные целые и заранее известный параметр k≥0. Унарное частное записывается нулями с завершающей единицей, затем ровно k бит остатка.

Для числа u≥0 единственным образом запишем u=q·2ᵏ+r, где q=⌊u/2ᵏ⌋ и 0≤r<2ᵏ. Частное q кодируется q нулями и одной единицей-ограничителем. За ней следует остаток r в двоичной записи ровно из k разрядов, включая ведущие нули. Полученная длина равна q+1+k; это число полезных битов самого символа.

Декодер считает нули до первой единицы, получает q и затем забирает ровно k следующих битов. Он немедленно знает границу слова и восстанавливает u. Разные q имеют разные положения ограничителя, а при равном q остатки имеют одинаковую длину. Поэтому ни одно законченное слово не является собственным началом другого.

Параметр оплачивает разные части распределения

Малое k уменьшает фиксированную часть, но увеличивает унарное частное больших чисел. Большое k делает остаток длинным даже у нуля. Для набора u₁,…,uₘ суммарная длина равна Σ⌊uᵢ/2ᵏ⌋+m(k+1). По этой формуле можно честно сравнить допустимые параметры, не строя каждый битовый поток заново.

Выбранное k тоже должно стать известно декодеру. Если параметр меняется от блока к блоку, стоимость его заголовка добавляется к полезным битам. Код Райса особенно удобен для наборов с множеством малых значений; один редкий огромный выброс способен создать длинный унарный хвост. В реальном декодере заранее ограничивают допустимую длину такого хвоста.

Знак и конец блока не спрятаны в формуле

Кодируемые u не имеют знака. Для целого остатка z можно отдельно согласовать отображение z≥0→2z и z<0→−2z−1. Тогда 0,−1,1,−2 переходят в 0,1,2,3. Это взаимно однозначная подготовка данных, а не изменение унарного правила. Параметр выбирают уже по преобразованным величинам.

Префиксность выделяет отдельное целое число, но байтовому контейнеру ещё нужны число значений или точная полезная битовая длина. Дополнение последнего байта может выглядеть как начало нового слова. Если поток оборвался до ограничителя или внутри k-разрядного остатка, декодер сообщает об усечении; незаписанные биты нельзя молча считать нулями.

Двенадцать битов и обратный разбор

Условие. Закодируйте неотрицательные 0,3,13 кодом Райса с k=2. Сравните общую длину с остальными k≥0 и восстановите исходный набор.

  1. Делитель равен четырём. Пары (q,r) для трёх чисел: (0,0), (0,3), (3,1). Двухбитовые остатки равны 00,11,01.
  2. Получаем слова 1|00, 1|11 и 0001|01, то есть 100,111,000101. Их длины 3,3,6 дают двенадцать битов.
  3. Общий поток 100111000101 читается слева направо. Первая единица и 00 дают ноль; следующая единица и 11 дают три; три нуля до единицы и 01 дают 3·4+1=13.
  4. При k=0 длины равны 1,4,14, сумма 19. При k=1 получаем 2,3,8, сумма 13; при k=3 — 4,4,5, снова 13.
  5. Для любого k≥4 все три частных нулевые, поэтому сумма равна 3(k+1)≥15. Значит среди всех неотрицательных k минимум действительно достигается при k=2.

Ответ. Поток 100111000101; полезная длина 12 битов, оптимальный для этого набора параметр k=2.

Проверка. Формула Σ⌊u/4⌋+3(2+1)=3+9=12 совпадает с длиной построенной строки. Три независимых разложения u=q·4+r после обратного чтения возвращают 0,3,13.

Где легко ошибиться. Не удаляйте ведущие нули остатка: после унарного ограничителя декодер обязан прочитать ровно k разрядов. Согласуйте также направление унарного кода; здесь это нули, завершённые единицей.

Проверьте понимание

Как кодируется 13 при k=2 и соглашении «q нулей, затем единица, затем k бит остатка»?

Вопросы к этой главе

Что происходит при k=0?

Остаток всегда нулевой и не занимает битов. Число u передаётся u нулями и одной единицей. Это корректный унарный код, хотя на больших значениях он может быть очень длинным.

Двенадцать полезных битов означают архив из полутора байтов?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • RFC 9639, §4 and §9.2.7: Rice residual coding

    Сверены деление на степень двойки, нулевая унарная часть с единичным ограничителем, фиксированная длина остатка и ограничение чрезмерного хвоста. Наш трёхчисловой пример и полный выбор параметра пересчитаны самостоятельно.

Алфавитный префиксный код сохраняет порядок листьев

Если средний по порядку символ встречается почти всегда, свободный префиксный код отдаст ему одноразрядное слово. Алфавитное ограничение может запретить такое дерево. Для весов 1,100,1 цена сохранения порядка оказывается особенно заметной: 203 вместо 104. Выведем оба результата и предъявим допустимые слова.

Перед началом: Дерево префиксного кода; Динамическое программирование по отрезкам.

Каждое поддерево хранит непрерывный блок символов

Двоичное префиксное дерево с положительными весами листьев; их заранее заданный порядок слева направо менять нельзя.

Пусть исходный порядок символов равен A₁,…,Aₙ. Алфавитным называют двоичное кодовое дерево, в котором листья при обходе слева направо расположены именно так. Ноль соответствует левому ребёнку, единица — правому. Любое поддерево содержит непрерывный отрезок исходного порядка: иначе между его листьями оказался бы лист другого поддерева.

Узел с одним ребёнком при положительных весах не нужен: его сжатие уменьшает длины потомков и сохраняет порядок. Значит можно рассматривать полные двоичные деревья. Корень любого дерева на отрезке [i,j] делит его между k и k+1, где i≤k<j. Перестановка двух листьев по весам уже не является допустимым приёмом.

Рекурсия учитывает один общий дополнительный бит

Обозначим E(i,j) минимальную взвешенную длину внутри поддерева, считая его корень глубиной ноль. Для одного листа E(i,i)=0. Если выбрать корневой разрез k, каждый лист обеих частей станет на один уровень глубже. Поэтому E(i,j)=W(i,j)+minₖ[E(i,k)+E(k+1,j)], где W(i,j)=Σᵣ₌ᵢʲwᵣ.

Эта формула не просто даёт кандидата. Любое допустимое дерево имеет некоторый корневой разрез и два допустимых поддерева, значит не может стоить меньше правой части. Обратно, соединение двух оптимальных поддеревьев выбранного разреза реализует эту стоимость. Заполняя интервалы по возрастанию длины, получают и число, и разрезы для восстановления кодовых слов.

Ограничение порядка отличается от предела глубины

Префиксность сама по себе не определяет порядок листьев. Алгоритм Хаффмана вправе сначала объединить два самых лёгких символа, даже если между ними стоит тяжёлый. Для алфавитного дерева такая пара не всегда образует непрерывный блок. Проверять лишь неравенство Крафта поэтому недостаточно: оно не привязывает выбранные длины к заданному расположению символов.

В этой задаче максимальная глубина не ограничена отдельно. Добавление такого ограничения потребовало бы ещё одного параметра состояния и новой проверки допустимости. Простая интервальная динамика работает за O(n³) времени и O(n²) памяти; известные более быстрые специальные алгоритмы не нужны для доказательства и проверки нашего маленького примера.

Тяжёлый символ в середине порядка

Условие. Символы A,B,C должны идти слева направо в этом порядке. Их веса равны 1,100,1. Найдите алфавитный оптимум и сравните со свободным префиксным кодом.

  1. Для пары A,B и пары B,C стоимость равна сумме весов: E(A,B)=101, E(B,C)=101. Для одного листа стоимость нулевая.
  2. Общий вес равен 102. Разрез A|BC даёт 102+0+101=203; разрез AB|C даёт 102+101+0=203. Других корневых разрезов нет.
  3. Первый оптимум реализуют A=0,B=10,C=11. Взвешенная длина 1·1+100·2+1·2=203; порядок листьев A,B,C сохранён.
  4. Без ограничения можно объединить A и C, затем их узел веса два с B. Например B=0,A=10,C=11 даёт 100·1+1·2+1·2=104.
  5. Свободный код дешевле, но его порядок листьев B,A,C нарушает условие. Замена нулей и единиц у корня не поставит одиночный B между двумя другими листьями.

Ответ. Алфавитная стоимость равна 203; свободная — 104. Два разных алфавитных дерева достигают одного минимума.

Проверка. Для трёх листьев полное двоичное дерево имеет только формы (A,(B,C)) и ((A,B),C). Прямой подсчёт их глубин подтверждает обе стоимости 203 независимо от таблицы динамики.

Где легко ошибиться. Не сортируйте символы по весам перед алфавитной оптимизацией: это изменит саму задачу. Одинаковые множества длин тоже не гарантируют допустимости их назначения конкретным упорядоченным символам.

Проверьте понимание

Чему равен алфавитный оптимум для разобранных весов A=1,B=100,C=1?

Вопросы к этой главе

Что значит алфавитный, если символы — числа или категории?

Нужен любой заранее закреплённый линейный порядок, а не обязательно русский алфавит. Такое дерево удобно, когда ветвление должно сохранять последовательность ключей или отвечать на пороговые вопросы.

Почему у одного листа внутренняя цена ноль?

У корня поддерева нет внутренних рёбер до этого единственного листа. При соединении с родителем общий дополнительный бит уже учитывается через W(i,j). Повторное прибавление единицы в базовом случае завысило бы все стоимости.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Michael B. Baer: Alphabetic Coding with Exponential Costs, Introduction and Definition 1

    Прочитаны классическая линейная цель и определение порядка листьев. Здесь выведена собственная простая интервальная динамика для линейной стоимости; экспоненциальный критерий дальнейших разделов статьи не подменяет нашу задачу.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться