Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
В коде Хаффмана это достигается формированием «дерева» – своеобразного графа, не имеющего замкнутых петель и очень распространенного в информатике, потому что такой граф представляет целую стратегию решений типа да/нет, где каждое решение зависит от предыдущего. Листьями дерева являются символы 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. Описанная выше сложная пятиступенчатая процедура, выполняемая в мгновение ока за кулисами, – это и есть магия, в которой задействованы пять областей математики.
* * *
Другой способ сжатия изображений вырос в конце 1980-х годов из фрактальной геометрии. Фрактал, как вы помните, это геометрическая фигура, структура которой детализируема на всех масштабах, как у береговой линии или облака. С фракталом связано определенное число, называемое размерностью и представляющее собой меру того, насколько данный фрактал угловат или волнист. Как правило, размерность фрактала не является целым числом. Полезный класс математически разрешимых фракталов включает самоподобные фракталы: небольшие их кусочки, надлежащим образом увеличенные, выглядят в точности так же, как более крупные куски целого. Классический пример – папоротник, состоящий из десятков листов, каждый из которых выглядит как миниатюрный папоротник. Самоподобные фракталы могут быть представлены математической структурой, известной как система итерированных функций (IFS). Это набор правил, говорящих, как следует сжимать копии формы и сдвигать получившиеся плитки так, чтобы они сложились и образовали целое. Фрактал можно восстановить по этим правилам, а для размерности фрактала существует даже формула.
Фрактальный папоротник, составленный из трех преобразованных копий самого себя
В 1987 году математик Майкл Барнсли, давно увлекавшийся фракталами, понял, что их главное свойство может стать основой для нового метода сжатия изображений. Вместо того чтобы использовать огромное количество данных для кодирования каждой крохотной детали папоротника, можно просто закодировать соответствующую систему итерированных функций, на что потребуется значительно меньше данных. Программное обеспечение всегда может восстановить изображение папоротника по IFS. Барнсли вместе с Аланом Слоуном основал компанию Iterated Systems Inc., которая получила более 20 патентов. В 1992 году она совершила настоящий прорыв: был разработан автоматический метод нахождения подходящих правил IFS. Программа ищет на изображении маленькие области, которые можно рассматривать как съежившиеся версии бо́льших по размеру областей. Таким образом, она использует намного больше плиток для мощения изображения. Однако метод остается общим и применим к любым изображениям, а не только к тем из них, которые очевидно самоподобны. Фрактальное сжатие изображений не настолько популярно, как JPEG, по разным причинам, но использовалось в нескольких практических приложениях. Пожалуй, самым успешным из них была цифровая энциклопедия Encarta компании Microsoft, где все основные изображения были сжаты методом IFS.
Кто это? Прищурьтесь
На протяжении 1990-х годов компания предпринимала энергичные попытки распространить свой метод на сжатие видео, но из этого ничего не вышло, в основном потому, что тогдашние компьютеры были недостаточно быстрыми и имели недостаточно памяти. На сжатие одной минуты видео уходило 15 часов. Сегодня все изменилось, и фрактальное видеосжатие в отношении 200:1 можно проводить со скоростью один видеокадр в минуту. Повышение мощности компьютеров делает реальными и другие методы, и на данный момент от фрактального видеосжатия практически отказались. Но идея, лежащая в его основе, в свое время была полезна, да и сейчас таит в себе интересные возможности.
* * *
У людей есть очень странный прием для расшифровки некачественных
