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

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

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

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

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

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

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

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

{ Displaystyle S = {, s_ {1}, s_ {2}, ldots, s_ {n} , }}

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

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

потом

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что ${ Displaystyle ell _ {1} leqslant ell _ {2} leqslant cdots leqslant ell _ {n}}$ . Позволять ${ displaystyle A}$ быть полным ${ displaystyle r}$ -арное дерево глубины ${ displaystyle ell _ {n}}$ (таким образом, каждый узел ${ displaystyle A}$ на уровне ${ displaystyle < ell _ {n}}$ имеет ${ displaystyle r}$ дети, а узлы на уровне ${ displaystyle ell _ {n}}$ листья). Каждое слово длины ${ Displaystyle ell leqslant ell _ {n}}$ над ${ displaystyle r}$ -арный алфавит соответствует узлу в этом дереве на глубине ${ displaystyle ell}$ . В ${ displaystyle i}$ ое слово в код префикса соответствует узлу ${ displaystyle v_ {i}}$ ; позволять ${ displaystyle A_ {i}}$ быть набором всех листовых узлов (т.е. узлов на глубине ${ displaystyle ell _ {n}}$ ) в поддереве ${ displaystyle A}$ укорененный в ${ 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 _ {я = 1} ^ {n} r ^ { ell _ {n} - ell _ {i}}}

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

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

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

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

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

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

{ 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)} конец {выровнено}}}

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

{ 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 {align} 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 _ { макс} конец {выровнено}}}

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

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

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

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

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

{ Displaystyle ell _ {1} leqslant ell _ {2} leqslant cdots leqslant ell _ {n}}

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

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

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

Примечания

^ Обложка, Томас М .; Томас, Джой А. (2006), «Сжатие данных», Элементы теории информации (2-е изд.), John Wiley & Sons, Inc, стр. 108–109, Дои:10.1002 / 047174882X.ch5, ISBN 978-0-471-24195-9

Смотрите также

[EIT-1] Обложка, Томас М .; Томас, Джой А. (2006), «Сжатие данных», Элементы теории информации (2-е изд.), John Wiley & Sons, Inc, стр. 108–109, Дои:10.1002 / 047174882X.ch5, ISBN 978-0-471-24195-9

[1]