О сжатии несжимаемых данных. Интересная статья

[jangle]

Сжатие информации и несжимаемые файлы

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

Закономерно возникает вопрос: а зачем сейчас нужно сжимать файлы, если все основные технические характеристики персональных компьютеров каждые полтора-два года удваиваются? Оперативная память современной персоналки от 128 до 512 мегабайт, дисковая память вообще исчисляется десятками гигабайт. Казалось бы, можно особенно не заботиться о размерах файлов.

Но интерес к сжатию файлов по-прежнему высок. Можно выделить две основные причины такого интереса. Первая, на персональных компьютерах стали воспроизводить и обрабатывать звук и изображение. Звуковые, графические и особенно видео файлы по объему памяти требуют на порядки больше памяти, чем текстовые. Одна фотография 15х20 см с хорошим разрешением 600 точек на дюйм или всего одна десятиминутная музыкальная композиция по объему превышают собрание сочинений Чехова.

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

Архиваторы уменьшают некоторые файлы в 5-10 раз. За счет чего удается так сильно сократить размер файла? Некоторые файлы построены неоптимально с точки зрения их объема. Например, распространенные архиваторы сжимают большие файлы Microsoft Word в пять-шесть раз, а маленькие почти в десять. Чтобы прочесть такой сжатый текстовый файл, его нужно разжать той же самой программой.

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

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

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

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

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

Интернет - очень удобная среда для общения профессионалов. Удаленные друг от друга специалисты из разных стран могут обсуждать проблемы своей области. В Сети хорошо известна сетевая иерархия Usenet. Она объединяет тысячи дискуссионных групп на самые разные темы. Есть там и группа под названием COMP.COMPRESS. В ней специалисты обсуждают компрессию, т.е. сжатие информации. Участие в обсуждениях группы требует значительной подготовки. Поэтому случайные посетители в COMP.COMPRESS надолго не задерживаются. Правда, время от времени кем-то из новичков высказывается мнение, действующее на специалистов по сжатию примерно так же, как на физиков проекты вечного двигателя, а на историков - сочинения Фоменко. Условно проблему можно назвать "чудо-компрессор".

Как правило, речь идет о том, что сотрудники малоизвестной компании разработали революционный алгоритм или даже программу для многократного сжатия информации. Обычно утверждается, что сжатие идёт без потерь, и (самое главное) - во много раз сжимается любая информация. При внимательном рассмотрении оказывается, что это - блеф, но, тем не менее, эта idea fix регулярно возникает на страницах компьютерной прессы. Характерный пример. В апреле 92-го года компания WEB Technologies объявила о создании программы, сжимающей в 16 раз любые файлы размером больше 64-х килобайта. Были другие фирмы, которые заявляли о столь же удивительных параметрах своих программ. Некоторым из них удалось даже запатентовать собственные алгоритмы, однако, в результате, подобные проекты оказались мыльными пузырями.

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

Если говорить о сжатии без потерь, то в нём уже давно не было пионерских работ. Последний принципиально новый алгоритм безпотерьного сжатия был изобретён в 80-х годах и пока мало применяется из-за большой сложности. Кроме того, как уже говорилось, есть данные, которые вообще нельзя сжать без потерь. Это, во-первых - случайная информация, а во вторых - сжатая ранее. Если допустить, что компрессор сжимает без потерь любые файлы, то можно взять файл и уменьшить его один раз, затем опять пропустить через компрессор и опять уменьшить. Если операцию повторять снова и снова, то, в конце концов, файл сожмётся до одного бита, сохранив всю полезную информацию, что, конечно - абсурд.

Несмотря на это, благодаря случайным посетителям, слухи о чудо-компрессорах регулярно проникают в группу COMP.COMPRESS и раздражают её старожилов. В один прекрасный день, чтобы покончить с вопросом раз и навсегда, один из профессионалов, Майк Голдмэн (Mike Goldman), предложил всем обладателям чудо компрессора выплатить денежное вознаграждение. Он написал:

Майк Голдмен

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

Александр Костинский

Другими словами, если у вас есть программа, на самом деле сжимающая любую информацию, то вы легко можете заработать пять тысяч долларов. Предложение Голдмена, было выложено в Интернете http://www.faqs.org/faqs/compression-fa ... ion-8.html вместе с подробными объяснениями, почему нельзя сжать случайную информацию и почему архиватор, сжимающий любые данные - невозможен. Пари оставалось без ответа несколько лет, но 26-го марта прошлого года, по электронной почте Голдмену пришло письмо от человека по имени Патрик Крейг (Patrick Craig) в нем писалось:

Патрик Крейг

Я прочитал ваше предложение. Звучит очень заманчиво, оно всё еще в силе? Если да, то хотелось бы узнать детали о декомпрессоре - он должен запускаться на любой машине или достаточно какой-то одной платформы, например Linux?

Майк Голдмен

Да, предложение в силе. Linux-а достаточно. Вы хотите рискнуть?

Патрик Крейг

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

Майк Голдмен

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

Патрик Крейг

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

Майк Голдмен

Да, вполне.

Патрик Крейг

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

Майк Голдмен

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

Патрик Крейг

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

Александр Костинский

Далее идёт обсуждение мелких деталей, из которых выясняется, что обладатель чудо компрессора - англичанин. Он сейчас живёт в Японии, откуда не может послать чек в США Майку, поэтому вышлет деньги наличными по почте. Видя, что вызов принят, Майк пробует выяснить - каким же способом Патрик собирается выполнить теоретически невозможные условия, но тот не сдаётся, отвечает: "подожди, увидишь" и высылает деньги. Заметим, что переговоры уместились в одиннадцать электронных писем и прошли всего за несколько часов. Наличные идут по обычной почте из Японии в США четверо суток. Майк получает деньги и Патрик сообщает ему размер файла, который он готов уменьшить. Он требует 3 мегабайта. Но что же предлагал сжать всем желающим Майк Голдмен?

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

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

Что же сделал с ними Патрик Крэйг? Свою версию событий он поместил в Интернете:

Патрик Крейг

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

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

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

Александр Костинский

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

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

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

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

Обо всем этом возмутитель спокойствия подробно рассказал (http://www.geocities.com/patchnpuki/oth ... ession.htm)

в дискуссионной группе COMP.COMPRESS к общему удовольствию всех подписчиков, которые несколько недель обсуждали неожиданный результат. (http://groups.google.com/groups?hl=en&i ... 8426e2de35 ).

Между тем, Майк Голдмен не заплатил обещанные пять тысяч и объяснил свои действия так:

Майк Голдмен

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

Александр Костинский

На это Патрик Крейг заметил:

Патрик Крейг

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

Александр Костинский

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

К чести Патрика Крейга, он не настаивал на награде и признался позже, что вовсе не рассчитывал заработать пять тысяч долларов. Его главной целью было "обхитрить хитреца" - показать, что у самоуверенного Голдмена можно выиграть, причём на его условиях, если рассматривать проблему, как головоломку, используя нечеткую постановку задачи.

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

http://archive.svoboda.org/programs/sc/ ... 041602.asp

[Debugger]

Интересно!

[FaKk2]

Интернет - очень удобная среда для общения профессионалов.

Где, где можно записаться в этот Интернет?!