Сжатие данных в примерах. Методы сжатия данных

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

Метод кодирования длины серий

Метод кодирования длины серий дает наилучшие результаты, если сжимаемые данные состоят из длинных последовательностей одних и тех же значений. В сущности, такой метод кодирования как раз и состоит в замене подобных последовательностей кодовым значением, определяющим повторяющееся значение и количество его повторений в данной серии. Например, для записи кодированной информации о том, что битовая последовательность состоит из 253 единиц, за которыми следуют 118 нулей и еще 87 единиц, потребуется существенно меньше места, чем для перечисления всех этих 458 бит.

Пример. Используя метод кодирования длины серий последовательность: 111111111100000000000000000 - можно представить в следующем виде: 10.

Метод относительного кодирования

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

Пример. Используя метод относительного кодирования, последовательность цифр: 1476; 1473; 1480; 1477 - можно представить в следующем виде: 1476; -3; +7; -3.

Частотно-зависимое кодирование

Этот метод сжатия данных предполагает применение частотно-зависимого кодирования, при котором длина битовой комбинации, представляющей элемент данных, обратно пропорциональна частоте использования этого элемента. Такие коды входят в группу кодов переменной длины, т.е. элементы данных в этих кодах представляются битовыми комбинациями различной длины. Если взять английский текст, закодированный с помощью частотно-зависимого метода, то чаще всего встречающиеся символы [е, t, а, i] будут представлены короткими битовыми комбинациями, а те знаки, которые встречаются реже , - более длинными битовыми комбинациями. В результате мы получим более короткое представление всего текста, чем при использовании обычного кода, подобного Unicode или ASCII. Построение алгоритма, который обычно используется при разработке частотно-зависимых кодов, приписывают Девиду Хаффману , поэтому такие коды часто называются кодами Хаффмана. Большинство используемых сегодня частотно-зависимых кодов является кодами Хаффмана.

Пример. Пусть требуется закодировать частотно-зависимым методом последовательность: αγααβααγααβαλααβαβαβαβαα, которая состоит из четырех символов α, β, γ и λ. Причем в этой последовательности α встречается 15 раз, β - 6 раз, γ - 2 раза и λ - 1 раз.

Выберем в соответствии с методом Хаффмана следующий двоичный код для представления символов:

α - 1
β - 01
γ - 001
λ - 000

Метод Лемпеля-Зива

Данный метод назван в честь его создателей, Абрахама Лемпеля и Джэкоба Зива . Системы кодирования по методу Лемпеля-Зива используют технологию кодирования с применением адаптивного словаря. В данном контексте термин словарь означает набор строительных блоков, из которых создается сжатое сообщение. Если сжатию подвергается английский текст, то строительными блоками могут быть символы алфавита. Если потребуется уменьшить размер данных, которые хранятся в компьютере, то компоновочными блоками могут стать нули и единицы. В процессе адаптивного словарного кодирования содержание словаря может изменяться. Например, при сжатии английского текста может оказаться целесообразным добавить в словарь окончание ing и артикль the. В этом случае место, занимаемое будущими копиями окончания ing и артикля the, может быть уменьшено за счет записи их как одиночных ссылок вместо сочетания из трех разных ссылок. Системы кодирования по методу Лемпеля-Зива используют изощренные и весьма эффективные методы адаптации словаря в процессе кодирования или сжатия. В частности, в любой момент процесса кодирования словарь будет состоять из тех комбинаций, которые уже были закодированы [сжаты].

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

αβααβλβ

Строка αβααβλβ является уже распакованной частью сообщения. Для того чтобы разархивировать остальной текст сообщения, необходимо сначала расширить строку, присоединив к ней ту часть, которая в ней уже встречается. Первый номер в триплете указывает, сколько символов необходимо отсчитать в обратном направлении в строке, чтобы найти первый символ добавляемого сегмента. В данном случае необходимо отсчитать в обратном направлении 5 символов, и мы попадем на второй слева символ а уже распакованной строки. Второе число в триплете задает количество последовательных символов справа от начального, которые составляют добавляемый сегмент. В нашем примере это число 4, и это означает, что добавляемым сегментом будет ααβλ. Копируем его в конец строки и получаем новое значение распакованной части сообщения: αβααβλβααβλ.

