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

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

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

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

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

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

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

быть закодировано в уникально декодируемый код по алфавиту размером с кодовыми словами длиной${\displaystyle r}$

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

Затем

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

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

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

${\displaystyle \sum _{\ell \in {\text{листья}}}2^{-{\text{глубина}}(\ell )}\leqslant 1.}$

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

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

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

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

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

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

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

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

${\displaystyle \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}}}$

из чего следует результат.

И наоборот, если задана любая упорядоченная последовательность натуральных чисел,${\displaystyle n}$

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

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

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

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

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

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

Теперь мы докажем, что неравенство Крафта выполняется, когда — однозначно декодируемый код. (Обратное не требует доказательства, поскольку мы уже доказали это для префиксных кодов, что является более сильным утверждением.) Доказательство принадлежит Джеку И. Карушу. ^{[3] [4]}${\displaystyle S}$

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

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

${\displaystyle {\begin{align}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{align}}}$

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

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

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

${\displaystyle {\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}}}$

Взяв корень степени -, получаем${\displaystyle m}$

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

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

Дана последовательность натуральных чисел,${\displaystyle n}$

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

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

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

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

Следующее обобщение можно найти в ^{[5] .}

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

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

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

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

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