Просмотр кода страницы Сжатие без потерь

{{Значения|Сжатие}}
[[Файл:Veri_sıkıştırma.jpg|мини]]
'''Сжатие данных без потерь''' ({{lang-en|lossless data compression}}) — класс алгоритмов [[сжатие данных|сжатия данных]] (видео, аудио, графики, документов, представленных в цифровом виде, программ на языках программирования и в машинных кодах и многих других видов данных), при использовании которых закодированные данные однозначно могут быть восстановлены с точностью до [[бит]]а, [[пиксель|пикселя]], [[воксел]]я и т.д. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от [[Сжатие данных с потерями|сжатия данных с потерями]]. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.

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

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

== Сжатие и [[комбинаторика]] ==
Легко доказывается теорема.

{{теорема|Для любого ''N'' > 0 нет алгоритма сжатия без потерь, который:
# Любой файл длиной не более ''N'' байт или оставляет той же длины, или уменьшает.
# Уменьшает некоторый файл длиной не более ''N'' хотя бы на один байт.}}

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

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

Так что несжимаемые фрагменты не приведут к бесконтрольному «раздуванию» архива. «Реальных» же файлов длины ''N'' намного меньше, чем <math>256^{N}</math> (говорят, что данные имеют низкую [[информационная энтропия|информационную энтропию]]) — например, маловероятно, чтобы буквосочетание «щы» встретилось в осмысленном тексте, а в [[импульсно-кодовая модуляция|оцифрованном звуке]] уровень не может за один семпл прыгнуть от 0 до 100 %. К тому же за счёт специализации алгоритмов на некоторый тип данных (текст, графику, звук и т. д.) удаётся добиться высокой степени сжатия: так, применяющиеся в [[архиватор]]ах универсальные алгоритмы сжимают звук примерно на треть (в 1,5 раза), в то время как [[FLAC]] — в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: например, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.

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

 00 → 0
 01 → 10
 10 → 110
 11 → 111

В таком случае шестнадцать битов

 00 01 00 00 11 10 00 00

будут преобразованы в тринадцать битов

 0 10 0 0 111 110 0 0

Такая подстановка является [[префиксный код|префиксным кодом]], то есть обладает такой особенностью: если мы запишем сжатую строку без пробелов, мы всё равно сможем расставить в ней пробелы — а значит, восстановить исходную последовательность. Наиболее известным префиксным кодом является [[код Хаффмана]].

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

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:
* [[Преобразование Барроуза — Уилера]] (блочно-сортирующая пре-обработка, которая делает сжатие более эффективным)
* [[LZ77|LZ77 и LZ78]] (используется [[Deflate]])
* [[LZW]]

Алгоритмы кодирования через генерирование битовых последовательностей:
* [[Алгоритм Хаффмана]] (также используется [[Deflate]])
* [[Арифметическое кодирование]]

== Методы сжатия без потерь ==
{{список примеров|дата=2014-08-26}}
Полный список смотрите в [[:Категория:Сжатие данных]]

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

=== Сжатие аудио ===
* [[Apple Lossless]] — ALAC (Apple Lossless Audio Codec)
* [[Audio Lossless Coding]] — также известен как MPEG-4 ALS
* [[Direct Stream Transfer]] — DST
* [[Dolby TrueHD]]
* [[DTS-HD Master Audio]]
* [[FLAC|Free Lossless Audio Codec]] — FLAC
* [[MLP|Meridian Lossless Packing]] — MLP
* [[Monkey's Audio]] — Monkey’s Audio APE
* [[OptimFROG]]
* [[RealPlayer]] — RealAudio Lossless
* [[Shorten]] — SHN
* [[TAK]] — (T)om’s verlustfreier (A)udio (K)ompressor (нем.)
* [[TTA]] — True Audio Lossless
* [[WavPack]] — WavPack lossless
* [[Windows Media Audio 9 Lossless|WMA Lossless]] — Windows Media Lossless

=== Сжатие графики ===
* [[Adaptive Binary Optimization|ABO]] — Adaptive Binary Optimization
* [[AVIF]] — AV1 Image File Format (сжатие с/без потерь)
* [[BTPC]]
* [[CALIC]]
* [[CREW]]
* [[CTW]]
* [[DPCM]]
* [[GIF]] — (без потерь только для изображений, содержащих не более 256 цветов)
* [[JBIG2]] — (с потерями или без ч/б изображений)
* Lossless [[JPEG]] — (расширение стандарта сжатия JPEG, обеспечивающее сжатие без потерь)
* [[JPEG-LS]] — (стандарт сжатия без потерь/почти без потерь)
* [[JPEG 2000]] — (в режиме сжатия без потерь)
* [[LOCO-I]]
* [[Алгоритм сжатия MRP|MRP]]
* [[Progressive Graphics File|PGF]] — Progressive Graphics File (сжатие с/без потерь)
* [[PNG]] — Portable Network Graphics
* [[Алгоритм сжатия PWC|PWC]]
* [[TIFF]] — (исключая режимы сжатия с потерями<ref name="TIFFspec">{{Cite web |url=http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf |title=Спецификация TIFF v6 |lang=en|access-date=2010-12-18 |archive-date=2012-07-03 |archive-url=https://web.archive.org/web/20120703095221/http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf |deadlink=yes }}</ref>)
* [[TMW]]
* [[Truevision TGA]]
* [[HD Photo]] — (включая метод сжатия без потерь)
* [[Free Lossless Image Format|FLIF]] — Free Lossless Image Format
* [[JPEG XL|JXL]]<ref>[[:JPEG XL|JPEG XL]]</ref> - JPEG XL (сжатие с/без потерь) кодек с самым высоким сжатием без потерь.

=== Сжатие видео ===
* [[Animation codec]]
* [[CamStudio Video Codec]]
* [[CorePNG]]
* [[FFV1]]
* [[Huffyuv]] — ограничен YUY2 и RGB, не совместим с ffvhuff, оригинальный не обновлялся с 2002 года
* [[FFvhuff]] — улучшенный по сжатию huffyuv, поддерживает ещё YV12, обратно совместим с исходным кодеком
* [[Lagarith]]
* [[LCL (video codec)|LCL]]
* [[MSU Lossless Video Codec]]
* [[Qbit Lossless Codec]]
* [[SheerVideo]]
* [[TSCC (video codec)|TSCC]] — TechSmith Screen Capture Codec
* [[Сжатие с использованием вейвлет]]
* [[Motion JPEG 2000]]

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

== Примеры алгоритмов ==
* Семейство алгоритмов [[LZ|Лемпеля-Зива]]
* [[Кодирование длин серий|RLE]] (Run-length encoding — Кодирование длин серий)

== Примеры форматов и их реализаций ==
* универсальные — [[Zip]], [[7-Zip]], [[RAR]], [[GZip]], [[PAQ]] и др.
* звук — [[FLAC]] (Free Lossless Audio Codec), [[Monkey's Audio]] (APE), [[TTA]] (True Audio), [[TTE]], [[Lossless Audio|LA]] (LosslessAudio), [[RealAudio Lossless]], [[WavPack]] и др.
* изображения — [[PNG]], [[AVIF]] и др.
* видео — [[Huffyuv]].

== См. также ==
* [[Сжатие данных с потерями]] (Lossy)
* [[Сжатие звука без потерь]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://mydebianblog.blogspot.com/2009/04/lossless-linux.html Lossless кодирование видео в Linux]
* [http://www.lossless.ru/faq/lossless-codec-comparison/ Краткое сравнение распространенных lossless аудиокодеков]

{{нет источников|дата=2014-08-26}}
{{Методы сжатия}}

[[Категория:Сжатие данных]]
[[Категория:Алгоритмы сжатия без потерь|*]]