Задания № 4, 8 · ЕГЭ

Префиксный код

Как распознать код, удобный для однозначного декодирования
2 мин чтенияСложность: Обновлено 29 сентября 2026

Префиксный код — это код, в котором ни одно кодовое слово не является началом другого. Благодаря этому сообщение можно читать слева направо и однозначно определять границы кодовых слов.

Префиксный кодНазвание связано со словом «префикс»: префикс — начальная часть последовательности.
Код, в котором для любых двух различных кодовых слов ни одно не является префиксом, то есть начальной частью, другого. Кодовое слово — последовательность символов кодового алфавита; это понятие полезно повторить на странице кодовое слово.

Как это работает

Если код префиксный, после чтения очередной последовательности символов не возникает ситуации, когда ещё неизвестно: это уже готовое кодовое слово или только начало более длинного. Поэтому декодирование выполняется без разделителей между словами. Префиксный код является важным видом кода и используется в задачах на кодирование информации.

№
Пример

Код \(А\to0\), \(Б\to10\), \(В\to11\) является префиксным. Слово \(0\,11\,10\) однозначно разбирается как \(АВБ\). Ни одно из слов \(0\), \(10\), \(11\) не начинается так же, как другое целиком.

!
Не путайте

Условие префиксности строже, чем просто различие кодовых слов. В коде \(А\to0\), \(Б\to01\) слова различны, но \(0\) является началом \(01\), поэтому такой код не является префиксным. Также префиксный код не обязан иметь кодовые слова одинаковой длины.

Проверка длины кодовых слов

Для двоичного префиксного кода длины кодовых слов \(l_1,l_2,\ldots,l_n\) выполняется неравенство Крафта:

\[\sum_{i=1}^{n}2^{-l_i}\le 1\]

Это необходимое условие существования двоичного префиксного кода с такими длинами. Однако для проверки небольшого кода обычно быстрее сравнить сами кодовые слова: ни одно не должно быть началом другого.

Проверь себя

Какой набор кодовых слов является префиксным?

Главное за минуту

Главное

  • Префиксный код: ни одно кодовое слово не является началом другого.
  • Такой код позволяет однозначно декодировать сообщение без разделителей.
  • Для двоичных длин кодовых слов выполняется неравенство Крафта: \(\sum 2^{-l_i}\le1\).