История развития теории сжатия информации


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

История развития теории сжатия информации

В сороковых годах ученые, работающие в области информационных технологий, ясно поняли, что можно разработать такой способ хранения данных, при котором пространство будет расходоваться более экономно. Клод Шеннон, изучая нюансы различий между семантикой (semantics) (что некая сущность значит) и синтаксисом (syntax) (как некая сущность выражается), разработал большинство базовых понятий этой теории. Понимание того, что одно и то же значение (семантика) может быть реализовано различными способами (синтаксис), приводит к закономерному вопросу: "Какой способ выражения чего-либо является наиболее экономичным?" Поиск ответа на этот вопрос привел Шеннона к мысли об энтропии, которая, проще говоря, соотносится с количеством, содержащейся в файле полезной информации. Методы сжатия пытаются увеличивать энтропию файла, то есть уменьшать длину файла, сохраняя при этом всю информацию.

Однако, Шеннон не был первым, кто задумывался о сущности информации и определении ее количества. Первый шаг на этом пути сделал в 1928 г. Хартли. Основной полученный им результат можно сформулировать примерно так: если в заданном множестве, содержащем N элементов, выделен некоторый элемент x, о котором известно лишь, что он принадлежит этому множеству, то, чтобы найти x, необходимо получить количество информации, равное log2 N. Эту формулу обычно называют формулой Хартли.

Формула Хартли является частным случаем более общей формулы Шеннона, позволяющей найти количество информации в случайном сообщении фиксированного алфавита. Пусть X1, ..., Xn - символы этого алфавита, P1, ..., Pn - вероятности их появления в тексте сообщения, тогда формула Шеннона принимает вид:

H = P1*log2(1 / P1) + ... + Pn*log2(1 / Pn),

где H - количество бит информации в одном символе сообщения, или энтропия символа сообщения. Это число показывает минимальное среднее число бит, необходимых для представления одного символа алфавита данного сообщения.

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

Доказательство Шеннона не было конструктивным, т.е. не содержало способа построения этих оптимальных кодов, а лишь показывало их существование. До появления работы Шеннона, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этой работы начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте. Например, часто в файлах некоторые значения байта встречаются чаще других. Таким образом, за счет использования для каждого значения байта кода различной длины можно значительно уменьшить общий размер данных. Эта базовая идея лежит в основе алгоритмов сжатия Шеннона-Фано (Shannon-Fano) и Хаффмана (Huffman). Подобные алгоритмы выбирают более короткие коды для часто встречающихся и более длинные для редко встречающихся значений байта. Обычно текстовые файлы (в которых одни значения байтов повторяются гораздо чаще других) они сжимают довольно хорошо.

Более тридцати лет алгоритм сжатия Хаффмана и его варианты оставались наиболее популярными методами. Однако в 1977 два исследователя из Израиля предложили совершенно другой подход к этой проблеме. Абрахам Лемпел и Якоб Зив выдвинули идею формирования "словаря" общих последовательностей данных. При этом сжатие данных осуществляется за счет замены записей соответствующими кодами из словаря. Существуют два алгоритма, в настоящее время известные как LZ77 и LZ78. Они уже не требуют включения словаря данных в архив, так как если вы формируете ваш словарь определенным способом, программа декодирования может его восстанавливать непосредственно из ваших данных. К сожалению, LZ77 и LZ78 тратят много времени на создание эффективного словаря. Лемпел был приглашен фирмой Sperry для оказания им помощи в разработке способа наиболее эффективной упаковки данных на компьютерных лентах. В этой же фирме Терри Велч (Terry Welch) расширил алгоритм LZ78, создав новый вариант, широко известный, как LZW.

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

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

Алгоритмы LZ-стиля (включая LZW, LZ77, LZ78 и многие другие варианты) очень популярны везде, где требуется универсальное сжатие. LZW используется в стандарте модема V.42bis, протоколе передачи данных ZModem, форматах GIF, TIFF, ARC и других прикладных программах. Другие алгоритмы LZ используются в дисковых утилитах сжатия типа DoubleSpace и Stacker, графических форматах типа PNG, а также в универсальных утилитах архивирования и сжатия, включая ZIP, GZIP и LHA.

Помимо пользующихся большим вниманием алгоритмов, базирующихся на словаре, существуют и другие подходы. Алгоритм сжатия Хаффмана (Huffman), основанный на статистических колебаниях распределения некоторых значений байтов, лег в основу нескольких очень эффективных методов сжатия, известных, как арифметическое кодирование (arithmetic encoding), энтропийное кодирование (entropy coding) или Q-кодирование (Q-coding). Арифметическое кодирование улучшает сжатие Хаффмана двумя путями. Первое усовершенствование заключается в том, что оно не требует, чтобы выбранные коды были целым числом бит. В то время как сжатие Хаффмана могло выбирать двух- и четырехбитовые коды, программа арифметического кодирования может использовать код длиной 6,23 бит. (Что такое 0,23 бит - чисто философский вопрос, если Вас это заинтересовало, то в отдельном разделе Вы найдете другое объяснение арифметического кодирования.) Второе усовершенствование (которое может также использоваться в сжатии Хаффмана) заключается в том, что арифметическое кодирование использует более сложную статистику. Она не просто следит за частотой появления байта в файле, а оценивает частоту его появления в определенном контексте. Например, при использовании исходного алгоритма сжатия Хаффмана символ "u", встречающийся не слишком часто, мог бы получать довольно длинный код. Но в сложной программе арифметического кодирования символ "u", следующий за "q", будет закодирован очень компактно, так как высока вероятность того, что "u" следует сразу за "q". Комбинация этих двух усовершенствований приводит очень к эффективному сжатию.

