Поделить и отнять

Иерархия Usenet, объединяющая тысячи эхоконференций, хорошо знакома пользователям Интернета. Способ общения, который она предлагает, оптимален для большой группы людей, и с эхоконференцией не сравнится никакой чат, будь он трижды звуковым или видео. Типичный пример такой удобной, умной и полезной дискуссионной группы - конференция Comp.Compress. Как понятно из названия, в ней обсуждают компрессию, то есть сжатие информации с помощью компьютеров. Большинство неспешных разговоров идет между авторами программ-компрессоров (их довольно много) и просто интересующимися людьми, поэтому обсуждаемые темы очень специфичны, малопонятны несведущему человеку и случайные посетители забредают в Comp. Compress редко. Однако время от времени в сообщениях, проходящих по Comp.Compress, всплывает вопрос, действующий на ее патриархов примерно так же, как на историков действует фамилия Фоменко, а на физиков - проекты вечного двигателя. Условно эту тему можно назвать «Чудо-Компрессор».

Как правило, это разработка маленькой, никому не известной компании, представляющая собой революционный алгоритм или уже готовый продукт для многократного сжатия информации. Обычно утверждается, что этот алгоритм сжимает без потерь во много раз, и самое главное - любую (!) информацию. Разумеется, при более близком знакомстве оказывается, что ничего подобного он не делает, но это, как говорится, детали. Главное, что idea fix регулярно возникает в Сети и на страницах масс-медиа уже много лет. Причина мистификаций очевидна - деньги и еще раз деньги. При некотором умении убеждать инвесторов и раскручивать компании в прессе таким способом можно хорошо зарабатывать. Характерным примером подобных афер может служить компания Entropy Systems из Огайо, сумевшая, по данным «Wired», с 1994 года получить от инвесторов 3,5 млн. долларов на создание вечного двигателя - Entropy Engines. Изобретатель и глава фирмы Санджай Амин (Sanjay Amin, сын турецкоподданого?) утверждал, что его двигатель не требует топлива и не загрязняет среду, а выделяющееся тепло легко преобразуется в электричество. В сентябре 1999 года Entropy Systems обещала выпустить первые модели своих моторов для катеров, газонокосилок и электрогенераторов, но, увы, что-то не заладилось.

Один из первых чудо-компрессоров «разработала» компания Web Technologies. В апреле 1992 года она объявила о создании программы, сжимающей в шестнадцать раз любые файлы размером больше 64 килобайт. Потом были другие фирмы, с другими «потрясающими разработками», некоторые даже патентовали алгоритмы, однако все они оказывались мыльными пузырями. Тем не менее, сообщения о каждом случае суперсжатия неизбежно проникают в конференцию Comp.Compress. Обычно их приносит восторженный новичок, делающий старожилам замечание в стиле: «Что вы тут ерундой занимаетесь, вот посмотрите, что придумали умные люди!»

Разоблачать подобные «достижения» и объяснять, почему они невозможны, - дело неблагодарное и трудное. Приходится излагать некоторые аспекты теории информации, а такие вещи сходу даже прочитать может не каждый. Можно, конечно, игнорировать эту тему, но она всплывает снова и снова. В солидных конференциях для таких случаев есть FAQ - «список часто задаваемых вопросов», документ, где все разложено по полочкам и к которому можно отсылать дилетантов. В Comp.Compress тоже есть такой список, но его авторы посчитали простые объяснения недостаточными, и решили предложить публике своего рода пари (www.faqs.org/faqs/compression-faq/part1/section-8.html).

Сначала Стив Тэйт (Steve Tate) объявил, что готов давать по 100 долларов каждому, кто хотя бы на 1/5 сожмет без потерь (а затем разожмет) его файл объемом 100 килобайт. Разумеется, все понимают, что файл не простой, а из категории «несжимаемых», поэтому на объявленную награду до сих пор никто не претендовал. Майку Голдмену (Mike Goldman) предложения Стива показалось мало, и он сделал свое, еще более заманчивое и демонстративное, с которым и связана прошлогодняя история.

Всем обладателям чудо-компрессоров Майк предложил вот что: «Я готов заплатить 5000 долларов любому, кто выполнит следующие условия. Вы сообщаете, какого размера файл можете сжать, и в доказательство своей серьезности присылаете мне 100 долларов. Я генерирую файл и высылаю вам. Вы изучаете его сколько хотите, приспосабливаете к данным свой алгоритм, затем сжимаете и присылайте мне вместе с вашим декомпрессором. Я разжимаю файл и проверяю - не была ли потеряна информация. Если не была и суммарный объем сжатого файла вместе с вашим декомпрессором хоть на сколько-нибудь меньше исходного файла, я заплачу вам 5000 плюс ваши 100 долларов».

Другими словами, можно было сжимать данные какого угодно размера, но величина компрессии увязывалась с размером декомпрессора. Приз не выплачивался, если файл сжимался на 100 байт, а для его разжатия нужна была программа размером в те же 100 байт.

26 марта Майку Голдмену по электронной почте пришло письмо от Патрика Крейга (Patrick Craig), и между ними завязалась переписка.

