Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Сжатие изображений – важная часть более общего вопроса сжатия данных, который, несмотря на громадные технологический успехи, по-прежнему остается жизненно важным. Каждый раз, когда интернет следующего поколения становится в 10 раз быстрее и приобретает еще более впечатляющую пропускную способность, какой-нибудь гений изобретает новый формат данных (скажем, трехмерное видео сверхвысокой четкости), требующий куда больше данных, чем прежде, и все возвращается на круги своя.
Иногда у нас просто нет другого выбора, кроме как выжимать каждый байт пропускной способности из канала связи. На Марсе 4 января 2004 года что-то свалилось с неба, ударилось о поверхность и отскочило. Если говорить точнее, то марсианский ровер A под названием Spirit подскочил над марсианским грунтом 27 раз. Он был со всех сторон окружен надувными баллонами, как будто завернут в эдакую космическую пузырчатую пленку – последнее слово в методах посадки. После общей проверки систем и различных процедур инициализации ровер пустился исследовать поверхность чужой планеты, где к нему вскоре присоединился компаньон, Opportunity. Оба ровера работали необычайно успешно и прислали на Землю громадное количество данных. Тогда же математик Филип Дэвис указал, что в этой программе многое зависит от математики, но «общественность вряд ли это сознает». Оказалось, что не сознает этого не только общественность. В 2007 году датские аспиранты-математики Уффе Янквист и Бьёрн Толдбод посетили Лабораторию реактивного движения в Пасадене с журналистской миссией: раскрыть роль математики в программе Mars Rover. И услышали в ответ:
– Мы ничего такого не делаем. На самом деле мы не используем никакой абстрактной алгебры, теории групп, ничего подобного.
Это встревожило молодых людей, и один из них спросил:
– За исключением кодирования канала?
– Там используется абстрактная алгебра?
– Коды Рида – Соломона основаны на полях Галуа.
– Это для меня новость.
На самом деле в космических программах NASA задействована очень и очень продвинутая математика для сжатия данных и их кодирования таким способом, который позволяет исправлять ошибки, неизбежно возникающие при передаче. Это просто приходится делать, когда передатчик находится чуть ли не в миллиарде километров от Земли и имеет мощность электрической лампочки. (Немного помогает передача данных через аппарат на орбите Марса, такой как Mars Odissey или Mars Global Surveyor.) Большинству инженеров нет нужды это знать, они и не знают. В этой ситуации, как в зеркале, отражается неверное представление широкой общественности о математике.
* * *
Все в вашем компьютере, будь то электронная почта, фото-, видео– или аудиоальбом, хранится в памяти как поток двоичных цифр, битов, нулей и единиц. Восемь бит образуют байт, а 1 048 576 байт – мегабайт. Типичная фотография низкого разрешения занимает около 2 Мб. Хотя все цифровые данные записываются именно в этом виде, разные приложения используют разные форматы, так что смысл данных зависит от приложения. Каждый тип данных имеет скрытую математическую структуру, и удобство обработки часто оказывается куда более значимым, нежели размер файла. Удобный формат данных может означать их избыточность – использование для их хранения больше битов, чем реально требует содержание информации. Это создает возможность сжатия данных посредством устранения избыточности.
Письменный (и устный) язык весьма и весьма избыточен. В качестве доказательства можно привести фразу, уже встретившуюся нам в этой главе, удалив при этом каждый пятый знак:
окру_ен н_дувн_ми б_ллон_ми, _ак б_дто _авер_ут в_эдак_ю.
Надо полагать, вы можете разобрать, что в ней говорится, без особых размышлений или усилий. Оставшейся информации достаточно, чтобы восстановить первоначальную фразу целиком.
Тем не менее эта книга будет намного легче восприниматься зрительно, если не заставлять издателей экономить на краске, пропуская каждый пятый знак. Правильные слова мозгу обрабатывать намного проще, потому что именно это он обучен делать. Однако если вы хотите передать битовую строку, вместо того чтобы обрабатывать эти данные при помощи какого-то приложения, эффективнее будет переслать более короткую последовательность нулей и единиц. Уже на заре развития теории информации такие ее пионеры, как Клод Шеннон, поняли, что избыточность информации дает возможность закодировать сигнал с использованием меньшего числа битов. Мало того, Шеннон вывел формулу, позволяющую вычислить, насколько короче код может получиться из данного сигнала для данного уровня избыточности.
Избыточность принципиально важна, потому что сообщения без нее невозможно сжать без потери информации. Доказательство основано на простом подсчете. Предположим, например, что нас интересуют сообщения длиной 10 бит, такие как 1001110101. Существует ровно 1024 таких битовых строки. Предположим, мы хотим сжать 10 бит данных в 8-битную строку. Таких строк существует ровно 256. Так что сообщений у нас имеется вчетверо больше, чем сжатых строк, и невозможно каждой 10-битной строке поставить в соответствие 8-битную строку так, чтобы разным 10-битным строкам соответствовали разные 8-битные строки. Если каждая 10-битная строка может встретиться с равной вероятностью, то выясняется, что у нас нет умного способа обойти это ограничение. Однако если некоторые из 10-битных строк встречаются очень часто, а остальные очень редко, мы можем выбрать код, который обозначит короткими битовыми строками (скажем, по 6 бит) самые часто встречающиеся сообщения и более длинными строками (может быть, по 12 бит) – редкие сообщения. 12-битных строк существует много, так что их недостаток нам не грозит. Всякий раз, когда встречается редкое сообщение, оно добавляет два бита к длине передачи, зато когда встречается частое сообщение, оно убавляет четыре бита. При подходящих вероятностях из сообщений будет отнято больше бит, чем добавлено.
Вокруг подобных методов выросла целая отрасль математики – теория кодирования. В общем случае эти методы куда тоньше, чем описанный выше, и обычно в них для определения кодов используются свойства абстрактной алгебры. Это не должно слишком удивлять: в главе 5 мы видели, что, по существу, коды – это математические функции и что особенно полезны здесь функции теории чисел. Там целью была секретность, здесь цель – сжатие данных, но общий принцип одинаков в обоих случаях. Алгебра имеет отношение к структуре, как и избыточность.
Сжатие данных, а следовательно, и сжатие изображений, использует избыточность для создания кодов, укорачивающих данные конкретного типа. Иногда данные сжимаются «без потерь»: в этом случае первоначальную информацию можно восстановить по сжатой версии в точности. Иногда данные теряются, и тогда восстановленный вариант лишь приближение первоначальных данных. Это было бы плохо, скажем, для банковских счетов, но зачастую вполне годится для изображений: главное – устроить все так, чтобы приближенный вариант по-прежнему выглядел для человеческого глаза похожим на первоначальное изображение. Тогда информация, которая теряется безвозвратно, вообще не имеет значения.
Изображения в реальном мире по большей части избыточны. Отпускные фотки часто содержат большие блоки голубого неба, нередко примерно одинакового оттенка по всей площади, так