Наконец, последний элемент [в нашем случае это символ α] должен быть помещен в конец расширенной строки, в результате чего получаем полностью распакованное сообщение: αβααβλβααβλα.

Сжатие изображений

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

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

Другим примером системы сжатия изображений является формат JPEG. Это стандарт, разработанный ассоциацией Joint Photographic Experts Group [отсюда и название этого стандарта] в рамках организации ISO. Формат JPEG показал себя как эффективный метод представления цветных фотографий. Именно по этой причине данный стандарт используется производителями современных цифровых фотокамер. Следует ожидать, что он окажет немалое влияние на область цифрового представления изображений и в будущем.

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

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

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

"Сжатие данных"

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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

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

JPEG - для графических данных;

MPG - для для видеоданных;

MP3 - для аудиоданных.

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

GIF, TIFF - для графических данных;

AVI - для видеоданных;

ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

алгоритм RLE (Run Length Encoding);

алгоритмы группы KWE(KeyWord Encoding);

алгоритм Хаффмана.

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:

где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Алгоритмы группы KWE

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

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

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

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).

Алгоритм Хаффмана

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

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

Пусть задан текст, в котором бурва "А" входит 10 раз, буква "В" - 8 раз, "С"- 6 раз, "D" - 5 раз, "Е" и "F" - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Таблица 1.

	Частота вхождения	Битовый код

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Таблица 2.

Формат сжатия	Операционная система MS DOS		Операционная система Windows
	Программа архивации	Программа разархивации	Программа архивации	Программа разархивации

Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:

создание нового архива;

добавление файлов в существующий архив;

распаковывание файлов из архива;

создание самораспаковающихся архивов (self-extractor archive);

создание распределенных архивов фиксированного размера для носителей маленькой емкости;

защита архивов паролями от несанкционированного доступа;

просмотр содержимого файлов разных форматов без предварительного распаковывания;

поиск файлов и данных внутри архива;

проверка на вирусы в архиве к распаковыванию;

выбор и настройка коэффициента сжатия.

Контрольные вопросы

1. Какие факторы влияют на степень избыточности данных? 2. Что такое архив? Какие программные средства называются архиваторами? 3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 4. Приведите примеры форматов сжатия с потерями информации. 5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 7. В чем состоит основная идея алгоритма RLE? 8. В чем состоит основная идея алгоритмов группы KWE? 9. В чем состоит основная идея алгоритма Хаффмана? 10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.

Информатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.

А.П.Микляев, Настольная книга пользователя IBM PC 3-издание М.:, "Солон-Р", 2000, 720 с.

Симонович С.В., Евсеев Г.А., Мураховский В.И. Вы купили компьютер: Полное руководство для начинающих в вопросах и ответах. - М.: АСТ-ПРЕСС КНИГА; Инфорком-Пресс, 2001.- 544 с.: ил. (1000 советов).

Ковтанюк Ю.С., Соловьян С.В. Самоучитель работы на персональном компьютере - К.:Юниор, 2001.- 560с., ил.

Принципы сжатия информации

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

Любой метод сжатия информации включает в себя два преобразования обратных друг другу:

• преобразование сжатия;
• преобразование расжатия.

Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.

Все методы сжатия делятся на два основных класса

• без потерь,
• с потерями.

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

Характеристики алгоритмов сжатия и применимость

Коэффициент сжатия

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

k = S o /S c ,

где k - коэффициент сжатия, S o - размер несжатых данных, а S c - размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть получает выходное сообщение размером, равным входному;
• если k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон:Е:бит составляет ровно 2 n . Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n . Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.

Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон , μ-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:

• среднее (обычно по некоторому тестовому набора данных);
• максимальное (случай наилучшего сжатия);
• минимальное (случай наихудшего сжатия);

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

Допустимость потерь

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

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

Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC , позволяет в большинстве случаев сжать звук в 1,5-2,5 раза, в то время как алгоритм с потерями Vorbis , в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых исполняются:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

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

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

См. также

Wikimedia Foundation . 2010 .

Смотреть что такое "Сжатие информации" в других словарях:

сжатие информации - уплотнение информации — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы уплотнение информации EN information reduction …

СЖАТИЕ ИНФОРМАЦИИ - (сжатие данных) представление информации (данных) меньшим числом битов по сравнению с первоначальным. Основано на устранении избыточности. Различают С. и. без потери информации и с потерей части информации, несущественной для решаемых задач. К… … Энциклопедический словарь по психологии и педагогике

