Сжатие информации

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

Все это возможно благодаря важному свойству информации – избыточности. Это означает, что человек понимает содержание информации, даже если получает ее не всю, а частично, в основном только первые «символы» формы представления.

Существует много веских причин выделять ресурсы ЭВМ в расчете на сжатое представление, т.к. более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ.

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

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

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

Нужно отметить, что в алгоритме Хаффмана для кодирования одной буквы сообщения в любом случае нужно использовать хотя бы один бит кода. Существует другой вид сжатия, который позволяет не кодировать некоторые фразы, а то и целые предложения. Такой алгоритм называется алгоритмом Лемпеля-Зива (LZ-78).

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

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