Задание 4 КЕГЭ (условие Фано): как понять, что один код можно сделать короче?
В задании 4 даны коды нескольких букв, и для одной буквы код неизвестен — надо подобрать минимальную длину так, чтобы выполнялось условие Фано (ни один код не является началом другого). Я понимаю формулировку, но не понимаю, как реально подбирать. С чего начинать?
2 ответа
Условие Фано: никакой код не должен быть префиксом (началом) другого кода. Это нужно, чтобы цепочку битов можно было однозначно разбить на буквы.
План решения:
- Выпиши известные коды, например:
A=0,B=10,C=110. - Построй мысленно (или на бумаге) двоичное дерево: каждый код — путь от корня (0 — влево, 1 — вправо). Буква "садится" в узел.
- Условие Фано выполнено, когда все буквы сидят только в листьях — ни одна не лежит на пути к другой.
- Для новой буквы ищи самый короткий свободный путь, который не проходит через уже занятый код и через который не проходят к другим.
Для примера выше: 0 занято, всё что начинается с 0 — запрещено. 10 занято. 110 занято. Свободно 111 (длина 3) и короче не получится, потому что 11 ведёт к 110. Значит минимум — 3 бита.
Главная мысль: рисуй дерево, а не перебирай вслепую.
Короткий практический приём без дерева: возьми все известные коды и проверяй кандидатов по возрастанию длины. Кандидат длины L подходит, если он не начинается ни с одного известного кода И ни один известный код не начинается с него. Первая длина, для которой такой кандидат вообще существует, и есть ответ. Для длины 1 кандидаты 0 и 1, для длины 2 — 00 01 10 11 и т.д. Перебор маленький, на бумаге быстро.