Задачи и дополнения

1. Каково минимальное число слов полного двоичного префиксного кода с максимальной длиной L? Какими будут длины кодовых слов такого минимального кода? (Ответы на эти вопросы подсказывает рис. 9.)

Решить те же вопросы в случае d-ичного кода.

2. Доказать, что префиксный код является полным тогда и только тогда, когда в неравенстве Крафта достигается равенство:

Указание. То, что из предыдущего равенства вытекает полнота, очевидно. Для доказательства обратного утверждения следует предположить, что неравенство (6) строгое, Тогда из него выводится строгое же неравенство

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

3. Утверждение предыдущей задачи допускает следующую забавную интерпретацию, являющуюся одновременно и его доказательством (она заимствована из книги [6]).

Рассмотрим дерево, соответствующее полному префиксному коду. Представим себе, что на это дерево взбирается обезьяна. Начав с корня, она наугад выбирает любую из d исходящих из него ветвей; вероятность такого выбора равна 1/d. Добравшись до очередной развилки, обезьяна снова наугад выбирает некоторую ветвь с вероятностью 1/d (напомним, что из каждой промежуточной вершины дерева полного кода исходит ровно d ветвей). Тогда вероятность того, что обезьяна достигнет какой-то определенной концевой вершины, находящейся на высоте k, равна (1/d)^k. Если таких вершин n_k, то с вероятностью n_kd^-k обезьяна остановится на высоте k. На какой-то высоте от 1 до L обезьяне придется остановиться (вероятность этого равна 1). Поэтому

(В приведенном рассуждении мы использовали правила сложения и умножения вероятностей.)

4. Префиксный код с данными длинами кодовых слов может быть построен далеко не единственным способом. Пусть d-ичный префиксный код (не обязательно полный) имеет n_k слов длины k (1 ≤ k ≤ L). Доказать, что число различных таких кодов с фиксированными L и n_k равно произведению

где (ⁱ_j) = C^j_i - число сочетаний из i элементов по j.

Например, число двоичных префиксных кодов с L = 4, n₁ = 0, n₂ = 1, n₃ = 2, n₄ = 4 равно

5. Выше было доказано, что если для чисел l₁, l₂, ..., l_N выполняется неравенство Крафта, то существует префиксный код с длинами l₁, l₂, ..., l_N. Найти этот код можно, строя этаж за этажом его кодовое дерево. Другой более удобный метод решения этой задачи был придуман Шенноном, и (применительно к двоичным кодам) он состоит в следующем.

Пусть числа l₁, l₂, ..., l_N удовлетворяют неравенству

Можно считать, что l₁ ≤ l₂ ≤ ... ≤ l_N. Рассмотрим последовательность чисел

Заметим, что все эти числа заключены в пределах 0 ≤ q < 1, поэтому каждое из них может быть представлено двоичной дробью вида ∑ⁿ_k=1 α_k2^-k, где каждое α_k есть 0 или 1. При этом из (7) можно заключить, что все эти дроби конечны, и двоичная запись для q_j имеет не более l_j значащих цифр. Таким образом, любое число q_j однозначно представимо в виде:

где всякое c_ij есть 0 или 1. Следовательно, каждому q_j однозначно отвечает слово υ_j = c_1jc_2j ... c_ljj длины l_j. Рассмотрим код V = {υ₁, υ₂ ..., υ_N}. Покажем, что он обладает свойством префикса. Пусть υ_j и υ_k два слова (k > j). Тогда, согласно (7), q_k - q_≥j 2^-l_j, а это означает, что l_j-й символ слова υ_j не совпадает с l_j-м символом слова υ_k. Следовательно, υ_j не является началом υ_k, откуда и вытекает префиксность кода V.

Разъясним сказанное на примере. Построим префиксный код с длинами слов l₁ = 1, l₂ = l₃ = 3, l₄ = 4. В этом случае

Двоичная запись этих чисел с нужным числом l_j знаков следующая:

В результате мы получим искомый код:

6. Используя метод Шеннона, найти префиксные коды с указанными ниже длинами слов:

а) l₁ = l₂ = 2; l₃ = l₄ = 3; l₅ = l₆ = l₇ =4;

б) l₁ = 1; l₂ = 2; l₃ = l₄ = l₅ = l₆ = 4.

Построить кодовые деревья для полученных кодов. Определить, какой из этих кодов является полным.