Неравенство Крафта – Макмиллана

В теории кодирования неравенство Крафта –Макмиллана дает необходимое и достаточное условие существования префиксного кода. (в версии Леона Г. Крафта) или однозначно декодируемый код (в версии Брокуэя Макмиллана ) для заданного набора длин кодовых слов . Его приложения для префиксных кодов и деревьев часто находят применение в информатике и теории информации . Префиксный код может содержать как конечное, так и бесконечное число кодовых слов.

Неравенство Крафта было опубликовано в Kraft (1949) . Однако в статье Крафта обсуждаются только префиксные коды, а анализ, приведший к неравенству, приписывается Раймонду Редхефферу . Результат был независимо обнаружен Макмилланом (1956) . Макмиллан доказывает результат для общего случая однозначно декодируемых кодов и приписывает версию для префиксных кодов устному наблюдению Джозефа Лео Дуба в 1955 году .

Приложения и интуиция

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

• Если неравенство Крафта выполняется при строгом неравенстве, код имеет некоторую избыточность .
• Если неравенство Крафта выполняется с равенством, рассматриваемый код является полным кодом.
• Если неравенство Крафта не выполняется, код не является однозначно декодируемым .
• Для каждого однозначно декодируемого кода существует префиксный код с тем же распределением длин.

Официальное заявление

Пусть каждый исходный символ из алфавита

$S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}$

быть закодировано в уникальный декодируемый код в алфавите размера $r$ с длиной кодового слова

$\ell _{1},\ell _{2},\ldots ,\ell _{n}.$

Затем

$\sum _{i=1}^{n}r^{-\ell _{i}}\leqslant 1.$

И наоборот, для данного набора натуральных чисел $\ell _{1},\ell _{2},\ldots ,\ell _{n}$ удовлетворяя указанному выше неравенству, существует однозначно декодируемый код в алфавите размера $r$ с такой длиной кодового слова.

Пример: бинарные деревья

9, 14, 19, 67 и 76 — листовые узлы на глубинах 3, 3, 3, 3 и 2 соответственно.

Любое двоичное дерево можно рассматривать как определение префиксного кода для листьев дерева. Неравенство Крафта утверждает, что

$\sum _{\ell \in {\text{leaves}}}2^{-{\text{depth}}(\ell )}\leqslant 1.$

Здесь сумма берется по листьям дерева, то есть по узлам без дочерних элементов. Глубина — это расстояние до корневого узла. В дереве справа эта сумма равна

${\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leqslant 1.$

Доказательство

Доказательство префиксных кодов

Пример двоичного дерева. Красные узлы представляют префиксное дерево. Показан метод расчета количества узлов-потомков в полном дереве.

Сначала покажем, что неравенство Крафта выполняется всякий раз, когда код для $S$ это префиксный код.

Предположим, что $\ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}$. Позволять $A$ быть полным $r$-арное дерево глубины $\ell _{n}$ (таким образом, каждый узел $A$ на уровне $<\ell _{n}$ имеет $r$ дети, а узлы на уровне $\ell _{n}$ это листья). Каждое слово длины $\ell \leqslant \ell _{n}$ над $r$-арный алфавит соответствует узлу в этом дереве на глубине $\ell$. $i$-е слово в префиксном коде соответствует узлу $v_{i}$; позволять $A_{i}$ быть набором всех листовых узлов (т.е. узлов на глубине $\ell _{n}$) в поддереве $A$ укорененный в $v_{i}$. Это поддерево имеет высоту $\ell _{n}-\ell _{i}$, у нас есть

$|A_{i}|=r^{\ell _{n}-\ell _{i}}.$

Поскольку код является префиксным кодом, эти поддеревья не могут иметь общие листья, а это означает, что

$A_{i}\cap A_{j}=\varnothing ,\quad i\neq j.$

Таким образом, учитывая, что общее количество узлов на глубине $\ell _{n}$ является $r^{\ell _{n}}$, у нас есть

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|=\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n}}$

откуда следует результат.

И наоборот, для любой упорядоченной последовательности $n$ натуральные числа,

$\ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}$

