Рождественские сказки?

Как раз на православное рождество флоридская стартап-компания ZeoSync объявила, что ею разработан и патентуется метод сжатия информации без потерь, в 10-100 раз более эффективный, чем любой из существующих. Что ж, очень своевременный шаг. Только жаль, что "без потерь". Хорошо бы ненужную информацию давить сразу и необратимо.

Общественность откликнулась на сенсационное сообщение без особого энтузиазма. Мне понравилось, как сказал известный криптограф Брюс Шнайер (Bruce Schneier): шансы на то, что метод сжатия в N раз будет работать, всегда составляют ровно 1/N (www.theregister.co.uk/content/55/23591.html). Но несмотря на почти нарочито комичные названия патентуемых алгоритмов - «Настройщик нуль-пространства» (Zero Space Tuner), например, - интерес к ZeoSync пока не пропадает. Между тем заявления о сенсационных коэффициентах сжатия делаются не так уж редко. Обсуждение некоторых из них есть здесь.

Интересно сравнить эту ситуацию с ажиотажем начала 1990-х вокруг фрактального сжатия. В первых статьях автора и идеолога этой технологии Майкла Барнсли (Michael Barnsley) демонстрировались изображения, сжатые в сотни и даже тысячи раз - с потерями, но без видимых искажений. Вскоре был опубликован и алгоритм кодирования, после чего сообщения о чудесах фрактального сжатия как-то незаметно сошли на нет. А затем появились математические теоремы об эквивалентности этого фрактального алгоритма другим методам, никогда не претендовавшим на сверхъестественные свойства ¹. Несмотря на солидные средства, вложенные в раскрутку этой технологии, результат категорически не соответствует ожиданиям - повсеместного вытеснения «обычных» методов сжатия фрактальными не произошло. Даже сколько-нибудь существенной ниши для таких методов (электронные энциклопедии, мультимедийные базы данных считались наиболее естественными областями их применения ) пока не возникло.

Специалист по сжатию данных Дмитрий Ватолин (ф-т ВМК МГУ) ознакомил меня с некоторыми свежими заявками на суперсжатие. Например, вот: «компания Digital Sounds завершила разработку алгоритма сжатия цифрового звука, оставляющего далеко позади все известные аналоги. В основу алгоритма положен оригинальный метод интенсивной деградации фрактальных последовательностей, обеспечивающий компрессию в 10-100 раз более эффективную, нежели широко распространенный MPEG 1 Layer 3…». Дата - март 2001 года; о сенсации сообщила и «КТ». Прошел почти год - и что?.. На www.faqs.org/faqs/compression-faq я даже набрел на замечательное описание жульнических программ, имитировавших суперсжатие. Похоже, страсть к покорению бурных потоков информации пробуждает темные стороны человеческой натуры не хуже, чем пресловутый квартирный вопрос (тоже, кстати, связанный с плотностью упаковки).

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

В статье Донохо, Добеши и др. «Сжатие данных и гармонический анализ» ² проблема компактного описания «естественных источников информации» названа Большим Вызовом (Grand Challenge). В этой и других работах приводятся в том числе и экзотические полушутливые аргументы в пользу того, что разрыв между достигнутым и достижимым уровнем сжатия таких данных огромен. Например, посчитав, сколько фотографий можно сделать за время существования Вселенной, если к каждому атому привязать по камере и снимать 1000 раз в секунду, легко убедиться, что снимки можно занумеровать… ну, скажем, 500-битными числами. То есть прямой доступ к воображаемой таблице снимков давал бы их сжатие без потерь до 500 бит.

Авторы упомянутых выше работ - крупнейшие ученые; Добеши стояла у истоков вейвлет-революции, Мамфорд - филдсовский лауреат и т. д. А еще один знаменитый математик, Стивен Смейл (Stephen Smale), классик топологии и теории динамических систем, получивший филдсовскую медаль на матконгрессе в Москве в 1966 году, упоминался в прессе как один из соавторов чудесной методики ZeoSync. Я обратился к нzему за комментариями и 14 января получил ответ: «…About 4 days ago i started working for ZeoSync here in Florida, for a two week plus consultation. I am in no position to say anything about the statements released by ZeoSync. <…> Best regards, Steve Smale» ³.

Интерпретацию оставляю читателю.

P.S. Оцените резонанс колонки Ваннаха и статьи Кагарлицкого в этом номере.