Компрессия (стр. 1 )

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1.  Компрессия (сжатие) данных, техника и типы.

1.1  Краткий обзор понятий.

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

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

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

1.3.2  Примеры сжатия данных с потерями.

1.4 Сжатие данных без потерь.

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

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

2. Методы сжатия (компрессии данных).

2.1 Алгоритм Зива-Лемпеля (LZ*).

2.1.1 Принцип скользящего окна.

2.1.2 Механизм кодирования совпадений.

2.1.3 Недостатки алгоритма.

2.1.4 LZ78.

2.2 Алгоритм Лемпеля — Зива — Велча (LZW).

2.2.1 Алгоритм.

2.2.2 Применение.

2.2.3 Пример.

2.2.4 Кодирование.

2.2.5 Декодирование.

2.2.6 Патенты.

2.2.7 Unisys, GIF и PNG.

2.3 Локально адаптивный алгоритм сжатия.

2.4 Сжатие данных с использованием преобразования Барроуза-Вилера.

2.5 Метод Шеннона-Фано.

2.6 Статический алгоритм Хаффмана.

3. Методы компрессии данных для изображений.

3.1 Алгоритм фрактального сжатия.

3.2 Сжатие с использованием вейвлет.

3.3 JPEG.

4. Архиваторы.

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

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

В данной работе рассматриваются существующие на сегодняшний день методы компрессии данных.

Компрессия (сжатие) данных.

1.1  Краткий обзор понятий.

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.2  Примеры сжатия данных с потерями.

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

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

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

● JPEG

● Вэйвлетная компрессия

● JPEG 2000

● DjVu

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

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

● H.261

● H.263

● H.264/MPEG-4 AVC

● MNG (поддерживает движущиеся изображения JPEG)

● Motion JPEG

● MPEG-1 Part 2

● MPEG-2 Part 2

● MPEG-4 Part 2

● Ogg Theora (отличается отсутствием патентных ограничений)

● Sorenson video codec

● VC-1 — попытка Microsoft выпустить открытую спецификацию для формата WMV

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

Музыка

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

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

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

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

● Musepack

● WMA — собственность Microsoft

● ADPCM

● ATRAC

● Dolby AC-3

● DTS

● MP2

● VQF

Речь

● CELP

● G.711

● G.726

● HILN

● Speex (отличается отсутствием патентных ограничений)

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

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

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

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

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

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

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

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

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