удовлетворяя неравенству Крафта, можно построить префиксный код с длиной кодового слова, равной каждому $\ell _{i}$ выбрав слово длины $\ell _{i}$ произвольно, затем исключая все слова большей длины, у которых он есть в качестве префикса. И снова мы будем интерпретировать это в терминах листовых узлов $r$-арное дерево глубины $\ell _{n}$. Сначала выберите любой узел из полного дерева на глубине. $\ell _{1}$; оно соответствует первому слову нашего нового кода. Поскольку мы строим префиксный код, все потомки этого узла (т. е. все слова, имеющие это первое слово в качестве префикса) становятся непригодными для включения в код. Рассматриваем потомков на глубине $\ell _{n}$ (т.е. листовые узлы среди потомков); есть $r^{\ell _{n}-\ell _{1}}$ такие узлы-потомки, которые исключены из рассмотрения. Следующая итерация выбирает (выживший) узел на глубине. $\ell _{2}$ и удаляет $r^{\ell _{n}-\ell _{2}}$ дальнейшие листовые узлы и так далее. После $n$ итераций, мы удалили всего

$\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}$

узлы. Вопрос в том, нужно ли нам удалять больше конечных узлов, чем у нас есть на самом деле. $r^{\ell _{n}}$ в общем — в процессе сборки кода. Поскольку неравенство Крафта выполнено, мы действительно имеем

$\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n}}$

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

Доказательство общего случая

Теперь мы докажем, что неравенство Крафта выполняется всякий раз, когда $S$ представляет собой однозначно декодируемый код. (Обратное утверждение не нуждается в доказывании, поскольку мы уже доказали это для префиксных кодов, что является более сильным утверждением.) Доказательство принадлежит Джеку И. Карушу.

Нам нужно доказать это только в случае конечного числа кодовых слов. Если кодовых слов бесконечно много, то любое его конечное подмножество также однозначно декодируемо, поэтому оно удовлетворяет неравенству Крафта – Макмиллана. Взяв предел, мы имеем неравенство для полного кода.

Обозначим $C=\sum _{i=1}^{n}r^{-l_{i}}$. Идея доказательства состоит в том, чтобы получить верхнюю оценку $C^{m}$ для $m\in \mathbb {N}$ и покажем, что оно может выполняться только для всех $m$ если $C\leq 1$. Переписать $C^{m}$ как

${\begin{aligned}C^{m}&=\left(\sum _{i=1}^{n}r^{-l_{i}}\right)^{m}\\&=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}r^{-\left(l_{i_{1}}+l_{i_{2}}+\cdots +l_{i_{m}}\right)}\\\end{aligned}}$

Рассмотрим все m -степени $S^{m}$, в виде слов $s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}$, где $i_{1},i_{2},\dots ,i_{m}$ индексы между 1 и $n$. Обратите внимание, что, поскольку S предполагалось, что однозначно декодируемо, $s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}=s_{j_{1}}s_{j_{2}}\dots s_{j_{m}}$ подразумевает $i_{1}=j_{1},i_{2}=j_{2},\dots ,i_{m}=j_{m}$. Это означает, что каждое слагаемое соответствует ровно одному слову в $S^{m}$. Это позволяет нам переписать уравнение в виде

$C^{m}=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }$

где $q_{\ell }$ количество кодовых слов в $S^{m}$ длины $\ell$ и $\ell _{max}$ длина самого длинного кодового слова в $S$. Для $r$-буквенный алфавит есть только $r^{\ell }$ возможные слова длины $\ell$, так $q_{\ell }\leq r^{\ell }$. Используя это, мы определяем верхнюю границу $C^{m}$:

${\begin{aligned}C^{m}&=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }\\&\leq \sum _{\ell =1}^{m\cdot \ell _{max}}r^{\ell }\,r^{-\ell }=m\cdot \ell _{max}\end{aligned}}$

Принимая $m$-й корень, получаем

$C=\sum _{i=1}^{n}r^{-l_{i}}\leq \left(m\cdot \ell _{max}\right)^{\frac {1}{m}}$

Эта оценка справедлива для любого $m\in \mathbb {N}$. Правая часть асимптотически равна 1, поэтому $\sum _{i=1}^{n}r^{-l_{i}}\leq 1$ должно выполняться (иначе неравенство было бы нарушено для достаточно большого $m$).

Альтернативная конструкция обратного

Учитывая последовательность $n$ натуральные числа,

$\ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}$

удовлетворяя неравенству Крафта, мы можем построить префиксный код следующим образом. Определи я ^й кодовое слово C _i , которое будет первым $\ell _{i}$ цифры после точки системы счисления (например, десятичной точки) в по основанию r представлении

$\sum _{j=1}^{i-1}r^{-\ell _{j}}.$

Обратите внимание, что согласно неравенству Крафта эта сумма никогда не превышает 1. Следовательно, кодовые слова отражают все значение суммы. Следовательно, при j > i первый $\ell _{i}$ цифры C _j образуют большее число, чем C _i , поэтому код не содержит префиксов.

