Задание № 7 · ОГЭ

Код переменной длины

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

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

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

Как читается такой код

В коде переменной длины границы между кодовыми словами не всегда видны сразу. Например, последовательность 010 может означать 0|10, 01|0 или 0|1|0. Поэтому таблицу кодирования составляют так, чтобы получатель мог единственным образом определить границы слов. Удобное условие: ни одно кодовое слово не должно быть началом другого. Такой код называется префиксным.

№
Пример

Пусть символам соответствуют коды: А — 0, Б — 10, В — 11. Код 01011 читается однозначно: 0|10|11, то есть АБВ. Код 0 не является началом кодов 10 и 11, а 10 и 11 не являются началами других слов.

\[L_{\text{ср}}=\frac{\sum_{i=1}^{n} p_i l_i}{\sum_{i=1}^{n} p_i}\]1

В задачах по эффективности кодирования иногда вычисляют среднюю длину кодового слова: \(l_i\) — длина кода символа, а \(p_i\) — число его появлений или вероятность. Код переменной длины позволяет уменьшить среднюю длину, если часто встречающимся символам назначить короткие коды.

!
Не путайте

Переменная длина сама по себе не гарантирует однозначного декодирования. Например, коды А — 0 и Б — 01 образуют неоднозначную систему: последовательность 01 можно прочитать как Б или как АА, если код А повторяется с другими условиями. Для надёжного чтения нужны префиксное свойство, разделители или заранее известные границы.

Проверьте себя

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

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

Главное

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