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

Представьте, что вам нужно передать другу секретное сообщение, но есть только два символа: 0 и 1. Никаких букв, никаких пробелов, никаких знаков препинания. Только бесконечная лента из нулей и единиц. Как быть?

Первое, что приходит в голову — придумать таблицу, где каждой букве соответствует свой набор из нулей и единиц. Например:

Отлично, но букв в алфавите гораздо больше двух. Значит, коды будут длиннее:

Теперь можно закодировать слово «БАГА»: 01 + 00 + 11 + 00 = 01001100. Красиво! Но вот беда: у нас всего четыре буквы, а хочется закодировать весь алфавит. Придётся делать коды длиннее — например, по пять бит на букву. Это работает, но получается очень длинно: каждая буква занимает целых пять символов.

А что, если сделать коды разной длины? Частым буквам — короткие, редким — длинные. Тогда сообщение станет короче. Но тут же возникает новая проблема, и она гораздо интереснее.

Попробуем такой код:

Вроде бы красивый код. А теперь попробуем расшифровать вот это: 0011. Что это? «ААББ»? Или «АГБ»? Или «ВББ»? Да всё сразу. Глядя на строку 0011, невозможно понять, где кончается одна буква и начинается другая.

Вот в чём проблема: код буквы А (0) является началом кода букв В (00) и Г (01). Когда мы читаем сообщение, мы не знаем, остановиться на 0 или подождать ещё один символ. Такие коды — плохие. Они не позволяют однозначно расшифровать сообщение, придётся перебирать все возможные варианты, а это может быть очень долго.

Прежде чем спасти положение, разберёмся с одним словом, а именно со словом «префикс». «Префикс» — это начало слова. У слова «КОТ» префиксы — это «К», «КО» и «КОТ». У слова «ПРИВЕТ» — «П», «ПР», «ПРИ», «ПРИВ», «ПРИВЕ», «ПРИВЕТ».

А теперь главное правило:

Наверное, понятнее было бы, если бы такие коды называли наоборот «непрефиксными», но уж как назвали - так назвали. В нашем плохом примере код буквы А был префиксом кода букв В и Г. Именно поэтому всё и сломалось. Если мы запретим такие ситуации, проблема исчезнет.

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

Самый простой префиксный код выглядит так:

Здесь ни один код не является началом другого. Проверим: 0 не начало 10, 10 не начало 110, 110 не начало 1110. Всё честно. Как это читать? Очень просто. Читаем слева направо и накапливаем символы. Как только накопленное совпало с каким-то кодом из таблицы — это буква, начинаем заново.

Возьмём 1101001110 и расшифруем:

• 1 — пока не буква.
• 11 — пока не буква.
• 110 — это В! Записываем, начинаем заново.
• 1 — не буква.
• 10 — это Б! Записываем.
• 0 — это А!
• 1, 11, 111, 1110 — это Г!

Получилось: В Б А Г. Всё однозначно, никаких пробелов не нужно. Почему этот код работает? Потому что нолик в конце играет роль точки. Мы ставим единички, пока считаем, а нолик говорит: «Стоп, буква закончилась». Чем дальше буква в алфавите, тем больше единичек перед ноликом.

Ещё один красивый код — он умеет сам подсказывать, как себя читать:

Здесь работает такой принцип: сначала идут нули — это подсказка. Надо посчитать нули, прибавить один — и тогда узнаешь, сколько всего символов в числе. А потом идёт само число, записанное в двоичном виде.

Например, 00101. Считаем нули в начале: два нуля. Прибавляем один: три символа. Значит, само число — это следующие три символа: 101. А 101 в двоичной системе — это 5. Или, такой код: 0001000. Три нуля в начале, плюс один — четыре символа. Следующие четыре символа: 1000. Это 8 в двоичной системе.

Код Элиаса хорош тем, что он очень логичен. Им удобно кодировать числа — а значит, и буквы, если заранее договориться, что каждой букве соответствует своё число.

Может показаться, что это просто игра ума. Но префиксные коды — не игрушка, а рабочий инструмент, на котором держится вся современная цифровая жизнь.

• Файлы MP3 сжимают музыку с помощью префиксных кодов.
• Картинки JPEG и видео MP4 тоже.
• Архивы ZIP и формат PNG используют их же.
• Интернет-трафик во многом устроен так же.

Идея везде одна: дать частым символам короткие коды, а редким — длинные. Тогда сообщение в среднем становится короче. А чтобы его можно было прочитать без пробелов, коды делают префиксными.

Самый знаменитый из таких кодов придумал в 1952 году американский математик Дэвид Хаффман. Он называется кодом Хаффмана и до сих пор используется почти везде — от сжатия фотографий до передачи данных по сети.

Есть ещё интересный префиксный код – код Фибоначчи. Он построен на одном интересном факте: любое число можно единственным способом собрать из непоследовательных чисел Фибоначчи.

На самом деле префиксных кодов бесконечно много. Для одного и того же алфавита и одного и того же набора вероятностей символов можно построить разные префиксные коды с разной средней длиной кодового слова. Можно это вообще сделать «вручную». Нарисовать дерево: корень, от него две ветки — 0 и 1. На каждой ветке снова развилка 0-1. И так далее. Буквы надо «сажать» только на самые концы веток — никогда в середину. И тогда «путь» до каждой буквы и получится префиксным кодом. Так как буквы можно сажать «по-разному», на разные листья этого дерева, то таких кодов может быть очень много.

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

В общем, это уже сложно для понимания, главное, что стоит запомнить:

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

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