адаптивное сжатие информации без потерь - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN adaptive lossless data compressionALDC … Справочник технического переводчика

уплотнение/сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compaction … Справочник технического переводчика

цифровое сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compression … Справочник технического переводчика

Звук является простой волной, а цифровой сигнал является представлением этой волны. Это достигается запоминанием амплитуды аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за… … Википедия

Процесс, обеспечивающий уменьшение объема данных путем сокращения их избыточности. Сжатие данных связано с компактным расположением порций данных стандартного размера. Различают сжатия с потерей и без потери информации. По английски: Data… … Финансовый словарь

сжатие цифровой картографической информации - Обработка цифровой картографической информации в целях уменьшения ее объема, в том числе исключения избыточности в пределах требуемой точности ее представления. [ГОСТ 28441 99] Тематики картография цифровая Обобщающие термины методы и технологии… … Справочник технического переводчика

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Сжатие данных

1. Информация. Её виды и свойства

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

Сведения об окружающем мире и протекающих в нем процессах, воспринимаемые человеком или специальным устройством.

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

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

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

Для этого в настоящее время изобретено множество способов хранения информации на внешних (относительно мозга человека) носителях и ее передачи на огромные расстояния.

Основные виды информации по ее форме представления, способам ее кодирования и хранения, что имеет наибольшее значение для информатики, это:

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

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

· текстовая - способ кодирования речи человека специальными символами - буквами, причем разные народы имеют разные языки и используют различные наборы букв для отображения речи; особенно большое значение этот способ приобрел после изобретения бумаги и книгопечатания;

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

· видеоинформация - способ сохранения «живых» картин окружающего мира, появившийся с изобретением кино.

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

С появлением компьютеров (или, как их вначале называли в нашей стране, ЭВМ - электронные вычислительные машины) вначале появилось средство для обработки числовой информации. Однако в дальнейшем, особенно после широкого распространения персональных компьютеров (ПК), компьютеры стали использоваться для хранения, обработки, передачи и поиска текстовой, числовой, изобразительной, звуковой и видеоинформации. С момента появления первых персональных компьютеров - ПК (80-е годы 20 века) - до 80% их рабочего времени посвящено работе с текстовой информацией.

Хранение информации при использовании компьютеров осуществляется на магнитных дисках или лентах, на лазерных дисках (CD и DVD), специальных устройствах энергонезависимой памяти (флэш-память и пр.). Эти методы постоянно совершенствуются, изобретаются новые устройства и носители информации. Обработку информации (воспроизведение, преобразование, передача, запись на внешние носители) выполняет процессор компьютера. С помощью компьютера возможно создание и хранение новой информации любых видов, для чего служат специальные программы, используемые на компьютерах, и устройства ввода информации.

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

Свойства информации

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

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

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

3. Достоверность информации. Данные возникают в момент регистрации сигналов, но не все сигналы являются «полезными» - всегда присутствует уровень посторонних сигналов.

5. Доступность информации.

6. Актуальность.

2. Сжатие данных

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

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

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

Алгоритмы сжатия текстов / файлов неизвестного формата

Имеется 2 основных подхода к сжатию файлов неизвестного формата.

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

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

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

3. Программные средства сжатия данных

Если методы сжатия информации применяют к готовым документам. То нередко термин «сжатие данных» подменяют термином «архивация данных», а программные средства, выполняющие эти операции, называют архиваторами.

Архиваторы предназначены для сжатия файлов, т.е. для уменьшения занимаемого ими места на диске. Они позволяют за счет специальных методов упаковки информации сжимать информацию на дисках, создавая копии файлов в один архивный файл. Несмотря на то, что объемы памяти ЭВМ постоянно растут, потребность в архивации не уменьшается.

Итак, архивация может пригодиться:

1) При хранении копий файлов и флоппи-дисках, т.к. флоппи-диск ограничен по размеру;

2) Для освобождения места на жестком диске;

3) При передачи информации по сети.

Архивация информации - это такое преобразование информации, при котором ее объем не уменьшается, а количество информации остается прежним.

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

Степень сжатия информации зависит от типа исходного файла, от используемой программы, а также от выбранного метода упаковки. Наиболее хорошо сжимаются файлы графических объектов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5-40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей -60-90%.