Патрик Майку: «Я прочитал ваше предложение. Звучит очень заманчиво, и мне интересно - оно все еще в силе? Хотелось бы узнать детали о декомпрессоре - он должен запускаться в любой среде или достаточно одной платформы, например Linux?»

Майк: «Да, предложение в силе. Линукса достаточно. Вы хотите попробовать?»

Патрик: «Я все еще думаю над этим. Вам нужен только сжатый файл?»

Майк: «Вы говорите, файл какого размера нужен, и присылаете мне

100 долларов. Я генерирую файл и отправляю вам. Вы присылаете мне его сжатым вместе с программой для разжатия. Если сжатый файл вместе с декомпрессором меньше оригинала - я высылаю вам 5000. Если у вас не получилось - можете опять прислать мне 100 долларов и попробовать еще раз».

Патрик: «А могу я прислать сжатую информацию не одним файлом, а несколькими частями плюс декомпрессор, который восстановит оригинал?»

Майк: «Да, вполне».

Патрик: «Я принимаю вызов. Как вам можно отправить деньги?»

Майк: «Пришлите чек или банковский перевод. Если вы закажете очень большой файл, то должны обеспечить соответствующий носитель. Вы уже решили, какой объем вам нужен?»

Патрик: «Я до сих пор думаю над оптимальным размером, но полагаю, он будет меньше гигабайта. У вас есть доступ к анонимному ftp-серверу?»

Далее идет обсуждение мелких деталей, из которых выясняется, что Патрик англичанин, но временно живет в Японии, откуда не может послать Майку чек в США, поэтому вышлет наличными по почте.

Видя, что пари (в оригинале - challenge) принимает серьезный оборот, Майк пробует выяснить, каким же гениальным способом Патрик собирается выполнить невозможные (он в этом уверен) условия? Крейг говорит: «подожди и увидишь» и высылает 100 долларов залога. Майк получает деньги, и Патрик сообщает ему размер файла - 3 мегабайта. Приближается кульминация, и здесь мы немного отвлечемся, чтобы понять, в чем же острота пари.

Читатели «КТ» наверняка знакомы с программами-компрессорами, или, как их часто называют, архиваторами. Это замечательные программы. Ими можно сжать почти любой файл, а потом разжать его, вернув первоначальный вид. Архиваторы незаменимы, если большие файлы нужно передать, например, на дискете или электронной почтой. Некоторые файлы удается уменьшить многократно, но зачастую этого мало, и, наверное, каждому читателю приходила в голову блестящая мысль - сжать уже сжатые файлы еще раз! (А потом еще раз, и еще, и еще…) Увы, первая же попытка разочаровывает: сжатые файлы дальше не сжимаются, причем любым архиватором. Почему так происходит?

Чтобы понять это, вспомним, что файлы в компьютере - просто-напросто очень длинные числа. А в математике есть аксиома, гласящая, что число любой длины нельзя точно передать числом меньшей длины, даже если оно короче всего на одну цифру. То есть, скажем, число 176 можно записать четырьмя цифрами, например 90 и 86, но двумя - нельзя ¹.

Здесь можно возразить, что число вроде 300004 можно записать менее чем шестью цифрами, если с помощью специального алгоритма «проглотить» идущие подряд нули. Однако такое «проглатывание» (то есть сжатие) подразумевает, что мы увидели в числе некую закономерность (несколько нулей подряд), точнее говоря - избыточность, и попытались ее записать в другом, более «экономном» виде. Именно такой подход - поиск в данных разного рода закономерностей - и является единственно возможным способом сжатия без потерь. Очевидно, что архиватор старается удалить максимум избыточной информации, поэтому в сжатых файлах ее не остается и сжать их еще раз невозможно.

Как ни странно, избыточной информации нет и в абсолютно случайных данных. Например, в тиражах Спортлото. Парадокс, но и в сжатой энциклопедии, и чистом хаосе результатов рулетки одинаково трудно найти закономерности. В этом наблюдении нам важен один момент: сжатие данных без потерь - это всегда поиск закономерностей в них. Если мы возьмем абсолютно случайные данные, сжать их будет невозможно потому, что в них нет закономерностей. Если же закономерности есть, это не случайные данные, а что-то другое. Таким образом, когда кто-то заявляет, что может сжимать любые файлы, в том числе и случайные, - это заявка на революцию в математике.

Вернемся к нашему пари. Майк Голдмэн, конечно, не хотел платить 5000 долларов и должен был предложить Патрику несжимаемый файл. То есть файл, созданный генератором случайных чисел, причем хорошим генератором. Сделать его совсем не просто. Классические компьютеры - полностью предсказуемые машины. Их действия предопределены программой, поэтому самостоятельно они могут генерировать лишь ПСЕВДОслучайные числа, которые недостаточно хаотичны. Настоящую случайность можно «взять» только из реальной жизни.

