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

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

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

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

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

А можно ли ещё короче? Попробуем на практике. Возьмём «алфавит» из 32 символов, чтобы влезть в длину кода 5 бит (`2^5=32`). На каждый символ придётся ровно по 5 бит, поэтому разделители не нужны. Длина зашифрованного текста в битах считается очень легко: ДлинаФразы*5.

Если нам надо зашифровать «У ЛУКОМОРЬЯ ДУБ ЗЕЛЁНЫЙ ЗЛАТАЯ ЦЕПЬ НА ДУБЕ ТОМ», то у нас должно получиться кодированное сообщение в 47*5=235 бит. Это намного круче, чем обычное кодирование 8-битными кодами, где получилось бы 47*8=376 бит. Но можно ли ещё укоротить результат без потери информации?

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

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

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

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

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

«Префикс» — это часть слова с его начала. Например, у слова «ПРИВЕТ» префиксы — «П», «ПР», «ПРИ», «ПРИВ», «ПРИВЕ», «ПРИВЕТ», у слова «МИР» префиксы — «М», «МИ» и «МИР».

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

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

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

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

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

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

Получилось: ВБАГ. Всё однозначно, никаких пробелов не нужно. Почему этот код работает? Потому что нолик в конце играет роль точки. Перебираем коды, пока нам встречаются единички, а как только встретили нолик – «стоп, буква закончилась». Очень красивый и простой код, действительно напоминающий лестницу с кучей ступенек.

Минус «лестницы» в том, что длина каждого следующего кода символа увеличивается на 1 бит. Чем дальше буква в алфавите, тем больше единичек перед ноликом. Для последней буквы длина кода будет больше 30 бит и в целом длина зашифрованной фразы получится катастрофически длинной настолько, что с лёгкостью проиграет обычным кодам с «фиксированной» длиной кода. Хотя для короткого словаря выигрыш безусловно будет.

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

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

Например, такой код: 001010001000. Считаем нули в начале: два нуля. Значит, после них нужно прочитать 2+1=3 следующих за ними бита: 101. А 101 в двоичной системе — это 5. Считаем далее: три нуля в начале, плюс один — четыре бита: 1000. Это 8 в двоичной системе. Значит 001010001000 – это 58.

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

Когда-то в разделе про моноалфавитные шифры замены я уже упоминал про частотный анализ. Разные буквы используются в текстах с разной частотой – какие-то чаще, какие-то реже. На основании этого можно расшифровывать простые шифры замены, как это делали герои романов Артура Конан Дойла и Эдгара По. Ниже приведена относительная частота встречаемых в тексте букв русского языка, рассчитанная на базе НКРЯ.

Если самым часто используемым буквам давать короткие коды, а самым редким – длинные, то на этом можно существенно сэкономить. В начале 1950-хх гг аспирант Дэвид Хаффман из Массачусетского технологического института при написании курсовой работы придумал интересный алгоритм, который до сих пор активно применяется в современных цифровых технологиях и базируется как раз на частотности символов. Этот алгоритм так назвали в его честь – алгоритм Хаффмана.

Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Классический алгоритм Хаффмана на входе получает таблицу частотностей символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создаётся их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. Битовые значения ветвей, исходящих от корня, не зависят от весов потомков.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Попробуем построить одно из таких деревьев. За основу возьмём таблицу частот НКРЯ:

Для кодирования текстов надо помимо букв использовать хотя бы какой-то разделитель для слов, иначе текст будет совсем нечитаемым. Поэтому добавим к этому алфавиту пробел между словами (обозначим его «_»), получится 34 символа. Для «красоты» ужмём алфавит до 32 символов, «склеив» пару редких букв с похожими по написанию, а именно Ь с Ъ, и Е с Ё. Это не сильно скажется на читаемости восстановленного текста, но зато позволит сэкономить на длине кода. Также сделаем частоты целыми числами, домножив на 100 и округлив. Пробелу дадим самую высокую вероятность, потому что он фактически встречается в каждом слове (в его конце).

Замечу, что вообще-то я категорически против того, что многие вместо Ё используют Е. Это же разные буквы! Почему бы тогда не пойти дальше и не использовать Ь вместо Ъ, И вместо Й, Ш вместо Щ? Или, скажем, Х вместо Ж. В общем, какая-то странная Ё-дискриминация. Ну да ладно, сейчас не об этом.

Итак, у нас получилась вот такая 32-символьная таблица:

Преобразуем её в вертикальный массив данных и сделаем программку, которая будет строить нам дерево.