Различными разработчиками созданы много программ-архиваторов. Среди них наиболее распространенные для Windows - WINRAR, WINZIP.

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

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

Сам Zip - алгоритм свободно используется в десятках программ, тем не менее для очень многих пользователей Windows ИМЕННО WinZip является стандартной программой для работы с архивами. Встроенные средства обработки архивов WinZIP позволяют упаковывать, просматривать и извлекать файлы из широко распространенных форматов архивов, таких как ZIP, CAB, Microsoft Compress, GZIP, TAR и т.д. WinZip очень прост и удобен в работе.

Однако не всегда оправдано использовать отдельные архиваторы с их собственными графическими оболочками. Наиболее удобной оболочкой для архиваторов является обычный файловый менеджер, например, Windows Commander, который имеет возможность просматривать и распаковывaть файлы архивов форматов ZTP, ARJ, RAR, TAR, GZ, CAB, ACE. Всё-таки большинство операций с файлами, в том числе и с архивами, выполняются именно в таких менеджерах.

4. Сжатие данных с потерями информации

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

Типы сжатия с потерями

Существуют две основных схемы сжатия с потерями:

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

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

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

Сжатие с потерями против сжатия без потерь

Преимущество методов сжатия с потерями над методами сжатия без потерь состоит в том, что первые существенно превосходят по степени сжатия, продолжая удовлетворять поставленным требованиям.

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

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

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

Звуковые данные, прошедшие сжатие с потерями, не принимаются судами как вещественные доказательства (и даже не берутся во внимание) по причине того, что информация, прошедшая сжатие, приобретает артефакты сжатия и теряет естественные шумы среды, из которой производилась запись. В связи с чем невозможно установить подлинная ли запись или синтезированная. Поэтому важные записи рекомендуется производить в формате ИКМ (PCM) или использовать плёночный диктофон.

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

Методы сжатия данных с потерями

v Компрессия изображений:

· Снижение глубины цвета;

· Метод главных компонент;

· Фрактальное сжатие;

v Компрессия видео:

· Flash (также поддерживает движущиеся изображения JPEG);

· MPEG-1 Part 2;

· MPEG-2 Part 2;

· MPEG-4 Part 2;

v Компрессия звука:

· MP3 - Определён спецификацией MPEG-1;

· Ogg Vorbis (отличается отсутствием патентных ограничений и более высоким качеством);

· AAC, AAC+ - существует в нескольких вариантах, определённых спецификациями MPEG-2 и MPEG-4, используется, например, в Apple Computer;

· eAAC+ - формат, предлагаемый Sony, как альтернатива AAC и AAC+;

· WMA - собственность Microsoft;

информация сжатие архиватор потеря

5. Сжатие данных без потерь информации

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

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате ZIP и Unix-утилите Gzip. Оно также используется как компонент в сжатии с потерями.

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример - исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без.

Техника сжатия без потерь

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

Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных - исполняемые файлы, файлы данных, тексты, графику и т.д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т.д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC - в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: так, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.

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

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:

Преобразование Барроуза - Уилера (блочно-сортирующая предобработка, которая делает сжатие более эффективным)

LZ77 и LZ78 (используется DEFLATE)

Алгоритмы кодирования через генерирование битовых последовательностей:

· Алгоритм Хаффмана (также используется DEFLATE)

· Арифметическое кодирование

Методы сжатия без потерь

· Многоцелевые

· Кодирование длин серий - простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений

· LZW - используется в gif и во многих других.

· Deflate - используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.

· LZMA - используется в 7-zip.

v Сжатие аудио:

· Apple Lossless - ALAC (Apple Lossless Audio Codec);

· Audio Lossless Coding - также известен как MPEG-4 ALS;

· Direct Stream Transfer - DST;

· Free Lossless Audio Codec - FLAC;

v Сжатие графики

· ABO - Adaptive Binary Optimization;

· GIF - (без потерь только для изображений содержащих менее 256 цветов);

· JBIG2 - (с потерями или без Ч/Б изображений);

· JPEG-LS - (стандарт сжатия без потерь / почти без потерь);

· JPEG 2000 - (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего);

· PGF - Progressive Graphics File (сжатие с/без потерь);

· PNG - Portable Network Graphics;

· WMPhoto - (включая метод сжатия без потерь);

