Задание №4 — Префиксные коды, условие Фано
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны:
| А | 000 |
| Б | 001 |
| В | 0101 |
| Г | 0100 |
| Д | 011 |
| Е | 101 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Правильный ответ
5
Пояснение
Решение:
Условие Фано означает, что ни одно кодовое слово не является началом другого. Удобно представлять коды как пути в двоичном дереве: занятое кодовое слово «закрывает» всю ветку под собой, и новые слова можно брать только из свободных веток.
Разберём ветку, начинающуюся с нуля. Под словом 00 стоят оба возможных продолжения — 000 (А) и 001 (Б); под словом 010 — оба продолжения 0100 (Г) и 0101 (В); само слово 011 занято буквой Д. Значит вся ветка 0 закрыта полностью, свободных слов в ней нет.
В ветке, начинающейся с единицы, занято только слово 101 (Е). Слово 10 брать нельзя — оно является началом кода 101, а вот слово 100 свободно, и свободна вся ветка 11. Коротких слов длины 2 всего четыре: 00 — начало кодов А и Б, 01 — начало кодов В, Г и Д, 10 — начало кода Е, и только 11 не конфликтует ни с чем.
Поэтому одну из букв кодируем словом 11 длиной 2 знака, а короче двух знаков для второй буквы уже ничего не остаётся: все однобуквенные слова 0 и 1 являются началами занятых кодов, а единственное свободное слово длины 2 мы уже использовали. Ближайшее свободное слово для второй буквы — 100 длиной 3 знака (оно не начинается с 11 и не является началом ни одного из известных кодов). Суммарная длина равна .
Тот же ответ даёт полный перебор пар кодовых слов:
from itertools import product
known = ['000', '001', '0101', '0100', '011', '101']
def fano(codes):
return all(i == j or not codes[j].startswith(codes[i])
for i in range(len(codes)) for j in range(len(codes)))
best = 99
for n1 in range(1, 6):
for n2 in range(1, 6):
for p in product('01', repeat=n1):
for q in product('01', repeat=n2):
zh, ze = ''.join(p), ''.join(q)
if zh != ze and fano(known + [zh, ze]):
best = min(best, n1 + n2)
print(best)
Ответ: 5