Наилучшими генераторами энтропии являются источники радиоактивного излучения. Они испускают заряженные частицы совершенно беспорядочно, поэтому их любят использовать криптографы для создания надежных ключей. Однако есть решения попроще. Например, веб-сайт www.random.org дает посетителям доступ к генератору случайных чисел, созданному на основе обычного радиоприемника. Приемник настроен на частоту, на которой не ведется передача, и в результате источником энтропии служит атмосферный радиошум. Как показывают исследования, это весьма качественный генератор случайности. Специальной программой его результаты можно собирать в файл, и именно так Майк Голдмен получил 3 мегабайта несжимаемых данных для Патрика.

Что же сделал с ними Патрик Крэйг? Процитируем главного героя.

«Тот, кто публично предлагает такое пари, наверняка знаком с теорией информации и скорее всего пришлет вам данные генератора случайных чисел. Теоретически, генератор может выдать все, что угодно, даже осмысленный текст, который можно сжать обычным архиватором. Однако мне не стоило на это рассчитывать, поскольку Майк Голдмен несомненно проверил бы файл, прежде чем высылать мне.

По условиям пари для выигрыша было достаточно сэкономить всего один байт, при этом ничего не говорилось о сохранении имени исходного файла. Теоретически, можно было использовать имя файла для сохранения в нем нескольких байт информации, соответственно уменьшив на них общий размер файла. Однако большинство сочло бы это нечестным трюком.

Другой вариант: отрезав от исходного файла несколько байт, вводить их из командной строки при запуске декомпрессора как необходимые «команды». В этом случае я бы сообщил Майку, что он должен набрать эти недостающие байты вручную. Фактически, это означало бы использование в качестве носителя информации человеческой памяти. Кстати, таким способом можно любой файл уменьшить до нуля, а затем восстановить, набирая байт за байтом на клавиатуре. Однако и это трудно назвать компрессией.

К счастью для меня, Майк разрешил использовать несколько сжатых файлов, и этот нюанс позволил мне легко выполнить условия пари, не прибегая к нечестным приемам».

Что же придумал Патрик? Поставим себя на его место. Итак, у нас есть длинный файл случайных данных, и мы решили найти в нем, например, самую первую букву А. Теперь букву выбросим и в этом месте разрежем файл на две части. У нас получатся два файла, которые в сумме будут на один байт меньше исходного. Чтобы восстановить оригинал, нужно просто склеить две его части, вставив между ними букву А.

Разумеется, исходный файл можно разрезать не на две части, а на три и больше, поскольку выбранная буква встречается много раз. Если мы имеем дело со случайными данными, то любой символ будет встречаться примерно один раз на 256 байт - это элементарный расчет вероятности. Таким образом, разрезая один длинный файл в тех местах, где у него находится буква А, и выбрасывая ее, мы превращаем файл в цепочку маленьких, сберегая при этом четыре байта на каждом килобайте. Остается только написать простейшую программу, которая могла бы склеить из множества нарезанных файлов один большой, первоначальный.

У Патрика эта программа, которую можно назвать декомпрессором, оказалась размером 156 байт. Исходный файл в 3 мегабайта описанным выше способом можно было разделить на 12 тысяч частей, но Патрик остановился после второй сотни, поскольку алгоритм был ясен, а результат очевиден.

В среду 4 апреля Майк Голдмен получил от Патрика письмо. Патрик предлагал взглянуть на результаты и объяснял, что высланный Майком файл был разделен на 218 частей, суммарный объем которых на 217 байт меньше. Программа-декомпрессор занимает 156 байт, кое-что ушло на сохранение имени файла, и общее уменьшение размеров составляет 44 байта. Так что давай, Майк, плати.

Позже Патрик подробно рассказал о своих действиях в конференции Comp.Compress, к общему удовольствию подписчиков дав повод для разговоров на несколько недель. Между тем Майк Голдмен не заплатил обещанные деньги, и вот почему.

Разрезая файл на две части и отбрасывая один байт в месте разреза, Патрик действительно уменьшал содержимое файлов на один байт. Но, кроме основного содержания, у каждого файла есть еще имя, дата создания, несколько атрибутов, координаты расположения на физическом диске и т. д. В результате два файла, длина которых на один байт меньше третьего, все равно занимают на диске больше места.

По этому поводу Патрик заметил, что если операционная система для одного длинного файла требует меньше места, чем для двух коротких, это ее проблемы, а не его.

Формально Патрик прав, и если понимать условия пари буквально, Голдмен должен признать проигрыш, а не уточнять правила на ходу. Поэтому в конференции призывали его «быть мужчиной и заплатить деньги». Однако Майк только вернул Патрику 100 долларов залога, сказав, что проделанный трюк нельзя назвать компрессий информации и он сожалеет, что условия пари были сформулированы нечетко.

К чести Патрика, он не настаивал на награде и признался, что вовсе не рассчитывал получить деньги. По его словам, главной целью было «обхитрить хитреца» - показать, что у Голдмена можно выиграть нарочито самоуверенное пари, причем на условиях самого Голдмена. Без сомнения, это ему блестяще удалось. Жаль только, что все происшедшее не помешает оборотистым мошенникам снова и снова заявлять на весь мир о создании алгоритма, сжимающего все подряд.