Обобщения

Следующее обобщение содержится в.

Теорема — Если ${\textstyle C,D}$ однозначно декодируются, и каждое кодовое слово в ${\textstyle C}$ представляет собой объединение кодовых слов в ${\textstyle D}$, затем $$\sum _{c\in C}r^{-|c|}\leq \sum _{c\in D}r^{-|c|}$$

Предыдущая теорема представляет собой частный случай, когда $D=\{a_{1},\dots ,a_{r}\}$.

Доказательство

Позволять ${\textstyle Q_{C}(x)}$ быть производящей функцией кода. То есть, $$Q_{C}(x):=\sum _{c\in C}x^{|c|}$$

По счетному аргументу, ${\textstyle k}$-й коэффициент ${\textstyle Q_{C}^{n}}$ количество строк длины ${\textstyle n}$ с длиной кода ${\textstyle k}$. То есть, $$Q_{C}^{n}(x)=\sum _{k\geq 0}x^{k}\#({\text{strings of length }}n{\text{ with }}C{\text{-codes of length }}k)$$ Сходным образом,
$${\frac {1}{1-Q_{C}(x)}}=1+Q_{C}(x)+Q_{C}(x)^{2}+\cdots =\sum _{k\geq 0}x^{k}\#({\text{strings with }}C{\text{-codes of length }}k)$$

Поскольку код однозначно декодируется, любая степень ${\textstyle Q_{C}}$ абсолютно ограничен ${\textstyle r|x|+r^{2}|x|^{2}+\cdots ={\frac {r|x|}{1-r|x|}}}$, поэтому каждый из ${\textstyle Q_{C},Q_{C}^{2},\dots }$ и ${\textstyle {\frac {1}{1-Q_{C}(x)}}}$ аналитичен на диске ${\textstyle |x|<1/r}$.

Мы утверждаем, что для всех ${\textstyle x\in (0,1/r)}$, $$Q_{C}^{n}\leq Q_{D}^{n}+Q_{D}^{n+1}+\cdots$$

Левая сторона $$\sum _{k\geq 0}x^{k}\#({\text{strings of length }}n{\text{ with }}C{\text{-codes of length }}k)$$ и правая сторона

$$\sum _{k\geq 0}x^{k}\#({\text{strings of length}}\geq n{\text{ with }}D{\text{-codes of length }}k)$$

Теперь, поскольку каждое кодовое слово в ${\textstyle C}$ представляет собой объединение кодовых слов в ${\textstyle D}$, и ${\textstyle D}$ однозначно декодируется, каждая строка длины ${\textstyle n}$ с ${\textstyle C}$-код ${\textstyle c_{1}\dots c_{n}}$ длины ${\textstyle k}$ соответствует уникальной строке ${\textstyle s_{c_{1}}\dots s_{c_{n}}}$ чей ${\textstyle D}$-код ${\textstyle c_{1}\dots c_{n}}$. Строка имеет длину не менее ${\textstyle n}$.

Следовательно, коэффициенты слева меньше или равны коэффициентам справа.

Таким образом, для всех ${\textstyle x\in (0,1/r)}$, и все ${\textstyle n=1,2,\dots }$, у нас есть $$Q_{C}\leq {\frac {Q_{D}}{(1-Q_{D})^{1/n}}}$$ принимая ${\textstyle n\to \infty }$ предел, у нас есть ${\textstyle Q_{C}(x)\leq Q_{D}(x)}$ для всех ${\textstyle x\in (0,1/r)}$.

С ${\textstyle Q_{C}(1/r)}$ и ${\textstyle Q_{D}(1/r)}$ оба сходятся, мы имеем ${\textstyle Q_{C}(1/r)\leq Q_{D}(1/r)}$ взяв предел и применив теорему Абеля .

Существует обобщение квантового кода .

Ссылки

• Крафт, Леон Г. (1949), Устройство для квантования, группировки и кодирования амплитудно-модулированных импульсов (Диссертация), Кембридж, Массачусетс: Диссертация магистра, факультет электротехники, Массачусетский технологический институт , hdl : 1721.1/12390 .

• Макмиллан, Броквей (1956), «Два неравенства, подразумеваемые уникальной дешифруемостью», IEEE Trans. Инф. Теория , 2 (4): 115–116, doi : 10.1109/TIT.1956.1056818 .

См. также

• постоянная Чайтина
• Канонический код Хаффмана