В теории кодирования , то неравенство крафт-McMillan дает необходимое и достаточное условие существования кода префикса [1] (в Leon G. Крафта версия) или однозначно декодируемыми код (в Brockway McMillan версии «s) для заданного набора из кодового слова длины. Его приложения к префиксным кодам и деревьям часто находят применение в информатике и теории информации .
Неравенство Крафт было опубликовано в Kraft (1949) . Однако в статье Крафт обсуждаются только префиксные коды, а анализ, приводящий к неравенству, приписывается Раймонду Редхефферу . Результат был независимо открыт Макмилланом (1956) . Макмиллан доказывает результат для общего случая однозначно декодируемых кодов и приписывает версию для префиксных кодов устному наблюдению Джозефа Лео Дуба в 1955 году .
Приложения и интуиция
Неравенство Крафт ограничивает длину кодовых слов в префиксном коде : если взять экспоненту длины каждого действительного кодового слова, результирующий набор значений должен выглядеть как функция вероятности массы , то есть его общая мера меньше или равна к одному. Неравенство Крафт можно рассматривать с точки зрения ограниченного бюджета, который должен быть потрачен на кодовые слова, при этом более короткие кодовые слова обходятся дороже. К полезным свойствам, вытекающим из неравенства, можно отнести следующие утверждения:
- Если неравенство Крафт выполняется со строгим неравенством, код имеет некоторую избыточность .
- Если неравенство Крафт выполняется с равенством, рассматриваемый код является полным кодом. [2]
- Если неравенство Крафт не выполняется, код не является однозначно декодируемым .
- Для каждого уникально декодируемого кода существует префиксный код с одинаковым распределением длины.
Официальное заявление
Пусть каждый исходный символ из алфавита
быть закодированным в однозначно декодируемый код по алфавиту размера с длинами кодовых слов
потом
И наоборот, для данного набора натуральных чисел удовлетворяющий указанному выше неравенству, существует однозначно декодируемый код над алфавитом размера с такой длиной кодового слова.
Пример: бинарные деревья
Любое двоичное дерево можно рассматривать как определение префиксного кода для листьев дерева. Неравенство Крафт утверждает, что
Здесь сумма берется по листьям дерева, то есть узлам без дочерних элементов. Глубина - это расстояние до корневого узла. В дереве справа эта сумма равна
Доказательство
Доказательство префиксных кодов
Сначала покажем, что неравенство Крафт выполняется всякий раз, когда код для это префиксный код.
Предположим, что . Позволять быть полным -арное дерево глубины (таким образом, каждый узел на уровне имеет дети, а узлы на уровне листья). Каждое слово длины над -арный алфавит соответствует узлу в этом дереве на глубине . Вое слово в коде префикса соответствует узлу; позволять быть набором всех листовых узлов (т.е. узлов на глубине ) в поддереве укорененный в . Это поддерево имеет высоту, у нас есть
Поскольку код является префиксным, эти поддеревья не могут иметь общих листьев, что означает, что
Таким образом, учитывая, что общее количество узлов на глубине является , у нас есть
из чего следует результат.
И наоборот, для любой упорядоченной последовательности натуральные числа,
удовлетворяющий неравенству Крафт, можно построить префиксный код с длинами кодовых слов, равными каждому выбрав слово длины произвольно, затем исключая все слова большей длины, которые имеют его в качестве префикса. Здесь мы снова будем интерпретировать это в терминах листовых узлов-арное дерево глубины . Сначала выберите любой узел из полного дерева на глубине; это соответствует первому слову нашего нового кода. Поскольку мы строим префиксный код, все потомки этого узла (т. Е. Все слова, у которых есть это первое слово в качестве префикса) становятся непригодными для включения в код. Мы рассматриваем потомков в глубине(т.е. листовые узлы среди потомков); Существуюттакие узлы-потомки, которые удаляются из рассмотрения. Следующая итерация выбирает (уцелевший) узел на глубине и удаляет дальнейшие листовые узлы и так далее. После итераций мы удалили в общей сложности
узлы. Вопрос в том, нужно ли нам удалить больше листовых узлов, чем у нас есть на самом деле.в целом - в процессе построения кода. Поскольку выполняется неравенство Крафт, действительно
и таким образом может быть построен префиксный код. Обратите внимание, что, поскольку выбор узлов на каждом шаге в значительной степени произвольный, в целом может быть построено множество различных подходящих префиксных кодов.
Доказательство общего случая
Теперь докажем, что неравенство Крафт выполняется всякий раз, когда является уникально декодируемым кодом. (Обратное утверждение не нужно доказывать, поскольку мы уже доказали это для префиксных кодов, что является более сильным утверждением.)
Обозначить . Идея доказательства состоит в том, чтобы получить верхнюю оценку на для и показать, что это может быть справедливо только для всех если . Переписать в виде
Рассмотрим все m -степени , в виде слов , где индексы от 1 до . Обратите внимание: поскольку предполагалось, что S однозначно декодируется, подразумевает . Это означает, что каждому слагаемому соответствует ровно одно слово в. Это позволяет нам переписать уравнение в виде
где количество кодовых слов в длины а также это длина самого длинного кодового слова в . Для-буквенный алфавит есть только возможные слова длины , так . Используя это, мы оцениваем сверху:
Принимая -й корень, получаем
Эта оценка верна для любого . Правая часть асимптотически равна 1, поэтому должно выполняться (иначе неравенство было бы нарушено для достаточно большого ).
Альтернативная конструкция для обратного
Учитывая последовательность натуральные числа,
удовлетворяющий неравенству Крафт, мы можем построить префиксный код следующим образом. Определите i- е кодовое слово, C i , как первоецифры после точки поразрядной (например , десятичной точки) в базовой г представлении
Обратите внимание, что по неравенству Крафт эта сумма никогда не превышает 1. Следовательно, кодовые слова фиксируют все значение суммы. Следовательно, при j > i первыецифры C j образуют большее число, чем C i , поэтому код не содержит префиксов.
Заметки
- ^ Обложка, Томас М .; Томас, Джой А. (2006), "Сжатие данных", Элементы теории информации (2 - е изд.), John Wiley & Sons, Inc, стр 108-109,. Дои : 10.1002 / 047174882X.ch5 , ISBN 978-0-471-24195-9
- ^ Де Рой, Стивен; Грюнвальд, Питер Д. (2011), «УДАЧА И Сожаление в МИНИМАЛЬНОМ ВЫВОДЕ ДЛИНЫ ОПИСАНИЯ», Философия статистики (1-е изд.), Elsevier, p. 875, ISBN 978-0-080-93096-1
Рекомендации
- Крафт, Леон Г. (1949), Устройство для квантования, группировки и кодирования амплитудно-модулированных импульсов , Кембридж, Массачусетс: диссертация магистра, кафедра электротехники, Массачусетский технологический институт , hdl : 1721.1 / 12390.
- Макмиллан, Броквей (1956), «Два неравенства, вытекающие из уникальной дешифрируемости», IEEE Trans. Инф. Теория , 2 (4): 115-116, DOI : 10,1109 / TIT.1956.1056818.