imported>Rainbow Spike: /* Сжатие аудио */

2025-10-29T10:29:11Z

Сжатие аудио

Новая страница

{{Значения|Сжатие}}
[[Файл: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 Audio 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 |url-status=dead }}</ref>)
* [[TMW]]
* [[Truevision TGA]]
* [[HD Photo]] — (включая метод сжатия без потерь)
* [[Free Lossless Image Format|FLIF]] — Free Lossless Image Format
* [[JPEG XL|JXL]] - 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}}
{{Методы сжатия}}

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

Сжатие без потерь - История изменений

imported>Rainbow Spike: /* Сжатие аудио */