Определение
Префиксный код — это набор кодов (например, двоичных кодов букв), в котором ни один код не является началом другого кода. Это требование называют условием Фано. Благодаря ему закодированное сообщение можно записать сплошной строкой, без пробелов и разделителей, и всё равно раскодировать его однозначно.
Ключевые признаки
- Запрещено только начало — код не может совпадать с началом другого кода; стоять в конце или в середине другого кода можно: коды 01 и 101 друг другу не мешают
- Разная длина кодов — префиксный код бывает неравномерным: А — 1, Б — 01, В — 00
- Без разделителей — сообщение записывают сплошной строкой из нулей и единиц, а границы между кодами находятся при чтении
- Чтение слева направо — цифры набирают по одной, пока набранное не совпадёт с кодом из таблицы; тогда выписывают букву и начинают набор заново
Пример
Коды: А — 0, Б — 10, В — 110, Г — 111. Ни один код не является началом другого, значит, код префиксный. Раскодируем 100110111, набирая цифры слева направо: 10 → Б, 0 → А, 110 → В, 111 → Г. Получается БАВГ, и другого способа разрезать эту строку на коды нет.
Тема целиком: Кодирование информации — теория, разобранные задания и тренажёр.
Не путай: Префиксный код и равномерный код
В равномерном коде все коды одной длины, и строку просто режут на равные куски. В префиксном коде длины бывают разными, важно лишь, чтобы ни один код не был началом другого. Равномерный код из разных кодов всегда префиксный, а префиксный не обязательно равномерный.
Частые вопросы
Что такое префиксный код простыми словами (для 7–9 класса)?
Префиксный код — это набор кодов (например, двоичных кодов букв), в котором ни один код не является началом другого кода. Это требование называют условием Фано. Благодаря ему закодированное сообщение можно записать сплошной строкой, без пробелов и разделителей, и всё равно раскодировать его однозначно.
Как префиксный код выглядит на практике?
Коды: А — 0, Б — 10, В — 110, Г — 111. Ни один код не является началом другого, значит, код префиксный. Раскодируем 100110111, набирая цифры слева направо: 10 → Б, 0 → А, 110 → В, 111 → Г. Получается БАВГ, и другого способа разрезать эту строку на коды нет.
В каких заданиях ОГЭ встречается «префиксный код»?
В заданиях на знание понятий информатики — потренируйся в тренажёре Совелия.