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

 

Формальное определение

Код $C$ над алфавитом (например, ${0,1}$) называется беспрефиксным, если

$$ \forall x, y \in C, x \neq y \implies x \text{ не является префиксом } y. $$

 

Примеры

  • Корректный беспрефиксный набор: $\lbrace 0, 10, 11 \rbrace$
  • Корректный беспрефиксный набор: $\lbrace 00, 01, 10, 11 \rbrace$
  • Некорректный набор: $\lbrace 0, 01, 10 \rbrace$ , так как $“0”$ является префиксом $“01”$.

 

Почему это важно

  • Мгновенное декодирование: как только вы распознали кодовое слово, оно считается завершённым — нет необходимости читать дополнительные биты.
  • Простота реализации: деревообразные кодировщики и расшифровщики напрямую соответствуют бинарному дереву.

 

Типы беспрефиксных кодов

  • Код фиксированной длины — каждому символу исходного алфавита назначается кодовое слово одинаковой длины.
  • Код переменной длины — длина кодовых слов варьируется в зависимости от частоты символов: более частые символы получают более короткие коды, а редкие — более длинные.

Last updated 09 мая 2025, 23:43 +0500 . history