Условие Фано

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 26 · страница 26.1
Условие Фано
Префиксные коды и однозначное декодирование.
Условие Фано
— ключ к однозначному декодированию без разделителей. Ни одно кодовое слово не является префиксом другого.
ФГОС
ОГЭ №2,4
ЕГЭ №4
Связь с главой 25.
Дерево кода — это бинарное дерево из
главы 25 «Деревья»
: листья хранят символы, путь от корня задаёт кодовое слово. Условие Фано = все символы в листьях.
01
Определение
Код
— правило сопоставления каждому символу алфавита кодового слова (битовой строки).
Префиксный код
— ни одно кодовое слово не является префиксом другого. Другое название:
условие Фано
.
Префиксные коды однозначно декодируются
без разделителей
.
Пример префиксного кода
Код {
A=0
,
B=10
,
C=110
,
D=111
}:
0 — не префикс 10, 110, 111 ✓
10 — не префикс 110, 111 ✓
110 — не префикс 111 ✓
Декодирование строки
01101110
: 0→A, 110→C, 111→D, 0→A. Результат:
A C D A
.
Пример НЕпрефиксного кода
Код {
A=0
,
B=01
,
C=011
}:
0 — префикс 01 и 011 ✗
Строку
011
можно декодировать как A+B (0+01) или как C (011) — неоднозначно!
02
Проверка условия Фано
🔍
Проверка кода на префиксность
Коды (формат: A=0;B=10;C=110)
03
Дерево кода
Дерево кода
— корневое бинарное дерево. Каждый лист = символ с его кодом. Каждое ребро = 0 (влево) или 1 (вправо). Путь от корня до листа = кодовое слово.
Все символы префиксного кода находятся в
листьях
дерева.
🌳
Конструктор дерева кода
Коды
04
Неравенство Крафта
Неравенство Крафта
необходимо и достаточно для существования префиксного кода с длинами слов L₁, L₂, ..., Lₙ в d-ичном алфавите:
∑ d
−Li
≤ 1
Для
двоичного
кода (d=2):
∑ 2
−Li
≤ 1   например: 1/2 + 1/4 + 1/4 = 1  ✓
Проверка существования кода
Код с длинами 1, 2, 3, 3: 1/2 + 1/4 + 1/8 + 1/8 = 1 — существует.
Код с длинами 2, 2, 2, 2, 2: 1/4 + 1/4 + 1/4 + 1/4 + 1/4 = 1.25 > 1 — не существует!
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Проверь себя
5 вопросов по условию Фано · 20 XP за каждый правильный ответ