Русская Википедия:Неравенство Крафта — Макмиллана
В теории кодирования, неравенство Крафта — Макмиллана даёт необходимое и достаточное условие существования разделимых и префиксных кодов, обладающих заданным набором длин кодовых слов.
Предварительные определения
Пусть заданы два произвольных конечных множества, которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом. Их элементы называются символами, а строки (последовательности конечной длины) символов — словами. Длина слова — это число символов, из которого оно состоит.
В качестве кодирующего алфавита часто рассматривается множество <math>\{0, 1\}</math> — так называемый двоичный или бинарный алфавит.
Схемой алфавитного кодирования (или просто (алфавитным) кодом) называется любое отображение символов кодируемого алфавита в слова кодирующего алфавита, которые называют кодовыми словами. Пользуясь схемой кодирования, каждому слову кодируемого алфавита можно сопоставить его код — конкатенацию кодовых слов, соответствующих каждому символу этого слова.
Код называется разделимым (или однозначно декодируемым), если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.
Префиксным кодом называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. Любой префиксный код является разделимым.
Формулировка
Это неравенство и известно под названием неравенства Крафта — Макмиллана. Впервые оно было выведено Леоном Крафтом в своей магистерской дипломной работе в 1949 году[1], однако он рассматривал только префиксные коды, поэтому при обсуждении префиксных кодов это неравенство часто называют просто неравенством Крафта. В 1956 году Броквэй Макмиллан доказал необходимость и достаточность этого неравенства для более общего класса кодов — разделимых кодов.[2]
Пример
Двоичные деревья
Любое укоренённое двоичное дерево можно рассматривать как графическое описание префиксного кода над двоичным алфавитом: символы кодируемого алфавита соответствуют листьям дерева, а путь в дереве от корня до листа задаёт его код (путь состоит из последовательности движений «влево» и «вправо», которые соответствуют символам 0 и 1).
Для таких деревьев неравенство Крафта — Макмиллана утверждает, что:
- <math> \sum_{x \in \mathcal{L}} 2^{-\mathrm{depth}(x)} \leqslant 1, </math>
где <math>\mathcal{L}</math> — множество листьев дерева, а <math>\mathrm{depth}(x)</math> — глубина листа <math>x</math>, число рёбер на пути от корня до <math>x</math>.
Для дерева на рисунке справа имеем:
- <math> \frac{1}{4} + 4 \left( \frac{1}{8} \right) = \frac{3}{4} \leqslant 1.</math>
Примечания
Литература
Ссылки
- Kraft’s inequality (NIST) Шаблон:Wayback
- http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Шаблон:Wayback
