Нерівність Крафта — Макміллана

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

У теорії кодування нерівність Крафта - Макміллана дає необхідну і достатню умову існування роздільних і префіксних кодів з заданим набором довжин кодових слів.

Попередні визначення

[ред. | ред. код]

Нехай задано дві довільно кінцеві множини, які називаються, відповідно, кодованим алфавітом і кодуючим алфавітом. Їх елементи називаються символами, а рядки (послідовності кінцевої довжини) символів — словами. Довжина слова — це кількість символів, з якого воно складається.

Як кодуючий алфавіт часто розглядається множина {0;1} — так званий двійковий або бінарний алфавіт.

Схемою алфавітного кодування (або просто (алфавітним) кодом) називається будь-яке відображення символів кодованого алфавіту в слова кодуючого алфавіту, які називають кодовими словами. Користуючись схемою кодування, кожне слово кодованого алфавіту можна зіставити з його кодом — конкатенацією кодових слів, що відповіднає кожному символу цього слова.

Код називається роздільним (або однозначно декодованим), якщо жодним двом словам кодованого алфавіту не може бути зіставлений один і той же код.

Префіксним кодом називається алфавітний код, в якому жодне з кодових слів не є префіксом жодного іншого кодового слова. Будь-який префіксний код є роздільним.

Формулювання

[ред. | ред. код]

Нехай задані кодований і кодуючий алфавіти, що складаються з n і d символів, відповідно, і задані бажані довжини кодових слів: . Тоді необхідною і достатньою умовою існування роздільного і префіксного кодів, що володіють заданим набором довжин кодових слів, є виконання нерівності:

Ця нерівність і відома під назвою нерівності Крафта — Макміллана. Вперше вона була виведена Леоном Крафтом в своїй магістерській дипломній роботі в 1949 році, проте він розглядав лише префіксні коди, тому при обговоренні префіксних код цю нерівність часто називають просто нерівністю Крафта. У 1956 році Броквей Макміллан довів необхідність і достатність цієї нерівності для загальнішого класу кодів — роздільних кодів.

Приклад

[ред. | ред. код]

Кореневе двійкове дерево - це таке дерво, в якому кожен вузол, що не є листом, має два і тільки два нащадки.

Будь-яке вкорінене двійкове дерево можна розглядати як графічний опис префіксного коду над двійковим алфавітом: символи кодованого алфавіту відповідають листам дерева, а шлях в дереві від кореня до листа задає його код (шлях складається з послідовності рухів «ліворуч» і «праворуч», які відповідають символам 0 і 1).

Для таких дерев нерівність Крафта — Макміллана стверджує, що:

де  — множина листів дерева, а  — глибина листка , тобто кількість ребер на шляху від кореня до кінцевої вершини (листа) .

Приклад: Двійкове дерево
Рис 1: Двійкове дерево


Розглянемо дерево на Рис 1.

Для 4 листків маємо глибину - 3, а для вузла із значенням 76 глибина рівна 2, таким чином маємо нерівність:

Література

[ред. | ред. код]

Посилання

[ред. | ред. код]