Как работает сжатие данных без потерь | Журнал Кванта

Ежедневно по Интернету перемещается более 9 миллиардов гигабайт информации, поэтому исследователи постоянно ищут новые способы сжатия данных в более мелкие пакеты. Передовые методы сосредоточены на подходах с потерями, которые обеспечивают сжатие путем преднамеренной «потери» информации из передачи. Google, например, недавно представила стратегию с потерями, когда компьютер-отправитель пропускает детали изображения, а компьютер-получатель использует искусственный интеллект, чтобы угадать недостающие части. Даже Netflix использует подход с потерями, снижая качество видео всякий раз, когда компания обнаруживает, что пользователь смотрит на устройстве с низким разрешением.

Напротив, в настоящее время проводится очень мало исследований по стратегиям без потерь, при которых передача становится меньше, но не жертвуется содержанием. Причина? Подходы без потерь уже удивительно эффективны. Они поддерживают все, от стандарта изображений JPEG до вездесущей утилиты PKZip. А все из-за аспиранта, который просто искал выход из жесткого выпускного экзамена.

Семьдесят лет назад профессор Массачусетского технологического института по имени Роберт Фано предложил студентам своего класса по теории информации выбор: сдать традиционный выпускной экзамен или улучшить передовой алгоритм сжатия данных. Фано мог сообщить или не сообщить своим ученикам, что он был автором этого существующего алгоритма или что он годами искал улучшение. Что мы знаем, так это то, что Фано предложил своим ученикам следующую задачу.

Рассмотрим сообщение, состоящее из букв, цифр и знаков препинания. Простым способом кодирования такого сообщения было бы присвоение каждому символу уникального двоичного числа. Например, компьютер может представить букву A как 01000001, а восклицательный знак как 00100001. В результате получаются коды, которые легко разобрать — каждые восемь цифр или битов соответствуют одному уникальному символу — но ужасно неэффективно, потому что одно и то же число двоичных цифр используется как для обычных, так и для необычных записей. Лучшим подходом было бы что-то вроде азбуки Морзе, где частая буква E представлена ​​​​всего одной точкой, тогда как менее распространенная Q требует более длинного и трудоемкого тире-тире-точка-тире.

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

Фано решил эту часть проблемы. Он понял, что может использовать коды различной длины без дорогостоящих пробелов, если он никогда не использует один и тот же набор цифр как в качестве полного кода, так и в начале другого кода. Например, если буква S была настолько распространена в определенном сообщении, что Фано присвоил ей очень короткий код 01, то никакая другая буква в этом сообщении не будет кодироваться чем-либо, начинающимся с 01; такие коды, как 010, 011 или 0101, будут запрещены. В результате закодированное сообщение можно было читать слева направо без какой-либо двусмысленности. Например, когда букве S присвоено значение 01, букве A присвоено значение 000, букве M присвоено значение 001, а букве L присвоено значение 1, сообщение 0100100011 может быть немедленно переведено в слово «маленький», даже если L представлено единицей. цифра, S по две цифры, а остальные буквы по три каждая.

Чтобы на самом деле определить коды, Фано построил бинарные деревья, поместив каждую необходимую букву в конец визуальной ветви. Затем код каждой буквы определялся путем сверху вниз. Если путь разветвлялся налево, Фано добавлял 0; правые ветви получили 1. Древовидная структура позволила Фано избежать этих нежелательных наложений: как только Фано поместил букву в дерево, эта ветвь закончилась, а это означало, что ни один будущий код не мог начинаться таким же образом.

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

Результатом стало удивительно эффективное сжатие. Но это было только приближение; должна была существовать лучшая стратегия сжатия. Поэтому Фано бросил вызов своим ученикам, чтобы найти его.

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

Рассмотрим сообщение, в котором подход Фано дает сбои. В «schoolroom» O встречается четыре раза, а S/C/H/L/R/M — по одному разу. Подход Фано к уравновешиванию начинается с назначения буквы O и еще одной буквы левой ветви, при этом пять общих использований этих букв уравновешивают пять появлений остальных букв. Результирующее сообщение требует 27 бит.

Хаффман, напротив, начинает с двух необычных букв — скажем, R и M — и группирует их вместе, рассматривая пару как одну букву.

Затем его обновленная диаграмма частот предлагает ему четыре варианта: O, который появляется четыре раза, новый комбинированный узел RM, который функционально используется дважды, и отдельные буквы S, C, H и L. Хаффман снова выбирает два наименее распространенных варианта, соответствующие (скажем) H с L.

Диаграмма снова обновляется: O по-прежнему имеет вес 4, RM и HL теперь имеют каждый вес 2, а буквы S и C стоят отдельно. Хаффман продолжает с этого момента, на каждом этапе группируя два наименее частых варианта, а затем обновляя как дерево, так и диаграмму частот.

В конечном итоге «учебная комната» становится 11101111110000110110000101, что на один бит меньше, чем в нисходящем подходе Фано.

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

Действительно, подход Хаффмана оказался настолько мощным, что сегодня почти каждая стратегия сжатия без потерь использует идеи Хаффмана полностью или частично. Нужен PKZip для сжатия документа Word? Первый шаг включает в себя еще одну умную стратегию для выявления повторения и, таким образом, сжатия размера сообщения, но второй шаг состоит в том, чтобы взять полученное сжатое сообщение и пропустить его через процесс Хаффмана. Сохранить изображение в формате JPEG? Ваш компьютер сначала переводит изображение в текстовое представление, а затем снова использует кодировку Хаффмана для сжатия этого текста.

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