Сжатие без потерь

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

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

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

Содержание

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

Легко доказывается теорема.

Для любого N нет алгоритма сжатия без потерь, который:

  1. Любой файл длиной не более N байтов или оставляет той же длины, или уменьшает.
  2. Существует файл длиной не более N, который уменьшается хотя бы на один байт.

Доказательство. Не ограничивая общности, можно предположить, что уменьшился файл A длины ровно N. Обозначим алфавит как Σ. Рассмотрим множество \Sigma^0 \cup \Sigma^1 \cup \ldots \cup \Sigma^{N-1} \cup \{ A \}. В этом множестве 256^0 + 256^1 + \ldots + 256^{N-1} + 1 исходных файлов, в то время как сжатых не более чем 256^0 + 256^1 + \ldots + 256^{N-1}. Поэтому функция декомпрессии неоднозначна, противоречие. Теорема доказана.

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

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

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

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

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

Полный список смотрите в Категория:Сжатие данных

[править] Многоцелевые

  • Кодирование длин серий — простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений
  • LZW — используется в gif и во многих других.
  • Deflate — используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.
  • LZMA — используется в 7-zip.

[править] Сжатие аудио

[править] Сжатие графики

  • ABO — Adaptive Binary Optimization
  • GIF — (без потерь только для изображений содержащих менее 256 цветов)
  • JBIG2 — (с потерями или без Ч/Б изображений)
  • JPEG-LS — (стандарт сжатия без потерь/почти без потерь)
  • JPEG 2000 — (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего)
  • PGF — Progressive Graphics File (сжатие с/без потерь)
  • PNG — Portable Network Graphics
  • Qbit Lossless Codec — фокусируется на intra-frame («одна картинка») сжатии без потерь
  • TIFF
  • WMPhoto — (включая метод сжатия без потерь)

[править] Сжатие видео

[править] Сжатие текстов

  • PPM — архиватор HA (автор Harry Hirvola), использующий алгоритм PPM, известен высокой степенью сжатия на текстовых файлах; по этому параметру он превосходит даже RAR, появившийся несколько лет спустя. Поэтому появившиеся в конце 90-х годов компакт-диски наподобие «Библиотека в кармане» использовали именно HA.

[править] Примеры алгоритмов

  • Семейство алгоритмов Лемпеля-Зива
  • RLE (Run-length encoding — Кодирование длин серий)

[править] Примеры форматов и их реализаций

[править] См. также

[править] Ссылки

Источник — «http://ru.wikipedia.org/wiki/%D0%A1%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%B1%D0%B5%D0%B7_%D0%BF%D0%BE%D1%82%D0%B5%D1%80%D1%8C»