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

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

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

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы (например PNG) используют только сжатие без потерь, тогда как другие (TIFF, MNG или 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 и LZ78 (используется DEFLATE)
• LZW

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

• Алгоритм Хаффмана (также используется DEFLATE)
• Арифметическое кодирование

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

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

Многоцелевые

• Кодирование длин серий — простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений
• 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
• Free Lossless Audio Codec — FLAC
• 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
• WMA Lossless — Windows Media Lossless

Сжатие графики

• ABO — Adaptive Binary Optimization
• BTPC
• CALIC
• CREW
• CTW
• DPCM
• GIF — (без потерь только для изображений содержащих не более 256 цветов)
• JBIG2 — (с потерями или без Ч/Б изображений)
• Lossless JPEG — (расширение стандарта сжатия JPEG, обеспечивающее сжатие без потерь)
• JPEG-LS — (стандарт сжатия без потерь/почти без потерь)
• JPEG 2000 — (в режиме сжатия без потерь)
• LOCO-I
• MRP
• PGF — Progressive Graphics File (сжатие с/без потерь)
• PNG — Portable Network Graphics
• PWC
• TIFF — (исключая режимы сжатия с потерями)
• TMW
• Truevision TGA
• HD Photo — (включая метод сжатия без потерь)
• FLIF - Free Lossless Image Format

Сжатие видео

• Animation codec
• CamStudio Video Codec
• CorePNG
• FFV1
• Huffyuv
• Lagarith
• LCL
• MSU Lossless Video Codec
• Qbit Lossless Codec
• SheerVideo
• TSCC — TechSmith Screen Capture Codec
• [stbit.ru/index.php?option=com_content&view=article&id=5&Itemid=4 WMC] — Wavelet Media Codec
• Motion JPEG 2000

Сжатие текстов

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

Примеры алгоритмов

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

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

• универсальные — Zip, 7-Zip, RAR, GZip, PAQ и др.
• звук — FLAC (Free Lossless Audio Codec), Monkey's Audio (APE), TTA (True Audio), TTE, LA (LosslessAudio), RealAudio Lossless, WavPack и др.
• изображения — BMP, PNG
• видео — Huffyuv.

См. также

• Сжатие данных с потерями
• Сжатие звука без потерь

Ссылки

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

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Сжатие без потерь

Седой камердинер сидел, дремля и прислушиваясь к храпению князя в огромном кабинете. Из дальней стороны дома, из за затворенных дверей, слышались по двадцати раз повторяемые трудные пассажи Дюссековой сонаты.
В это время подъехала к крыльцу карета и бричка, и из кареты вышел князь Андрей, высадил свою маленькую жену и пропустил ее вперед. Седой Тихон, в парике, высунувшись из двери официантской, шопотом доложил, что князь почивают, и торопливо затворил дверь. Тихон знал, что ни приезд сына и никакие необыкновенные события не должны были нарушать порядка дня. Князь Андрей, видимо, знал это так же хорошо, как и Тихон; он посмотрел на часы, как будто для того, чтобы поверить, не изменились ли привычки отца за то время, в которое он не видал его, и, убедившись, что они не изменились, обратился к жене:
– Через двадцать минут он встанет. Пройдем к княжне Марье, – сказал он.
Маленькая княгиня потолстела за это время, но глаза и короткая губка с усиками и улыбкой поднимались так же весело и мило, когда она заговорила.
– Mais c'est un palais, – сказала она мужу, оглядываясь кругом, с тем выражением, с каким говорят похвалы хозяину бала. – Allons, vite, vite!… [Да это дворец! – Пойдем скорее, скорее!…] – Она, оглядываясь, улыбалась и Тихону, и мужу, и официанту, провожавшему их.
– C'est Marieie qui s'exerce? Allons doucement, il faut la surprendre. [Это Мари упражняется? Тише, застанем ее врасплох.]
Князь Андрей шел за ней с учтивым и грустным выражением.
– Ты постарел, Тихон, – сказал он, проходя, старику, целовавшему его руку.
Перед комнатою, в которой слышны были клавикорды, из боковой двери выскочила хорошенькая белокурая француженка.
M lle Bourienne казалась обезумевшею от восторга.
– Ah! quel bonheur pour la princesse, – заговорила она. – Enfin! Il faut que je la previenne. [Ах, какая радость для княжны! Наконец! Надо ее предупредить.]
– Non, non, de grace… Vous etes m lle Bourienne, je vous connais deja par l'amitie que vous рorte ma belle soeur, – говорила княгиня, целуясь с француженкой. – Elle ne nous attend рas? [Нет, нет, пожалуйста… Вы мамзель Бурьен; я уже знакома с вами по той дружбе, какую имеет к вам моя невестка. Она не ожидает нас?]
Они подошли к двери диванной, из которой слышался опять и опять повторяемый пассаж. Князь Андрей остановился и поморщился, как будто ожидая чего то неприятного.
Княгиня вошла. Пассаж оборвался на середине; послышался крик, тяжелые ступни княжны Марьи и звуки поцелуев. Когда князь Андрей вошел, княжна и княгиня, только раз на короткое время видевшиеся во время свадьбы князя Андрея, обхватившись руками, крепко прижимались губами к тем местам, на которые попали в первую минуту. M lle Bourienne стояла около них, прижав руки к сердцу и набожно улыбаясь, очевидно столько же готовая заплакать, сколько и засмеяться.
Князь Андрей пожал плечами и поморщился, как морщатся любители музыки, услышав фальшивую ноту. Обе женщины отпустили друг друга; потом опять, как будто боясь опоздать, схватили друг друга за руки, стали целовать и отрывать руки и потом опять стали целовать друг друга в лицо, и совершенно неожиданно для князя Андрея обе заплакали и опять стали целоваться. M lle Bourienne тоже заплакала. Князю Андрею было, очевидно, неловко; но для двух женщин казалось так естественно, что они плакали; казалось, они и не предполагали, чтобы могло иначе совершиться это свидание.
– Ah! chere!…Ah! Marieie!… – вдруг заговорили обе женщины и засмеялись. – J'ai reve сette nuit … – Vous ne nous attendez donc pas?… Ah! Marieie,vous avez maigri… – Et vous avez repris… [Ах, милая!… Ах, Мари!… – А я видела во сне. – Так вы нас не ожидали?… Ах, Мари, вы так похудели. – А вы так пополнели…]
– J'ai tout de suite reconnu madame la princesse, [Я тотчас узнала княгиню,] – вставила m lle Бурьен.
– Et moi qui ne me doutais pas!… – восклицала княжна Марья. – Ah! Andre, je ne vous voyais pas. [А я не подозревала!… Ах, Andre, я и не видела тебя.]
Князь Андрей поцеловался с сестрою рука в руку и сказал ей, что она такая же pleurienicheuse, [плакса,] как всегда была. Княжна Марья повернулась к брату, и сквозь слезы любовный, теплый и кроткий взгляд ее прекрасных в ту минуту, больших лучистых глаз остановился на лице князя Андрея.
Княгиня говорила без умолку. Короткая верхняя губка с усиками то и дело на мгновение слетала вниз, притрогивалась, где нужно было, к румяной нижней губке, и вновь открывалась блестевшая зубами и глазами улыбка. Княгиня рассказывала случай, который был с ними на Спасской горе, грозивший ей опасностию в ее положении, и сейчас же после этого сообщила, что она все платья свои оставила в Петербурге и здесь будет ходить Бог знает в чем, и что Андрей совсем переменился, и что Китти Одынцова вышла замуж за старика, и что есть жених для княжны Марьи pour tout de bon, [вполне серьезный,] но что об этом поговорим после. Княжна Марья все еще молча смотрела на брата, и в прекрасных глазах ее была и любовь и грусть. Видно было, что в ней установился теперь свой ход мысли, независимый от речей невестки. Она в середине ее рассказа о последнем празднике в Петербурге обратилась к брату:
– И ты решительно едешь на войну, Andre? – сказала oia, вздохнув.
Lise вздрогнула тоже.
– Даже завтра, – отвечал брат.
– II m'abandonne ici,et Du sait pourquoi, quand il aur pu avoir de l'avancement… [Он покидает меня здесь, и Бог знает зачем, тогда как он мог бы получить повышение…]
Княжна Марья не дослушала и, продолжая нить своих мыслей, обратилась к невестке, ласковыми глазами указывая на ее живот:
– Наверное? – сказала она.
Лицо княгини изменилось. Она вздохнула.
– Да, наверное, – сказала она. – Ах! Это очень страшно…
Губка Лизы опустилась. Она приблизила свое лицо к лицу золовки и опять неожиданно заплакала.
– Ей надо отдохнуть, – сказал князь Андрей, морщась. – Не правда ли, Лиза? Сведи ее к себе, а я пойду к батюшке. Что он, всё то же?
– То же, то же самое; не знаю, как на твои глаза, – отвечала радостно княжна.
– И те же часы, и по аллеям прогулки? Станок? – спрашивал князь Андрей с чуть заметною улыбкой, показывавшею, что несмотря на всю свою любовь и уважение к отцу, он понимал его слабости.
– Те же часы и станок, еще математика и мои уроки геометрии, – радостно отвечала княжна Марья, как будто ее уроки из геометрии были одним из самых радостных впечатлений ее жизни.
Когда прошли те двадцать минут, которые нужны были для срока вставанья старого князя, Тихон пришел звать молодого князя к отцу. Старик сделал исключение в своем образе жизни в честь приезда сына: он велел впустить его в свою половину во время одевания перед обедом. Князь ходил по старинному, в кафтане и пудре. И в то время как князь Андрей (не с тем брюзгливым выражением лица и манерами, которые он напускал на себя в гостиных, а с тем оживленным лицом, которое у него было, когда он разговаривал с Пьером) входил к отцу, старик сидел в уборной на широком, сафьяном обитом, кресле, в пудроманте, предоставляя свою голову рукам Тихона.