Префиксные коды и однозначное декодирование.
Условие Фано — ключ к однозначному декодированию без разделителей. Ни одно кодовое слово не является префиксом другого.
Код — правило сопоставления каждому символу алфавита кодового слова (битовой строки).
Префиксный код — ни одно кодовое слово не является префиксом другого. Другое название: условие Фано.
Префиксные коды однозначно декодируются без разделителей.
Код {A=0, B=10, C=110, D=111}:
Декодирование строки 01101110: 0→A, 110→C, 111→D, 0→A. Результат: A C D A.
Код {A=0, B=01, C=011}:
Строку 011 можно декодировать как A+B (0+01) или как C (011) — неоднозначно!
Дерево кода — корневое бинарное дерево. Каждый лист = символ с его кодом. Каждое ребро = 0 (влево) или 1 (вправо). Путь от корня до листа = кодовое слово.
Все символы префиксного кода находятся в листьях дерева.
Неравенство Крафта необходимо и достаточно для существования префиксного кода с длинами слов L₁, L₂, ..., Lₙ в d-ичном алфавите:
Для двоичного кода (d=2):
Код с длинами 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 вопросов по условию Фано · 20 XP за каждый правильный ответ