Желание одного студента не сдавать выпускной экзамен привело к появлению вездесущего алгоритма, который сжимает данные, не жертвуя при этом информацией.
Ежедневно по Интернету перемещается более 9 миллиардов гигабайт информации, поэтому исследователи постоянно ищут новые способы сжатия данных в более мелкие пакеты. Передовые методы сосредоточены на подходах с потерями, которые обеспечивают сжатие путем преднамеренной «потери» информации из передачи. Google, например, недавно представила стратегию с потерями, когда компьютер-отправитель пропускает детали изображения, а компьютер-получатель использует искусственный интеллект, чтобы угадать недостающие части. Даже Netflix использует подход с потерями, снижая качество видео всякий раз, когда компания обнаруживает, что пользователь смотрит его на устройстве с низким разрешением.
При этом исследований стратегий сжатия без потерь, при которых можно уменьшить размер данных, не жертвуя содержанием, напротив, проводится очень мало. Причина? Подходы без потерь уже удивительно эффективны. Они используются во всём, от стандарта изображений PNG до вездесущей утилиты PKZip. А всё из-за аспиранта, который просто пытался избежать сложного выпускного экзамена.
Семьдесят лет назад профессор Массачусетского технологического института по имени Роберт Фано предложил студентам своего класса по теории информации выбор: сдать традиционный выпускной экзамен или улучшить передовой алгоритм сжатия данных. Неизвестно, сообщал ли Фано своим ученикам, что являлся автором этого алгоритма и годами искал способ улучшить его. . Что мы знаем наверняка, так это то, что Фано предложил своим ученикам следующую задачу.
Рассмотрим сообщение, состоящее из букв, цифр и знаков препинания. Простым способом кодирования такого сообщения было бы присвоение каждому символу уникального двоичного числа. Например, компьютер может представить букву A как 01000001, а восклицательный знак — как 00100001. В результате получаются коды, которые легко разобрать, – каждые восемь цифр или битов соответствуют одному уникальному символу, но это ужасно неэффективно, поскольку одинаковое количество двоичных цифр используется как для частых, так и для нечастых записей. Лучшим подходом было бы что-то вроде азбуки Морзе, где частая буква E представлена всего одной точкой, тогда как менее распространенная буква Q требует более длинного и трудоемкого тире-тире-точка-тире.
Но азбука Морзе тоже неэффективна. Конечно, некоторые коды короткие, а другие длинные. Но поскольку длина кода различается, сообщения азбукой Морзе нельзя понять, если они не включают короткие периоды тишины между передачей каждого символа. Действительно, без этих дорогостоящих пауз получатели не смогли бы отличить сообщение Морзе тире точка-тире-точка точка-точка тире точка («trite») от тире точка-тире-точка точка-точка-тире точка («true»).
Фано решил эту часть проблемы. Он понял, что может использовать код различной длины без дорогостоящих пробелов, если не задействует один и тот же набор цифр одновременно и в качестве полного кода, и в начале другого кода. Например, если буква S была настолько распространена в определенном сообщении, что Фано присвоил ей очень короткий код 01, то никакая иная буква в этом сообщении не будет кодироваться чем-либо, начинающимся с 01; такие коды, как 010, 011 или 0101, будут запрещены. В результате закодированное сообщение можно было читать слева направо без какой-либо двусмысленности. Например, если букве S присвоить 01, букве A присвоить 000, букве M — 001, а букве L — 1, то сообщение 0100100011 можно сразу перевести как слово «small», даже если L представлено одной цифрой, S – двумя цифрами, а остальные буквы – тремя каждая.
Чтобы определить конкретные коды, Фано построил бинарные деревья, поместив каждую букву в конец ветви. Код каждой буквы определялся путем движения сверху вниз по дереву. Если путь поворачивал налево, Фано добавлял 0; если направо — 1. Древовидная структура позволила Фано избежать нежелательных наложений: когда буква была помещена в дерево, эта ветвь заканчивалась, а это означало, что ни один будущий код не мог начинаться таким же образом.
Дерево Фано для сообщения «encoded». Буква D появляется слева, а затем справа, поэтому она кодируется как 01, а C – справа-справа-слева, 110. Важно отметить, что все ответвления заканчиваются, когда ставится буква.
Чтобы решить, какие буквы куда поместить, Фано мог тщательно протестировать все возможные шаблоны на предмет максимальной эффективности, но это было бы непрактично. Поэтому вместо этого он разработал аппроксимацию: для каждого сообщения он упорядочивал соответствующие буквы по частоте, а затем назначал буквы ветвям так, чтобы буквы слева в любой заданной паре ветвей использовались в сообщении примерно столько же раз, сколько буквы справа. Благодаря такому распределению часто используемые символы попадут на более короткие и менее плотные ветви. Небольшое количество высокочастотных букв всегда будет уравновешивать большее количество низкочастотных.
Сообщение «bookkeeper» состоит из трех E, двух K, двух O и по одному B, P и R. Симметрия Фано очевидна во всем дереве. Например, E и K вместе имеют общую частоту 5, что идеально соответствует объединенной частоте O, B, P и R.
Результатом стало удивительно эффективное сжатие. Но это была всего лишь аппроксимация; должна была существовать более эффективная стратегия сжатия. Поэтому Фано бросил вызов своим ученикам, чтобы найти её.
Фано строил свои деревья сверху вниз, сохраняя как можно большую симметрию между парными ветвями. Его ученик Дэвид Хаффман перевернул процесс с ног на голову, построив те же типы деревьев, но снизу вверх. Идея Хаффмана заключалась в том, что в эффективном коде два наименее распространенных символа, что бы ни случилось, должны иметь два самых длинных кода. Итак, Хаффман определил два наименее распространенных символа, сгруппировал их вместе в виде ветвящейся пары, а затем повторил процесс, на этот раз разыскивая два наименее распространенных элемента среди оставшихся символов и пары, которую он только что построил.
Рассмотрим сообщение, в котором подход Фано дает сбои. В «schoolroom» O встречается четыре раза, а S/C/H/L/R/M – по одному разу. Балансирующий подход Фано начинается с назначения буквы О и еще одной буквы левой ветви, при этом пять общих использований этих букв уравновешивают пять появлений остальных букв. Результирующее сообщение требует 27 бит.
Хаффман, напротив, начинает с двух нечастых букв – скажем, R и M – и группирует их вместе, рассматривая пару как одну букву.
Затем его обновленная диаграмма частот предлагает ему четыре варианта: буква O, которая появляется четыре раза, новый комбинированный узел RM, который функционально используется дважды, и отдельные буквы S, C, H и L. Хаффман снова выбирает два наименее распространенных варианта, сопоставляя (скажем) H с L.
Диаграмма снова обновляется: O по-прежнему имеет вес 4, RM и HL теперь каждый имеют вес 2, а буквы S и C стоят отдельно. Хаффман продолжает с этого момента, на каждом этапе группируя два наименее частых варианта, а затем обновляя как дерево, так и диаграмму частот.
В конечном итоге «schoolroom» становится 11101111110000110110000101, что на один бит меньше, чем в нисходящем подходе Фано.
Один бит может показаться не таким уж большим, но даже небольшая экономия значительно возрастает при масштабировании в миллиарды гигабайт.
Действительно, подход Хаффмана оказался настолько мощным, что сегодня почти каждая стратегия сжатия без потерь использует понимание Хаффмана полностью или частично. Нужен PKZip для сжатия документа Word? Первый шаг включает в себя еще одну умную стратегию для выявления повторения и, таким образом, сжатия размера сообщения, но второй шаг состоит в том, чтобы взять полученное сжатое сообщение и пропустить его через процесс Хаффмана.
Неплохо для проекта, изначально мотивированного желанием аспиранта пропустить выпускной экзамен.
Но это было не легко. Хаффман работал над этой проблемой несколько месяцев, разработав несколько вариантов решений, но ни один из них не оказался эффективным. В конце концов, он отчаялся когда-либо найти эффективное решение и решил начать подготовку к экзамену. Пока он выбрасывал свои заметки в мусор, к нему пришло решение. «Это был самый необычный момент в моей жизни, — сказал Хаффман. — «Молния внезапного осознания».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