v Сжатие видео

· Animation codec;

· CamStudio Video Codec;

6. Хранение информации (текстовой, графической, звуковой)

Хранение информации происходит с помощью определенных носителей информации. Человек хранит свои знания либо в собственной памяти, либо на каких-то внешних носителях.

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

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

В ЭВМ в качестве устройств для записи, чтения информации стали использоваться: устройства чтения перфокарт; накопители на магнитной ленте, накопители на гибких (дисковод) и жестких (винчестер) магнитных дисках; накопители на компакт-дисках (CD-ROM) и другие более современные устройства накопления и хранения информации.

Библиографический список

1. Федеральный закон Российской Федерации «Об информации, информатизации и защите информации» от 27.07.2006 №149-ФЗ.

2. Левин А.Ш. Самоучитель работы на компьютере. - СПб.: Питер, 2006. - 655 с.

3. Романова Н.И. Основы информатики. - СПб.: Политехника, 2004. -224 с.

4. Симонович С.В. Информатика. Базовый курс. - СПб.: Питер, 2008 -640 с.

Размещено на Allbest.ru

Подобные документы

Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.

курсовая работа , добавлен 26.01.2011


Классификация и основные характеристики метода сжатия данных. Вычисление коэффициентов сжатия и оценка их эффективности. Алгоритмы полиноминальных, экстраполяционных и интерполяционных методов сжатия и их сравнение. Оптимальное линейное предсказание.

курсовая работа , добавлен 17.03.2011


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

презентация , добавлен 06.01.2014


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

реферат , добавлен 05.12.2013


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

презентация , добавлен 05.04.2011


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

контрольная работа , добавлен 12.03.2011


Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.

практическая работа , добавлен 24.04.2014


Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.

курсовая работа , добавлен 28.07.2009


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

дипломная работа , добавлен 13.10.2015


Программы для создания архивов. Эффективность сжатия данных как важнейшая характеристика архиваторов. Основные методы сжатия данных. Характеристика программы для упаковки текстов и программ WinRar. Распаковка файлов, упаковка файлов и папок в общий архив.

Введение.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и

количество времени, необходимого для передачи информации по каналу установленной

ширины пропускания. Это есть форма кодирования. Другими целями кодирования

являются поиск и исправление ошибок, а также шифрование. Процесс поиска и

исправления ошибок противоположен сжатию - он увеличивает избыточность данных,

когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя

из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск

шифpа доступным для взломщика статистическим методом.

Рассмотpим обратимое сжатие или сжатие без наличия помех, где первоначальный

текст может быть в точности восстановлен из сжатого состояния. Необратимое или

ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как

человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов,

записанных на естественных и на искусственных языках, поскольку в этом случае

ошибки обычно недопустимы. Хотя первоочередной областью применения

рассматриваемых методов есть сжатие текстов, что отpажает и наша терминология,

однако, эта техника может найти применение и в других случаях, включая обратимое

кодирование последовательностей дискретных данных.

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое

представление, т.к. более быстрая передача данных и сокpащение пpостpанства для

их хpанения позволяют сберечь значительные средства и зачастую улучшить

показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все

возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно

использовать для преодоления некотоpых физических ограничений, таких как,

напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

ПРИМЕНЕНИЕ РАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.

Алгоритмы сжатия могут повышать эффективность хранения и передачи данных

посредством сокращения количества их избыточности. Алгоритм сжатия берет в

качестве входа текст источника и производит соответствующий ему сжатый текст,

когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из

него на выходе первоначальный текст источника. Большинство алгоритмов сжатия

рассматривают исходный текст как набор строк, состоящих из букв алфавита

исходного текста.

Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть длина

представления в битах, а H(S) - энтропия - мера содержания информации, также

выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать

строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из

исходного текста извлекать по одной букве некоторого случайного набоpа,

использующего алфавит А, то энтропия находится по формуле:

H(S) = C(S) p(c) log ---- ,

где C(S) есть количество букв в строке, p(c) есть статическая вероятность

появления некоторой буквы C. Если для оценки p(c) использована частота появления

каждой буквы c в строке S, то H(C) называется самоэнтропией строки S. В этой

статье H (S) будет использоваться для обозначения самоэнтропии строки, взятой из

статичного источника.

Расширяющиеся деревья обычно описывают формы лексикографической упорядоченности

