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

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

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

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

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

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

Содержание

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

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

Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных — исполняемые файлы, файлы данных, тексты, графику и т. д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т. д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 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.

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

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

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

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


Шестерня Это незавершённая статья о технике. Вы можете помочь проекту, исправив и дополнив её.
Это примечание по возможности следует заменить более точным.
Источник — «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»