Internet любят все. С особенным чувством к Сети относятся бизнесмены — она упрощает торговлю. Жулики тоже обожают Сеть — им в ней намного легче представляться бизнесменами. И террористы жалуют Сеть — она исключает необходимость в явочных квартирах и тайниках для обмена шифровками. Тинейджеры вообще без ума от Сети — здесь легко можно изображать из себя "крутого" кибертеррориста. Спецслужбы не остались в стороне от всеобщего удовольствия — с помощью Сети им намного проще ловить тинейджеров, представляющихся террористами, тем самым улучшая отчетность. На "фестиваль любви" спешат чиновники от политики: одни для поднятия рейтинга, другие — в поиске ни к чему не обязывающей, но прибыльной и обещающей популярность должности "регионального начальника Internet". Юристы торопятся "застолбить" участки на пустующем правовом поле виртуальной реальности — должность юрисконсульта при "начальнике Internet" манит замечательным сочетанием потенциальной безответственности и высокой престижности. Над "океаном любви" гордым буревестником реет "его величество Контент", вознося к недостижимым высотам самых "неистовых любовников Сети" — Web-оформителей.
Короче говоря, Сеть стала предметом всеобщего обожания тех, кто либо ничего о ней не знает, либо зарабатывает деньги для тех, кто ничего о ней не знает. Куда более спокойно к Internet относятся непосредственные "виновники" возникновения этого феномена: военные недолюбливают Сеть за высокую уязвимость от воздействий "потенциального противника", академическая наука — за невыразительность средств формирования контента (исследовательские и научные сайты обычно оформлены более чем скромно — только минимально необходимая навигация, а содержательная часть "спрятана" в postscript или pdf-файлы).
Неформальная история
языков разметки документов
"И был рай. И на седьмой день творения создал Бог язык HTML. И увидел Бог, что это хорошо. Но пришел к Богу математик и спросил: "Господь, а как мне на этом записывать формулы?". Тогда придумал Бог расширение HTML — MathML. И только увидел, что это хорошо, как пришел к нему химик: "Господи, я даже формулу бензола на этом записать не могу!". Только задумался Бог о новом расширении, а в дверях уже композитор стоит. Открыл Бог дверь в приемную, а там — и электронщик-схемотехник, и архитектор, и гидравлик, и бухгалтер, и топограф, и военные, и врачи, и вообще все-все-все… И задумался Бог еще на семь дней, и придумал XML, и увидел, что это нехорошо, но лучше все равно ничего не будет. И расстроился Господь, и отдал просителям XML и изгнал их из рая. И это был день четырнадцатый".
Неформальность неформальностью, но в сущности все именно так и есть. С ростом популярности Сети требования к языкам разметки документов (ЯРД) катастрофически растут: с одной стороны, "абсолютный гипертекст" принципиально необходим, с другой — не менее принципиально невозможен.
"Расширяемые" ЯРД (типа XML) решением проблемы не являются, скорее наоборот, — они порождают новую проблему сегментации информационного пространства Сети: определяемые пользователями элементы языка требуют дополнительной программной поддержки. С точки зрения потребителя информационных ресурсов это означает одно — можно использовать только тот документ, для которого есть необходимое ПО. Вся прелесть информационной свободы Internet сразу утрачивается. А ведь еще есть проблемы с национальными языками и валютами, с множеством шрифтов, с разными единицами измерения… И наконец, есть ПРОБЛЕМА # 1 — более 90% информационных ресурсов (по очень оптимистичным оценкам) всего человечества хранятся в "самом архаичном представлении" — на бумаге. Преобразование их в ЯРД-форму требует и астрономических средств, и принципиально невозможных распознающих программ (по очевидной причине принципиальной невозможности создания "абсолютного гипертекста"), но главное не в этом. Главное заключается в отсутствии необходимости этого преобразования — информация нужна людям, а не программам. А людям важно, чтобы представление обеспечивало удобства чтения, хранения и доступа к информации, форма же самого представления нас интересует мало (естественно, в том случае, когда у нас есть простые инструментальные средства, позволяющие использовать эти информационные ресурсы).
Единственный разумный выход из сложившейся ситуации — перевод документов в один из растровых графических форматов — широко используется в Сети для "лечения болезней" ЯРД. Достоинств у такого подхода много, но недостатков не меньше. Например, конечные полоса пропускания линий связи и емкость долговременной памяти компьютеров требуют применения компактных ("упакованных") графических форматов с потерей качества (или с низкой разрешающей способностью). Соответственно, изготовление хорошо читаемого документа в одном из таких форматов — большое искусство, и ни о каких массовых применениях его и речи идти не может. Растровые форматы, обеспечивающие представление документа без потерь (например, tiff), не годятся из-за огромных размеров — страница формата A4, сканированная с разрешением 300 dpi, в таком виде может занимать несколько десятков мегабайт. Даже при постоянно снижающихся ценах на накопители высокой емкости такие объемы выглядят, мягко говоря, несколько избыточными.
О разном
Вся эта история начиналась в 1800 году. Барон Жан Батист Фурье, вернувшийся из наполеоновской кампании в Египте к научной работе, в своей эпохальной статье "Аналитическая теория теплоты" использовал для представления периодической функции бесконечную последовательность композиции тригонометрических функций — синусов и косинусов. Впоследствии это представление назвали спектром, а сам метод его получения — преобразованием Фурье, которое сегодня является одним из основных инструментов в области цифровой обработки сигналов. Но не единственным — спектры, определенные преобразованием Фурье, далеко не всегда соответствуют потребностям ученых и инженеров. Во-первых, Фурье-анализ хорошо "работает" с периодическими функциями, если же речь идет о непериодическом (имеющем характер "всплеска") явлении, в спектральном Фурье-представлении "теряется" очень важная информация о времени.
Сформулирован (и разрешен с физической точки зрения) интересный "парадокс Фурье", наглядно показывающий логические "подводные камни" спектрального преобразования Фурье. Допустим, что у нас есть такие электрическая лампочка, выключатель и источник энергии, которые "работают" с бесконечно большой скоростью. Это предположение означает, что лампочка начинает светиться сразу после включения питания без всякой (даже сколь угодно малой) задержки. Соответственно, излучение лампочки изменяется по простому закону: сначала она выключена, и излучение равно 0, в момент времени tx лампочка включается, и излучение, предположим, равно 1. Спектр Фурье такого скачка — бесконечное множество "излучений" (те самые синусы и косинусы), существующих "во все времена Вселенной" (в диапазоне времен —
Этот парадокс разрешается для разных аналогий далеко не всегда просто, но сам факт его существования настораживал ученых, вынуждая искать эффективные методы анализа непериодических явлений. Фурье-преобразование обобщили — оказалось, что в спектральном представлении вместо синусов и косинусов можно использовать целые классы так называемых ортогональных функций (само понятие ортогональности не совсем тривиально, а формул с интегралами автор принципиально решил избежать).
Смысл ортогональности все же нужно напомнить: существует точная векторная аналогия, хорошо знакомая со школьной скамьи, — помните проекции вектора на оси координат и векторы-орты единичной длины? Появились спектральные преобразования с несинусоидальными базисными функциями, например Уолша. Но принципиального недостатка — потери информации о временных характеристиках сигнала — все эти меры не устраняли.
Затем появились вейвлеты и вейвлетное преобразование, идея которого — представление некоторой функции композицией других функций-вейвлетов — напоминает преобразование Фурье. Но во всем остальном вейвлет-преобразование разительно отличается от своих "спектральных предшественников". Во-первых, вейвлеты—базисные функции конечны (и описанный выше парадокс в этом случае не возникает), во-вторых, вместо амплитудного масштабирования базисных функций в вейвлет-преобразовании используется временная "растяжка", в-третьих, простая линейная операция композиции (сложение) в Фурье-преобразовании заменяется временными сдвигами и временным масштабированием.
Без существенного смыслового ущерба процедуру вейвлет-преобразования можно изобразить графически. Основу основ всей этой "адской механики" составляет главный (или материнский) вейвлет — весьма специфическая функция, один из вариантов которой приведен на рис. 1. Сначала для вычисления преобразования используется "материнский" вейвлет, затем он сдвигается (во времени), и вычислительные процедуры повторяются, одновременно с этим материнский вейвлет "растягивается" во времени и над ним и сигналом выполняются аналогичные процедуры и т. д.
Подобный алгоритм, в котором временной интервал анализируемого сигнала разбивается на 2M участков, а на каждые 2 (или в более общем случае — на 2N) процедуры сдвига "материнского" вейвлета приходится одна процедура временного масштабирования ("растяжки"), именуется дискретным вейвлет-анализом.
Существует и так называемое непрерывное вейвлет-преобразование, в котором операции сдвига в соответствии с именем метода осуществляются на единичные (в терминах оцифрованного анализируемого сигнала) моменты времени по всей временной оси, а операции временного масштабирования настраиваются, исходя из требований к качеству результата преобразования.
Автор умышленно опустил сущность математических операций, проделываемых в ходе преобразования над вейвлетами и сигналом, — здесь без "кошмарных" формул с интегралами не обойтись, да и после этого короткого знакомства самые бесстрашные читатели смогут поближе познакомиться с вейвлет-теорией самостоятельно (очень хорошая коллекция ссылок на Web-ресурсы, посвященные вейвлетам, собрана на сайте dmoz.org/Science/Math/Wavelets/). Все эти попытки "на пальцах" объяснить вещи сколь сложные, столь и интересные, надеюсь, помогут ослабить симптомы первой "шоковой реакции" при углублении в математические дебри.
Возвращаясь к реальности
Вейвлеты — теория сравнительно новая и, по крайней мере на бумаге, красивая. А всякая красивая теория непременно должна давать полезные практические результаты. Вейвлет-преобразование хорошо подходит для решения задач, связанных с обработкой звука и изображений (есть еще масса приложений, где достоинства вейвлетов уже не вызывают сомнений даже у самых агрессивных скептиков), настолько хорошо, что законодатель мод в области цифровой обработки сигналов — компания Analog Devices — серийно выпускает "вейвлет-процессоры" семейства ADV601, на которых уже создаются самые разнообразные устройства (к слову, ADV601 — чипы недорогие и, как вся продукция Analog Devices, прекрасно поддерживаемые компанией, например, стоимость модуля для разработки приложений с использованием этих кристаллов составляет всего $199).
Широкие возможности и вейвлет-технологии, и процессоров ADV601 подтверждаются изделиями на их основе, например цифровыми видеомагнитофонами, в реальном времени осуществляющими компрессию/декомпрессию видеосигнала с коэффициентом сжатия до 350 : 1 и качеством VHS (25 минут VHS-видео на 1 GB жесткого диска).
В контексте же данной статьи хорошие показатели вейвлет-технологии интересны прежде всего с точки зрения Internet-приложений. О проблемах, возникающих при попытках перенести большие "бумажные" архивы, уже упоминалось. И здесь на помощь приходят абстрактные вейвлеты, точнее, не они сами, а программные продукты, основанные на вейвлет-компрессорах.
Существует несколько реализаций и графических форматов, и программ вейвлет-упаковки, но на сегодняшний день только одно решение может претендовать на роль массово-необходимого овеществления вейвлет-теории. Речь идет об одноименных формате данных и программных средствах под названием Dejavu, разработанных исследовательскими лабораториями знаменитой AT&T (если при чтении этой статьи вы сидите за компьютером, подключенным к Internet, не теряя времени отправляйтесь на сайт dejavu.research.att.com и обзаведитесь всем необходимым для работы с данными в этом формате). К чести AT&T, компания продолжает активно способствовать развитию программного обеспечения с открытыми исходными текстами и предоставляет разработчикам ПО бесплатную версию Reference Library (библиотека на языке программирования С++), позволяющую встраивать программы декомпрессии и визуализации Dejavu-файлов в приложения.
Итак, Dejavu. На первый взгляд— ничего особенного: ну, новый формат упаковки графических растровых файлов, ну, хорошо поддержанный и созданный именитой компанией. Но стоит только один раз попробовать… Оптимизированный для обработки сканированных изображений программный компрессор "сжимает" 20—30-мегабайтовые файлы до… единиц (в худшем случае — десятков) килобайт. Самое интересное выясняется после операции декодирования — исходное разрешение информативной части сканированного файла… восстанавливается. При этом скорость декомпрессии даже на скромном Pentium 200 MHz можно назвать "моментальной".
Под информативной частью изображения в AT&T справедливо понимают высококонтрастные составляющие "картинки", например черный текст, формулы, схемы на белом фоне, — если разрешение при сканировании составляло 300 dpi, Dejavu честно его восстановит. Результат превосходит все ожидания: файлы Dejavu занимают намного меньше места, чем их HTML-аналоги (это утверждение только кажется не бесспорным), и не предъявляют требований к системному окружению (например, к шрифтам). Самое главное, что Dejavu абсолютно все равно, что содержит пресловутый контент: схемы, формулы, рукописный текст, детские рисунки сжимаются им с почти одинаковой эффективностью.
А теперь давайте на время предположим, что нет никаких языков типа HTML/XML, а есть только Dejavu (или нечто более эффективное, но аналогичного назначения), программы распознавания символов и векторизаторы (ПО, обеспечивающее в идеале автоматический перевод растровых изображений в векторный формат). Пусть есть еще средства организации гиперссылок (вот здесь может пригодиться или XML, или заботливо предусмотренный самой AT&T встроенный механизм их поддержки). В результате получаем компактную, простую и эффективную альтернативу существующей НТМL-организации Web. "Электронная бумага" Dejavu-формата дает целый ряд преимуществ: маленькие и информативные файлы, очень простой броузер, способный работать на любой платформе, возможность использования фрагментов распространяемых документов (нужна вам фраза текста из Dejavu-файла — укажите ее программе распознавания и затем используйте в своем тексте, аналогично — с векторизованными изображениями), минимальные затраты на создание как новых документов (представленных, например, в tiff-формате), так и переноса в новую технологию старого, "бумажного", но бесценного контента. К слову, и программы распознавания символов, и векторизаторы активно разрабатываются AT&T… в рамках проекта Dejavu.
Идея, конечно, нереальная — процветающая Internet-индустрия не допустит таких "вольностей", но… Dejavu открывает уникальные перспективы для библиотек, как персональных, так и коллективного пользования. Например, коллекция автора из нескольких сотен статей, "напичканных" электронными схемами и формулами, занимает на винчестере чуть больше мегабайта, а процедуры подготовки этого информационного массива длились чуть больше часа (для сравнения: автор неоднократно пытался проделать то же самое с использованием программ распознавания текстов — мучительная процедура "выковыривания" схем и формул отнимала десятки минут на каждую страницу, а размеры пригодных к чтению схем в gif- и jpg-форматах убедительно свидетельствовали о бесперспективности мероприятия).