деpевьев двоичного поиска, но деревья, используемые при сжатии данных могут не

иметь постоянной упорядоченности. Устранение упорядоченности приводит к

значительному упрощению основных операций расширения. Полученные в итоге

алгоритмы предельно быстры и компактны. В случае применения кодов Хаффмана,

pасширение приводит к локально адаптированному алгоритму сжатия, котоpый

замечательно прост и быстр, хотя и не позволяет достигнуть оптимального сжатия.

Когда он применяется к арифметическим кодам, то результат сжатия близок к

оптимальному и приблизительно оптимален по времени.

КОДЫ ПРЕФИКСОВ.

Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах

Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве

кодом переменной длины. Более частые буквы представляются короткими кодами,

менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться

свойствам префикса, а именно: код, использованный в сжатом тексте не может быть

префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист

соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево кода

префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при

обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви,

а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый

лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а

внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости

букв в исходном тексте, что ведет к необходимости его двойного просмотра - один

для получения значений частот букв, другой для проведения самого сжатия. В

последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы

в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется

за один шаг, т.к. код, используемый для каждой буквы исходного текста, основан

на частотах всех остальных кpоме нее букв алфавита. Основы для эффективной

реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал

практическую версию такого алгоритма, а Уиттер его pазвил.

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на

букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно

составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда

лежат в пределах одного бита на букву исходного текста от H (они достигают этот

предел только когда для всех букв p(C) = 2). Существуют алгоритмы сжатия

которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например,

присваивает слова из аpхива фиксированной длины строкам исходного текста

пеpеменной длины, а арифметическое сжатие может использовать для кодирования

букв источника даже доли бита.

Применение расширения к кодам префикса.

Расширяющиеся деревья были впервые описаны в 1983 году и более подpобно

рассмотрены в 1985. Первоначально они понимались как вид самосбалансиpованных

деpевьев двоичного поиска, и было также показано, что они позволяют осуществить

самую быструю реализацию приоритетных очередей. Если узел расширяющегося дерева

доступен, то оно является расширенным. Это значит, что доступный узел становится

корнем, все узлы слева от него образуют новое левое поддерево, узлы справа -

новое правое поддерево. Расширение достигается при обходе дерева от старого

корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена

расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон показали, что расширяющиеся деревья статично оптимальны.

Другими словами, если коды доступных узлов взяты согласно статичному

распределению вероятности, то скорости доступа к расширяющемуся дереву и

статично сбалансированному, оптимизированному этим распределением, будут

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

длинных сериях доступов. Поскольку дерево Хаффмана представляет собой пример

статично сбалансированного дерева, то пpи использовании расширения для сжатия

данных, pазмер сжатого текста будет лежать в пределах некоторого коэффициента от

размера архива, полученного при использовании кода Хаффмана.

Как было первоначально описано, расширение применяется к деревьям, хранящим

данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все

свои данные только в листьях. Существует, однако, вариант расширения, называемый

полурасширением, который применим для дерева кодов префикса. При нем целевой

узел не перемещается в корень и модификация его наследников не производится,

взамен путь от корня до цели просто уменьшается вдвое. Полурасширение достигает

тех же теоретических границ в пределах постоянного коэффициента, что и

расширение.

В случае зигзагообразного обхода лексикографического дерева, проведение как

расширения, так и полурасширения усложняется, в отличие от прямого маршрута по

левому или правому краю дерева к целевому узлу. Этот простой случай показан на

рисунке 2. Воздействие полурасширения на маршруте от корня (узел w) до листа

узла A заключается в перемене местами каждой пары внутренних следующих друг за

другом узлов, в результате чего длина пути от корня до узла-листа сокращается в

2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня,

включаются в новый путь (узлы x и z), а более близкие из него

исключаются (узлы w и y).

Сохранение операцией полурасширения лексикографического порядка в деревьях кода

префикса не является обязательным. Единственно важным в операциях с кодом

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

дереву, используемому процедурой развертывания. Любое его изменение, допущенное

между последовательно идущими буквами, производится только в том случае, если

обе процедуры осуществляют одинаковые изменения в одинаковом порядке.

Hенужность поддержки лексикографического порядка значительно упрощает проведение

операции полурасширения за счет исключения случая зигзага. Это может быть