Теория
В неравномерном коде разные буквы кодируются словами разной длины: частые буквы получают короткие коды, редкие — длинные. Такой код компактнее равномерного, но у него есть опасность: цепочка из нулей и единиц должна разбираться на слова однозначно, без разделителей. Эту гарантию даёт условие Фано: ни одно кодовое слово не является началом другого. Тогда, читая цепочку слева направо, мы в первый же момент, когда прочитанные биты совпали с кодовым словом, точно знаем, что это очередная буква.
Набор слов, для которого условие выполнено, называют префиксным кодом. У него есть удобная числовая проверка — неравенство Крафта: сумма \(2^{-l_i}\) по всем словам не превосходит 1, где \(l_i\) — длина слова. Сумма меньше единицы означает, что в дереве кодов остались свободные ветви и код можно дополнить новым словом. Если сумма равна единице, код полный: добавить слово, не нарушив условие Фано, уже нельзя.
Кратчайшее допустимое слово ищут перебором по возрастанию длины: проверяют слова 0, 1, 00, 01, 10, 11 и так далее, отбрасывая те, что начинаются с существующего слова или сами являются началом другого.
Важно: условие Фано — достаточное, но не обязательное условие однозначности. Существуют коды без префиксного свойства, которые всё же декодируются однозначно, но в школьных задачах проверяют именно условие Фано.
Пример с решением
- Условие. Для букв А, Б, В использованы кодовые слова 0, 110 и 100. Найдите кратчайшее кодовое слово для новой буквы Г, чтобы условие Фано сохранилось.
- Что занято. Слово 0 закрывает все слова, начинающиеся с 0. Слова 110 и 100 закрывают свои продолжения.
- Перебор по длине. Длина 1: слово 1 — начало слова 110, не подходит. Длина 2: 10 — начало слова 100, 11 — начало слова 110, оба заняты.
- Свободное слово. Длина 3: 100 и 110 заняты, а 101 не начинается ни с одного слова и не является началом другого — подходит.
- Проверка. Сумма Крафта была \(0{,}5 + 0{,}125 + 0{,}125 = 0{,}75\), с новым словом стала \(0{,}75 + 0{,}125 = 0{,}875\), то есть не больше единицы.
- Ответ. Кратчайшее слово — 101. В калькуляторе это режим «Найти кратчайшее новое слово» со списком «0», «110», «100».
Главное
- Условие Фано: ни одно кодовое слово не является началом другого.
- Следствие: цепочка декодируется слева направо однозначно, без разделителей.
- Неравенство Крафта: сумма \(2^{-l_i}\) не больше 1; равенство — код полный.
- Поиск нового слова: перебираем слова по возрастанию длины и берём первое свободное.