Это база: Зачем нужна математика в повседневной жизни

Например, в качестве словарных символов можно использовать буквы алфавита. В английском алфавите их 26, так что каждой из них можно было бы присвоить 5-битную строку, скажем, A = 00001, B = 00010 и т. д. Пять бит нужны потому, что из четырех бит можно составить только 16 строк. Но использовать 5-битные строки было бы неэффективно, потому что на буквы, которые встречаются редко, такие как Z, уходит ровно столько же битов, сколько на распространенные буквы, такие как E. Лучше было бы присвоить E короткую строку, такую как 0 или 1, и постепенно удлинять строки по мере того, как буквы становятся менее вероятными. Однако, поскольку в этом случае кодовые строки получаются разными по длине, потребуется дополнительная информация, которая сообщит реципиенту, где следует разбить строку на отдельные буквы. В принципе, это можно сделать при помощи префикса перед кодовой строкой, но у нас сам код должен быть, как говорят математики, беспрефиксным: кодовая строка не должна начинаться с другой, более короткой кодовой строки. Редко используемые буквы, такие как Z, при этом требуют намного больше битов, но, поскольку они редкие, более короткие строки для E с лихвой компенсируют это. Общая длина типичного сообщения оказывается короче.

В коде Хаффмана это достигается формированием «дерева» – своеобразного графа, не имеющего замкнутых петель и очень распространенного в информатике, потому что такой граф представляет целую стратегию решений типа да/нет, где каждое решение зависит от предыдущего. Листьями дерева являются символы A, B, C, …, и из каждого листа выходит по две ветви, соответствующие двум битам 0 и 1. Каждый лист обозначен числом, которое называют его весом и которое показывает, как часто встречается соответствующий символ. Дерево строится шаг за шагом путем слияния двух наименее частых листьев в новый «материнский» лист, тогда как первые два листа становятся листьями-«дочками». Материнскому листу присваивается вес, равный сумме весов двух дочерних листьев. Этот процесс продолжается до тех пор, пока все символы не сольются. Тогда кодовая строка для символа считывается с пути, который ведет по дереву к этому символу.

Построение кода Хаффмана

Например, на рисунке слева вверху показаны пять символов A, B, C, D, E и числа 18, 9, 7, 4, 3, указывающие на частоту их встречаемости. Самые редко встречающиеся символы здесь D и E. На втором этапе, вверху по центру, их смешивают с образованием материнского листа (ненумерованного) с весом 4 + 3 = 7, а символы D и E становятся дочерними. Две ведущие к ним ветви получают обозначения 0 и 1. Этот процесс повторяется несколько раз, пока все символы не сливаются воедино (внизу слева). Теперь мы считываем кодовые строки, следуя по путям вниз по дереву. К A ведет одна-единственная ветвь, обозначенная как 0. К B ведет путь 100, к C – путь 101, к D – путь 110 и к E – путь 111. Обратите внимание, что A, самый часто встречающийся символ, получает короткий путь, а менее распространенные символы – более длинные пути. Если бы вместо этого мы использовали код с фиксированной длиной строки, нам потребовалось бы по крайней мере три бита, чтобы закодировать пять символов, потому что двухбитных строк всего четыре. Здесь же в самых длинных строках по три бита, но в самой часто встречающейся – всего один, так что в среднем этот код более эффективен. Эта процедура гарантирует, что наш код беспрефиксный, поскольку любой путь на дереве ведет к какому-нибудь символу и на нем останавливается. Он не может продолжаться до другого символа. Более того, начав с наименее распространенных символов, мы гарантируем, что к самым распространенным символам будут вести самые короткие пути. Это отличная идея, легкая в программировании и очень простая концептуально, стоит один раз в ней разобраться.

Когда ваша камера создает файл JPEG, ее электроника производит все расчеты на лету, как только вы нажимаете на спуск. Процесс сжатия проходит не без потерь, но большинство из нас никогда этого не заметит. В любом случае экраны компьютеров и принтеры при распечатке не передают цвета и яркость в точности, за исключением случаев, когда их заранее тщательно калибруют. Непосредственное сравнение оригинального изображения и его сжатой версии делает различия более очевидными, но даже в этом случае только эксперт заметит разницу, если файл был сжат до 10 % от первоначального объема. Обычные смертные замечают разницу, только когда файл уменьшается до примерно 3 % от оригинала. Так что JPEG позволяет записать на карту памяти в 10 раз больше изображений, чем оригинальный формат данных RAW. Описанная выше сложная пятиступенчатая процедура, выполняемая в мгновение ока за кулисами, – это и есть магия, в которой задействованы пять областей математики.

* * *