Другие методы сжатия предназначены для данных определенного типа, а потому они плохо подходят для архивирования. Многие усовершенствованные методы, появлявшиеся в последнее время, основывались на синтезе этих трех методов (например, использование кодов Хаффмана для записей словаря) или выполнения сложной предварительной обработки данных, увеличивающей эффективность сжатия одним из этих методов. (Файлы JPEG с выборочно удаленными графическими данными можно затем сжать с помощью метода Хаффмана или арифметического кодирования. Для более эффективного кодирования с помощью методов, базирующихся на словаре, PNG преобразует графические данные, используя для этого простую методику фильтра.)

Возможно, одним из наиболее существенных событий за последние несколько десятилетий в области алгоритмов сжатия стало появление патентов на программное обеспечение. С 1981 United States Patent and Trademark Office (USPTO) начал принимать заявки на патентование алгоритмов программного обеспечения. Многие из представленных патентов были по методам сжатия. Наиболее известные из них - патенты фирмы Unisys на алгоритм сжатия LZW и патенты фирмы IBM на арифметическое кодирование. К сожалению, первоначально работа по обработке заявок в USPTO была поставлена неважно. В результате чего разным людям предоставлялись различные патенты на один и тот же алгоритм (причем иногда с почти идентичной формулировкой). Некоторые из этих патентов оспаривались в судебном порядке, но высокая стоимость судебного разбирательства исков резко снижает количество таких претендентов.

Один положительный результат введения патентования вряд ли приходится оспаривать. Патентование программного обеспечения спровоцировало появление огромного количества работ по разработке новых алгоритмов сжатия (большая часть которых быстро патентуется их изобретателями). Однако другой эффект был абсолютно отрицательный. Многие из алгоритмов сжатия использовались специфическим образом, например, как часть международных стандартов (V.42bis и JPEG). Кроме того, отдельные компании и пользователи скопировали общедоступный код (так, реализация compress LZW широко копировалась для самых разных целей). Финансовые штрафы за использование этих алгоритмов (в форме авторских отчислений к владельцам патента) отвращали от поддержки этих стандартов авторов условно-бесплатного и бесплатного программного обеспечения или бесплатных библиотек. Некоторые компании публично объявили о том, что они не будут требовать авторских отчислений за использование их запатентованных алгоритмов в бесплатном программном обеспечении. Однако так поступили далеко не все. Пока неясно, как этот конфликт отразится на индустрии бесплатного программного обеспечения и на патентном законодательстве. По крайней мере, одна организация, League for Programming Freedom, борется с патентами программного обеспечения и предпринимает активные шаги по их отмене.

Сжатие не совершенно

Алгоритмы сжатия полезны, но и они имеют свои ограничения. Наиболее очевидное ограничение состоит в том, что никакой из методов сжатия (или комбинация методов сжатия) не совершенен. Некоторые данные могут даже, как это ни парадоксально, в результате применения одной из техник сжатия увеличиваться в размерах. Внимательно смотрите на то, как работает алгоритм сжатия. Заявление о том, что алгоритм может уменьшить в размере файлы с самыми разными типами данных, требует особого внимания. Хорошо написанные программы сжатия помещают в начало выходных данных маркер, указывающий на то, каким методом данные были сжаты. Если данные сжать не удалось, маркер указывает, что данные "не сжаты". При этом размер файла увеличивается на размер маркера.

Иногда программы сжатия утверждают, что они сжимают практически "любой файл на 16 килобайт" или "сжимают каждый файл, по крайней мере, на 30 процентов". Любое такое утверждение просто неверно, хотя некоторые весьма престижные издания стали публиковать объявления о таких программах. В 1992 году фирма WEB Technologies объявила о выходе новой программы сжатия DataFiles/16. При этом фирма сделала ряд интересных заявлений. Прежде всего, она утверждала, что с "помощью неоднократного использования DataFiles/16 фактически любое количество данных может быть уплотнено до 1024 байт".

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

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

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

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

Реальным доказательством работы метода является не кодирование (сжатие), а декодирование (распаковка). Метод сжатия, не позволяющий восстанавливать первоначальные данные, вряд ли полезен.

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

Это может показаться Вам несущественным, но все же давайте точно определим, сколько на жестком диске файлов. Так как в каждом байте восемь бит, то у Вас должно быть 2 в степени 80 000 файлов, причем размер каждого из них точно 10 000 байт. В результате мысленного эксперимента у нас по-прежнему останется 2 в степени 80 000 файлов, каждый из которых будет короче чем 10 000 байт. Однако не совсем понятно, каким образом могут получиться два совершенно одинаковых "сжатых" файла! А ведь именно это мы и получаем, поскольку не так уж и много существует файлов короче 10000 байтов. Предположив, что полученные файлы отличаются друг от друга по размеру всего на один байт, то есть 9 999 байтов, затем 9 998 байтов и так далее, вы получите меньше чем 2 в степени 80 000 возможных вариантов.

Таким образом, вы приходите к важному выводу, что по крайней мере два сжатых файла должны быть идентичны. Если не вся логическая цепочка, приводящая к этому выводу, для Вас очевидна, представьте, что у Вас есть пять перевернутых карт. Так как существуют только четыре варианта масти, вы знаете, что две из них имеют одинаковую масть (возможно, что все пять карт имеют одинаковую масть, но Вы не можете об этом знать наверняка). В данном случае применялся тот же принцип: эксперимент предполагал наличие 2 в степени 80 000 файлов, однако после сжатия возможное количество неодинаковых файлов стало меньше этого значения. Так как их число не должно было измениться, то по меньшей мере два файла должны быть одинаковы.

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

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

Использованная литература:

Тим Кенцл, - Форматы файлов Internet, - 1997, - В переводе на русский язык, издательство "Питер".

Sarmin Alexey