Условие Фано: префиксные коды
Коротко
Код удовлетворяет условию Фано, если ни одно кодовое слово не является началом другого. Такой код однозначно декодируется. Удобно строить двоичное дерево: кодовые слова — листья, ни одно слово не может лежать на пути к другому. Чтобы найти кратчайший код для новой буквы, ищут свободную ветку дерева минимальной длины.
Условие Фано
Ни одно кодовое слово не является началом (префиксом) другого.
Пример: {0, 10, 110, 111} — подходит. {0, 01} — не подходит: 0 — начало 01.
Дерево
- Каждое кодовое слово — лист.
- Узел, где уже стоит слово, нельзя продолжать.
- Свободная ветка — место для нового слова.
Пример
А — 0, Б — 10, В — 110. Свободна только ветка 111 (и её продолжения). Кратчайший код для Г — 111, длина 3.
Типичные ошибки
- Проверяют только «соседние» коды, а не все пары.
- Забывают, что требование может быть и к обратному условию Фано (ни одно слово не является концом другого).
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 4
Пример 1 из 2
Буквы А — 0, Б — 10, В — 110. Какой кратчайший код можно дать букве Г?
- Разбор
- Ветки 0, 10, 110 заняты; свободна 111.
- Ответ
- 111
Пример 2 из 2
Удовлетворяет ли условию Фано код {1, 01, 001, 000}?
- Разбор
- Ни одно слово не является началом другого.
- Ответ
- Да
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Что требует условие Фано?
Показать ответ
Ответ: Ни одно слово не является началом другого.
Префиксный код.
- Вопрос 2 из 5
Подходит ли {0, 01}?
Показать ответ
Ответ: Нет.
0 — начало 01.
- Вопрос 3 из 5
Зачем условие Фано?
Показать ответ
Ответ: Для однозначного декодирования.
Без разделителей.
- Вопрос 4 из 5
Как удобно искать свободный код?
Показать ответ
Ответ: Деревом.
Слова — листья.
- Вопрос 5 из 5
Можно ли продолжать ветку, где уже есть слово?
Показать ответ
Ответ: Нет.
Иначе слово станет префиксом.
Проверьте всё задание 4, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти