Задание №4. Условие Фано: код без путаницы
Что от тебя хотят
Есть алфавит из нескольких букв. Для некоторых букв коды уже известны. Остальным нужно выдать коды так, чтобы закодированное сообщение, склеенное в одну строку из нулей и единиц, всегда читалось одним способом. Классический вопрос: «какова наименьшая возможная длина закодированного слова».
Когда код читается однозначно
Достаточно выполнить одно из двух условий:
- Прямое условие Фано: ни одно кодовое слово не является началом другого. Читаем слева направо и всегда знаем, где кончилась буква.
- Обратное условие Фано: ни одно кодовое слово не является концом другого. Тогда читаем справа налево.
В условии про «однозначное декодирование» годится любое из двух. Нельзя смешивать: весь набор целиком должен подчиняться одному условию.
Дерево кодов
Рисуем двоичное дерево: из каждого узла идут две ветки, 0 влево и 1 вправо. Каждой букве соответствует свой узел. Для прямого условия буква ставится в конец ветки, и всё, что растёт ниже неё, закрыто. Так видно, какие свободные узлы остались, и какой самый короткий из них.
Разбор 1: прямое условие
Буквам А, Б, В, Г назначены коды А: 00, Б: 010, В: 011, Г: 10. Для букв Д и Е нужно выбрать коды по условию Фано так, чтобы код Д был как можно короче, а среди равных по длине имел наименьшее значение. Какой код у Д?
- Занято: 00, 010, 011 и 10. Ветка 0 закрыта полностью: 00 внизу слева, а 010 и 011 заняты внизу справа.
- Свободная ветка одна:
11. Если отдать её букве Д целиком, для Е ничего не останется. - Значит узел 11 надо разделить:
110и111. - Наименьший по значению из них 110.
Ответ: 110.
Разбор 2: можно и обратное условие
Для букв П, Р, О, Б использовали коды 00, 1001, 0101, 111. Алфавит ещё содержит К, Н и И. Код должен допускать однозначное декодирование. Найдите наименьшую возможную длину закодированного слова КОРОН.
- Слово КОРОН состоит из К, О, Р, О, Н. Известные части: О = 0101 (дважды) и Р = 1001, это 4 + 4 + 4 = 12 бит. Остаётся длина кодов К и Н.
- Свободных кодов длины 2 в прямом режиме нет: ветки 01 и 10 уже заняты (0101 и 1001 растут внутри них). Длины 3 свободны три: 011, 101 и 110. К и Н получат по 3 бита, и всё слово займёт 12 + 6 = 18.
- А теперь обратное условие. В нём ни один код не заканчивается другим. Код
10не заканчивает ни один из известных, и сам не заканчивается на них. Подходит К = 10 (2 бита). Для Н найдём 3 бита:011. Для И подойдёт0001, это не мешает, так как И в слове нет. - Итого 12 + 2 + 3 = 17.
Ответ: 17. Проверено перебором: прямое условие даёт 18, обратное даёт 17.
Разновидности и прототипы задания на экзамене
Код решения на Python
Запустить код в онлайн-песочницеcodes = ["00", "1001", "0101", "111", "10", "011", "0001"]
prefix_ok = True
suffix_ok = True
for a in codes:
for b in codes:
if a != b and b.startswith(a):
prefix_ok = False
if a != b and b.endswith(a):
suffix_ok = False
print(prefix_ok, suffix_ok)from itertools import product
known = ["00", "1001", "0101", "111"]
short = ["".join(p) for n in range(1, 5) for p in product("01", repeat=n)]
long_words = ["".join(p) for n in range(1, 7) for p in product("01", repeat=n)]
best = 100
for k in short:
for n in short:
for i in long_words:
codes = known + [k, n, i]
if len(set(codes)) < 7:
continue
prefix_ok = True
suffix_ok = True
for a in codes:
for b in codes:
if a != b and b.startswith(a):
prefix_ok = False
if a != b and b.endswith(a):
suffix_ok = False
if prefix_ok or suffix_ok:
best = min(best, 12 + len(k) + len(n))
print(best)Типичные ошибки
01, нельзя дать Б код 010: 01 стало бы началом 010.ГРОБ №4: Слово с повторяющимися буквами
В слове «АНАНАС» буква А повторяется три раза, а Н два. Если отдать им одинаковые по длине коды, слово окажется длиннее нужного.
Лайфхаки на экзамене
- При равной длине берут код с наименьшим числовым значением: нули раньше. 100 меньше 101 и 110.
- Проверка на бумаге: сумма 2 в степени минус длина каждого кода не больше единицы (неравенство Крафта). Если больше, кодов не хватит.
- Длину слова считай по буквам с учётом повторов: О в КОРОН входит дважды, и её код тоже дважды.