<style>
  .huffman-widget { font-family: Consolas, "Courier New", monospace; color: inherit; background: transparent; line-height: 1.4; }
  .huffman-widget__title { font-size: 1.4em; margin: 0 0 0.6em 0; }
  .huffman-widget__subtitle { font-size: 1.1em; margin: 1.2em 0 0.4em 0; }
  .huffman-widget__subsubtitle { font-size: 1em; margin: 1em 0 0.3em 0; }
  .huffman-widget__text { margin: 0.3em 0 0.6em 0; font-size: 14px; }
  .huffman-widget__pre { background: rgba(0, 0, 0, 0.04); border: 1px solid rgba(0, 0, 0, 0.15); border-radius: 6px;
    padding: 12px; overflow-x: auto; white-space: pre; font-size: 13px; line-height: 1.35; overflow-y: auto;
  }
  .huffman-widget__pre--wrap { white-space: pre-wrap; word-break: break-all; max-height: none; }
  .huffman-widget__table { border-collapse: collapse; font-size: 13px; }
  .huffman-widget__table th,
  .huffman-widget__table td { border: 1px solid rgba(0, 0, 0, 0.2); padding: 4px 10px; text-align: left; }
  .huffman-widget__table th { background: rgba(0, 0, 0, 0.06); font-weight: 600; }
  .huffman-widget__sym { color: #c0392b; font-weight: 700; }
  .huffman-widget__bits { font-family: Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.5; }
</style>
 
<div class="huffman-widget">
  <h2 class="huffman-widget__title">Построение дерева Хаффмана</h2>
 
  <h3 class="huffman-widget__subtitle">Шаги слияния</h3>
  <pre class="huffman-widget__pre" data-role="steps"></pre>
 
  <h3 class="huffman-widget__subtitle">Получившееся дерево Хаффмана</h3>
  <pre class="huffman-widget__pre" data-role="tree"></pre>
 
  <h3 class="huffman-widget__subtitle">Кодовая таблица на основе дерева Хаффмана</h3>
  <center>
  <table class="huffman-widget__table" data-role="codes">
    <thead>
      <tr><th>Символ</th><th>Вес</th><th>Код</th></tr>
    </thead>
    <tbody></tbody>
  </table>
  </center>
 
  <h3 class="huffman-widget__subtitle">Пример кодирования</h3>
  <p class="huffman-widget__text" data-role="phrase"></p>
 
  <h4 class="huffman-widget__subsubtitle">Покодированная таблица символов</h4>
  <center>
  <table class="huffman-widget__table" data-role="encoded-table">
    <thead>
      <tr><th>Символ</th><th>Код</th><th>Длина кода</th></tr>
    </thead>
    <tbody></tbody>
  </table>
  </center>
 
  <h4 class="huffman-widget__subsubtitle">Битовая строка</h4>
Выписываем из таблицы все коды по порядку
  <pre class="huffman-widget__pre huffman-widget__pre--wrap" data-role="encoded-bits1"></pre>
и склеиваем в одну строку
  <pre class="huffman-widget__pre huffman-widget__pre--wrap" data-role="encoded-bits"></pre>
 
  <h4 class="huffman-widget__subsubtitle">Итоги</h4>
  <p class="huffman-widget__text" data-role="totals"></p>
</div>
 
(function () {
  const widget = document.querySelector('.huffman-widget');
  function esc(s) { return String(s).replace(/&/g, '&amp;').replace(/</g, '&lt;')
                    .replace(/>/g, '&gt;').replace(/"/g, '&quot;').replace(/'/g, '&#39;');
  }
  function sym(s) { return `<span class="huffman-widget__sym">${esc(s)}</span>`; }
 
  const input = [
    ['_', 2000], ['О', 1098], ['Е', 849], ['А', 800], ['И', 737], ['Н', 670], ['Т', 632], ['С', 547],
    ['Р', 475],  ['В', 453],  ['Л', 434], ['К', 349], ['М', 320], ['Д', 298], ['П', 280], ['У', 262],
    ['Я', 200],  ['Ы', 190],  ['Ь', 178], ['Г', 169], ['З', 164], ['Б', 159], ['Ч', 145], ['Й', 121],
    ['Х', 97],   ['Ж', 94],   ['Ш', 72],  ['Ю', 64],  ['Ц', 49],  ['Щ', 36],  ['Э', 33],  ['Ф', 27]
  ];
 
  let nodes = input.map(([name, weight]) => ({ name, weight, left: null, right: null }));
  let step = 1;
  const stepLines = [];
 
  while (nodes.length > 1) { nodes.sort((a, b) => a.weight - b.weight);
    const left = nodes.shift(); const right = nodes.shift();
    const parent = { name: left.name + right.name, weight: left.weight + right.weight, left, right };
    stepLines.push( `${step}. ` + `${sym(left.name)}(${left.weight}) + ` +
      `${sym(right.name)}(${right.weight}) = ` + `${sym(parent.name)}(${parent.weight})`
    );
    step++;
    nodes.push(parent);
  }
 
  const root = nodes[0];
  const codes = {};
 
  function buildCodes(node, prefix = '') {
    if (!node.left && !node.right) { codes[node.name] = prefix || '0'; return; }
    if (node.left) buildCodes(node.left, prefix + '0');
    if (node.right) buildCodes(node.right, prefix + '1');
  }
  buildCodes(root);
 
  function drawTree(node) {
    const lines = [];
    function walk(n, prefix, isLast, edgeLabel, isRoot) {
      const label = (edgeLabel !== null ? `[${edgeLabel}] ` : '') + `${sym(n.name)}(${n.weight})`;
      if (isRoot) lines.push(label);
      else lines.push(prefix + (isLast ? '└── ' : '├── ') + label);
      const childPrefix = isRoot ? '' : prefix + (isLast ? '    ' : '│   ');
      if (n.left && n.right) { walk(n.left, childPrefix, false, '0', false); walk(n.right, childPrefix, true, '1', false); } 
      else if (n.left) { walk(n.left, childPrefix, true, '0', false); }
      else if (n.right) { walk(n.right, childPrefix, true, '1', false); }
    }
    walk(node, '', true, null, true);
    return lines.join('\n');
  }
 
  widget.querySelector('[data-role="steps"]').innerHTML = stepLines.join('\n');
 
  const tbody = widget.querySelector('[data-role="codes"] tbody');
  for (const [ch, weight] of input) {
    const tr = document.createElement('tr');
    const tdCh = document.createElement('td');
    tdCh.innerHTML = sym(ch);
    const tdWeight = document.createElement('td');
    tdWeight.textContent = weight;
    const tdCode = document.createElement('td');
    tdCode.textContent = codes[ch];
    tr.append(tdCh, tdWeight, tdCode);
    tbody.appendChild(tr);
  }
 
  widget.querySelector('[data-role="tree"]').innerHTML = drawTree(root);
 
  const phrase = 'У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ ЗЛАТАЯ ЦЕПЬ НА ДУБЕ ТОМ';
 
  const phraseHtml = [...phrase].map(ch => ch === ' ' ? '&nbsp;' : sym(ch)).join('');
  widget.querySelector('[data-role="phrase"]').innerHTML = phraseHtml;
 
  const encodedTable = widget.querySelector('[data-role="encoded-table"] tbody');
  const bitsArr = [];
  let unknownChars = new Set();
 
  for (const ch of phrase) {
    const key = ch === ' ' ? '_' : ch; //заменяем пробелы на _, как в кодовой таблице
    const code = codes[key]; if (code === undefined) { unknownChars.add(ch); continue; }
    bitsArr.push(code);
    const tr = document.createElement('tr');
    const tdCh = document.createElement('td'); tdCh.innerHTML = ch === ' ' ? '_' : sym(ch);
    const tdCode = document.createElement('td'); tdCode.textContent = code;
    const tdLen = document.createElement('td'); tdLen.textContent = code.length;
    tr.append(tdCh, tdCode, tdLen);
    encodedTable.appendChild(tr);
  }
 
  const bits = bitsArr.join('');
  const totalBits = bits.length;
  const totalBytes = Math.ceil(totalBits / 8);
 
  widget.querySelector('[data-role="encoded-bits"]').textContent = bits + ` (${totalBits} бит)`;
  const bits1 = bitsArr.join(' ');
  widget.querySelector('[data-role="encoded-bits1"]').textContent = bits1;
 
  let totalsHtml =
    `Фраза: ${phrase} (${phrase.length} символов)<br>` +
    `Длина битовой строки: ${totalBits} бит<br>` +
    `Длина в байтах (с округлением вверх): ${totalBytes} байт`;
 
  if (unknownChars.size > 0) { totalsHtml += `<br><b>Внимание:</b> во фразе встретились символы, ` +
      `отсутствующие в таблице кодов: ` + [...unknownChars].map(c => `«${esc(c)}»`).join(', ');
  }
 
  widget.querySelector('[data-role="totals"]').innerHTML = totalsHtml;
})();

Если фразу «У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ ЗЛАТАЯ ЦЕПЬ НА ДУБЕ ТОМ» кодировать в лоб – по одному байту (8 бит) на символ, то для нашей строки получим 47 байт или 376 бит. А кодом Хаффмана мы её сжали до 221 бита или 28 байт, более чем в полтора раза. Выигрыш получился за счёт того, что частые символы кодируются количеством бит меньшим, чем 8, и к тому же код префиксный, то есть не нужны специальные разделители.

Хочу отметить, что код Хаффмана с длиной закодированного сообщения в 221 бит выигрывает не только у 7- и 8-битных кодовых таблиц, но даже у «идеальной» 5-битной кодовой таблицы, описанной в самом начале, потому что там битовая строка получалась длиной `47*5=235` бит и это казалось круто.

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

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

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

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

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

Так как буквы можно сажать «по-разному», на разные листья этого дерева, то этих кодов реально может быть очень-очень много. А раз их много, то конечно же, сразу встаёт задача выбрать из них самые хорошие Существует целое семейство так называемых оптимальных префиксных кодов — тех, которые минимизируют среднюю длину сообщения при заданных вероятностях (весах) символов. И даже для одного и того же набора весов таких оптимальных кодов тоже может быть несколько. К примеру, некоторые веса могут быть одинаковыми. Или можно вместо «0-слева 1-справа» делать в узлах наоборот «0-справа 1-слева», главное чтобы на каждой развилке одно плечо было 0, а второе 1, а какое из них какое – не важно.

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

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

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