Сжатие без потерь — Википедия

У этого термина существуют и другие значения, см. Сжатие.

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

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

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

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

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

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

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

Так что несжимаемые фрагменты не приведут к бесконтрольному «раздуванию» архива. «Реальных» же файлов длины N намного меньше, чем 256N{\displaystyle 256^{N}} (говорят, что данные имеют низкую информационную энтропию) — например, маловероятно, чтобы буквосочетание «щы» встретилось в осмысленном тексте, а в оцифрованном звуке уровень не может за один семпл прыгнуть от 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

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

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

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

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

Список примеров в этом разделе не основывается на авторитетных источниках, посвящённых непосредственно предмету статьи или её раздела.Добавьте ссылки на источники, предметом рассмотрения которых является тема настоящей статьи (или раздела) в целом, а не отдельные элементы списка. В противном случае раздел может быть удалён.

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

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

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

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

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

• 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 — (исключая режимы сжатия с потерями^[1])
• TMW
• Truevision TGA
• HD Photo — (включая метод сжатия без потерь)
• FLIF — Free Lossless Image Format

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

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

• 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.

Основные сведения об архиваторах

Среди наиболее известных архиваторов можно назвать такие, как ZIP, ARJ, RAR, GZIP, LHA, HA, ACE. Стало традицией, что архив, созданный тем или иным архиватором, имеет расширение, соответствующее названию архиватора. Например, расширение файла archive.rar говорит о том, что он был создан с помощью архиватора RAR. Архиваторы различаются возможностями и качеством сжатия. Важно заметить, что качество сжатия зависит не только от архиватора, но и от типа сжимаемых данных. Некоторые архиваторы лучше работают с одними типами данных, но плохо показывают себя с другими. Как уже говорилось, создать абсолютно универсальный архиватор невозможно.

Когда говорят о возможностях архиваторов, часто обращают внимание на такие функции, как создание многотомных архивов и самораспаковывающихся архивов. Многотомные архивы – это архивы, которые разбиты на несколько отдельных файлов, находящихся на разных носителях. Многотомные архивы применяют в тех случаях, когда необходимо перенести большой объем информации на дискетах. В этом случае на каждую дискету помещается отдельный том архива. При извлечении данных из многотомного архива, архиватор будет последовательно обрабатывать тома и запрашивать смену дискеты.

Самораспаковывающиеся архивы используются в тех случаях, когда необходимо перенести информацию на другой компьютер, но неизвестно, установлен ли там соответствующий архиватор. Самораспаковывающийся архив представляет собой исполняемый (.EXE) файл, который включает в себя как заархивированные данные, так и программу для их распаковки, поэтому для того, чтобы извлечь данные, дополнительных программ не требуется.

3. Сжатие различных типов данных

Если рассматривать различные типы данных, то, наверное, лучше всего сжимаются простые растровые изображения. Коэффициент сжатия сильно колеблется и во многом зависит от используемого алгоритма и сложности изображения. Например, черно-белое изображение чертежного качества может быть сжато даже в сотню раз, цветные рисунки – в пять-десять раз, а цветные изображения высокого фотографического качества сжимаются менее чем в два раза. Хорошо сжимаются текстовые файлы. Если файл содержит текст, написанный на естественном языке, например, повесть или рассказ, то коэффициент сжатия будет равен двум-трем, а если в файле записан текст программы на языке программирования, то коэффициент сжатия может достигать пяти и выше. Коэффициент сжатия исполняемых файлов также сильно колеблется, однако, в среднем он равен примерно трем.

Использование универсальных методов сжатия применительно ко звуку редко дает хорошие результаты – звуковой файл сокращается всего на 20-40%. То же самое касается и высококачественных изображений, имеющих много деталей. Поэтому, для этих типов изображений используются специальные методы сжатия, особо хорошие результаты дают так называемые алгоритмы сжатия с потерями. Одна из идей этих алгоритмов состоит в том, что человеческий глаз и ухо не очень восприимчивы к некоторым мелким деталям изображения или звука, поэтому лишнюю информацию можно просто отбросить. Разумеется, кроме отбрасывания лишней информации, используются и другие алгоритмы, в результате чего достигается несравнимый коэффициент сжатия при минимальных потерях качества (с точки зрения восприятия человека). Такой подход используется в файлах формата JPEG, предназначенного для хранения статичных изображений и MPEG, предназначенного для хранения видео- и аудиоинформации. Сегодня особенно популярны такие форматы, как MPEG-3 (или MP3), предназначенный для хранения аудиоинформации, и позволяющий достигнуть десятикратного сжатия почти без потери качества, и MPEG-4, используемый для хранения видеофильмов.

Важно заметить, что те файлы, которые уже были сжаты тем или иным методом, почти не сжимаются дальше (чаще наоборот – увеличиваются в объеме), поэтому попытки сделать двойное архивирование редко дают положительный результат.

Подведем итог. Хорошо архивируются файлы, содержащие изображение с небольшим количеством деталей в несжатом виде (.BMP, .PSD и др.), текстовые файлы (.TXT, .DOC, .PAS и др.), большинство исполняемых файлов (.EXE).

Средне архивируются файлы, содержащие в несжатом виде звук (.WAV, .AU и др.), изображения фотореалистичного качества (.BMP, .PSD (были выше) и др.).

Плохо архивируются, либо вообще увеличиваются в размере файлы, данные в которых уже сжаты, в том числе архивы (.RAR, .ZIP, .ARJ и др.), графические файлы тех форматов, которые имеют собственное сжатие (.GIF, .JPG, .PNG и др.), аудиофайлы (.MP3), видеофайлы (.MPG, .AVI и др.), самораспаковывающиеся архивы (.EXE).

Сжатие информации и несжимаемые файлы

Сжатие информации и несжимаемые файлы

Первые персональные компьютеры обладали небольшой дисковой памятью. Чтобы перенести файлы и программы с одного компьютера на другой, их записывали на гибкие дискеты малой емкости. Памяти катастрофически не хватало. Дефицит памяти естественно побудил компьютерщиков искать способы экономной записи файлов. Одним из таких способов стала компрессия или сжатие информации. Оказалось, что во многих случаях файл можно после преобразования специальной программой сделать гораздо меньшим по размеру. Программы сжатия стали называть архиваторами. Сегодня мы на примере одной любопытной истории подробно расскажем о такой полезной для каждого пользователя функции, как сжатие файлов. Закономерно возникает вопрос: а зачем сейчас нужно сжимать файлы, если все основные технические характеристики персональных компьютеров каждые полтора-два года удваиваются? Оперативная память современной персоналки от 128 до 512 мегабайт, дисковая память вообще исчисляется десятками гигабайт. Казалось бы, можно особенно не заботиться о размерах файлов. Но интерес к сжатию файлов по-прежнему высок. Можно выделить две основные причины такого интереса. Первая, на персональных компьютерах стали воспроизводить и обрабатывать звук и изображение. Звуковые, графические и особенно видео файлы по объему памяти требуют на порядки больше памяти, чем текстовые. Одна фотография 15х20 см с хорошим разрешением 600 точек на дюйм или всего одна десятиминутная музыкальная композиция по объему превышают собрание сочинений Чехова. Вторая причина интереса к сжатию, пересылка файлов по электронной почте и скачивание с Интернет-узлов звуковой и графической информации. Пропускная способность обычных интернетовских линий не позволяет быстро пересылать файлы, превышающие несколько мегабайт, и поэтому многие серверы просто не пропускают большие файлы или искусственно ограничивают у пользователя скорость передачи информации. Поэтому сжатие файлов по-прежнему актуально. Архиваторы уменьшают некоторые файлы в 5-10 раз. За счет чего удается так сильно сократить размер файла? Некоторые файлы построены неоптимально с точки зрения их объема. Например, распространенные архиваторы сжимают большие файлы Microsoft Word в пять-шесть раз, а маленькие почти в десять. Чтобы прочесть такой сжатый текстовый файл, его нужно разжать той же самой программой. Многим пользователям поначалу приходила в голову блестящая мысль — попробовать сжать ещё раз уже сжатые файлы. Первая же попытка разочаровывает — сжатые файлы дальше не сжимаются, причём у всех архиваторов. Почему так происходит? Дело в том, что файлы представлены в памяти компьютера как длинные числа. А число любой заданной длины, в общем случае, нельзя точно передать числом меньшей длины, даже если оно короче всего на одну цифру. Из-за этого единственным способом сжатия данных является поиск в них некоей избыточной информации или закономерностей. Избыточную информацию можно удалить, а закономерности использовать для кодирования похожих фрагментов меньшим количеством байт. Значительное сжатие аудио-файлов стало возможно, потому что часть записанного звука ухо среднего человека не различает, или его не раздражает потеря некоторой звуковой информации. Когда программа обработала файлы соответствующим образом, нашла закономерности, удалила малозначимую информацию, то вторично она уже эту операцию провести не сможет. Поэтому при повторных сжатиях файл не уменьшается. Может показаться странным, но избыточной информации нет и в случайных данных, например в записях шумов радиоприемника на частоте, где нет передающих станций или в результатах работы программы — генератора случайных чисел. Дело в том, что в наборе действительно случайных чисел архиватор не может найти закономерностей. Получается, что и в сжатой энциклопедии, и в результатах тиражей Спортлото машина не может найти избыточную информацию, хотя энциклопедия — это концентрат знаний, а тиражи Спортлото — длинный набор случайных цифр. Надо подчеркнуть, что программы-архиваторы не проводят анализа содержания. Одна и та же по смыслу информация может занимать совершенно разные объемы памяти. Страница текста отпечатанного на компьютере в текстовом редакторе — это всего два килобайта. Если та же страница представлена в виде черно-белой картинки с удовлетворительным пространственным разрешением, то требуется — 2 мегабайта, то есть в тысячу раз больший объем. В цвете эта страница достигнет 20 мегабайт. Если текст прочтет диктор по радио, то в зависимости от качества записи две минуты звучания займут от одного до 20 мегабайт. Наконец, вы захотели увидеть диктора, читающего эту страницу: размер оцифрованного файла увеличится еще на порядок. Итак, основной принцип сжатия — это поиск закономерностей. В случайных данных закономерностей нет, и поэтому теоретически их сжать абсолютно невозможно. Несжимаемость, с точки зрения теории информации, — это фундаментальное свойство ряда случайных чисел. Однако весной прошлого года произошла история, где это утверждение подверглось серьезному испытанию. История эта тем интереснее, что её главный герой — не учёный, а находчивый дилетант, хорошо понимающий, что важны не только фундаментальные принципы, но и способы их программной реализации. Но расскажем об всём по порядку. Интернет — очень удобная среда для общения профессионалов. Удаленные друг от друга специалисты из разных стран могут обсуждать проблемы своей области. В Сети хорошо известна сетевая иерархия Usenet. Она объединяет тысячи дискуссионных групп на самые разные темы. Есть там и группа под названием COMP.COMPRESS. В ней специалисты обсуждают компрессию, т.е. сжатие информации. Участие в обсуждениях группы требует значительной подготовки. Поэтому случайные посетители в COMP.COMPRESS надолго не задерживаются. Правда, время от времени кем-то из новичков высказывается мнение, действующее на специалистов по сжатию примерно так же, как на физиков проекты вечного двигателя, а на историков — сочинения Фоменко. Условно проблему можно назвать «чудо-компрессор». Как правило, речь идет о том, что сотрудники малоизвестной компании разработали революционный алгоритм или даже программу для многократного сжатия информации. Обычно утверждается, что сжатие идёт без потерь, и (самое главное) — во много раз сжимается любая информация. При внимательном рассмотрении оказывается, что это — блеф, но, тем не менее, эта idea fix регулярно возникает на страницах компьютерной прессы. Характерный пример. В апреле 92-го года компания WEB Technologies объявила о создании программы, сжимающей в 16 раз любые файлы размером больше 64-х килобайта. Были другие фирмы, которые заявляли о столь же удивительных параметрах своих программ. Некоторым из них удалось даже запатентовать собственные алгоритмы, однако, в результате, подобные проекты оказались мыльными пузырями. Это, конечно, не значит, что компрессия данных, как направление, больше не развивается. Наоборот, едва ли не каждые полгода появляются новые алгоритмы или совершенствуются старые, сжимающие данные всё сильнее и сильнее. Особенно заметен прогресс в компрессии звука и видео. Если десять лет назад для записи обычного фильма требовались два огромных лазерных диска размером с большую грампластинку, то сейчас для достижения близкого качества достаточно одного CD-ROM-а, и судя по всему, это не предел. Такие успехи создают у неспециалистов иллюзию, что сжимать можно всё и очень сильно, надо только придумать алгоритм. Но не надо забывать, что популярные алгоритмы сжатия звука и графики сжимают данные с потерями. Это означает, что они не столько сжимают информацию, сколько удаляют из неё фрагменты, удаление которых не режет слух и не бросается в глаза. Но даже непрофессионал, если у него есть возможность сравнить, услышит разницу между действительно качественным звуком и сжатыми файлами. Если говорить о сжатии без потерь, то в нём уже давно не было пионерских работ. Последний принципиально новый алгоритм безпотерьного сжатия был изобретён в 80-х годах и пока мало применяется из-за большой сложности. Кроме того, как уже говорилось, есть данные, которые вообще нельзя сжать без потерь. Это, во-первых — случайная информация, а во вторых — сжатая ранее. Если допустить, что компрессор сжимает без потерь любые файлы, то можно взять файл и уменьшить его один раз, затем опять пропустить через компрессор и опять уменьшить. Если операцию повторять снова и снова, то, в конце концов, файл сожмётся до одного бита, сохранив всю полезную информацию, что, конечно — абсурд. Несмотря на это, благодаря случайным посетителям, слухи о чудо-компрессорах регулярно проникают в группу COMP.COMPRESS и раздражают её старожилов. В один прекрасный день, чтобы покончить с вопросом раз и навсегда, один из профессионалов, Майк Голдмэн (Mike Goldman), предложил всем обладателям чудо компрессора выплатить денежное вознаграждение. Он написал: Майк Голдмен Я готов заплатить пять тысяч долларов любому, кто выполнит следующие условия. Вы сообщаете мне, какого размера файл можете сжать, и в доказательство своей серьезности присылаете мне 100 долларов. Я генерирую файл и высылаю вам. Вы изучаете его сколько хотите, затем сжимаете и присылаете мне вместе с программой для разжатия. Я разжимаю файл и проверяю — не была ли потеряна информация. Если не была, и сжатый файл вместе с вашим декомпрессором хоть сколько-нибудь меньше исходного файла, я заплачу вам 5 тысяч, плюс ваши 100 долларов. Александр Костинский Другими словами, если у вас есть программа, на самом деле сжимающая любую информацию, то вы легко можете заработать пять тысяч долларов. Предложение Голдмена, было выложено в Интернете http://www.faqs.org/faqs/compression-faq/part1/section-8.html вместе с подробными объяснениями, почему нельзя сжать случайную информацию и почему архиватор, сжимающий любые данные — невозможен. Пари оставалось без ответа несколько лет, но 26-го марта прошлого года, по электронной почте Голдмену пришло письмо от человека по имени Патрик Крейг (Patrick Craig) в нем писалось:

Патрик Крейг Я прочитал ваше предложение. Звучит очень заманчиво, оно всё еще в силе? Если да, то хотелось бы узнать детали о декомпрессоре — он должен запускаться на любой машине или достаточно какой-то одной платформы, например Linux? Майк Голдмен Да, предложение в силе. Linux-а достаточно. Вы хотите рискнуть? Патрик Крейг Я всё еще думаю над этим. Вам нужен только сжатый файл? Майк Голдмен Вы говорите, какого размера файл нужен, и присылаете мне 100 долларов. Я генерирую файл и высылаю вам. Вы присылаете мне его сжатым вместе с декомпрессором. Если сжатый файл вместе с декомпрессором меньше оригинала — я высылаю вам 5 тысяч. Если у вас не получилось — можете опять прислать мне 100 долларов и попробовать ещё раз. Патрик Крейг А могу я прислать сжатую информацию не одним файлом, а несколькими частями, плюс декомпрессор, который восстановит оригинал? Майк Голдмен Да, вполне. Патрик Крейг Я принимаю вызов. Как вам можно отправить деньги? Майк Голдмен Пришлите чек или банковский перевод. Если вы закажете очень большой файл, то должны обеспечить соответствующий носитель. Вы уже решили, какой размер вам нужен? Патрик Крейг Я до сих пор думаю над оптимальным размером, но полагаю, он будет меньше гигабайта. У вас есть где-нибудь доступ к анонимному ftp-серверу? Александр Костинский Далее идёт обсуждение мелких деталей, из которых выясняется, что обладатель чудо компрессора — англичанин. Он сейчас живёт в Японии, откуда не может послать чек в США Майку, поэтому вышлет деньги наличными по почте. Видя, что вызов принят, Майк пробует выяснить — каким же способом Патрик собирается выполнить теоретически невозможные условия, но тот не сдаётся, отвечает: «подожди, увидишь» и высылает деньги. Заметим, что переговоры уместились в одиннадцать электронных писем и прошли всего за несколько часов. Наличные идут по обычной почте из Японии в США четверо суток. Майк получает деньги и Патрик сообщает ему размер файла, который он готов уменьшить. Он требует 3 мегабайта. Но что же предлагал сжать всем желающим Майк Голдмен? Человек, рискующий пятью тысячами долларов, должен позаботиться о несжимаемости своих данных. Совершенно несжимаемая информация, как уже говорилось — набор случайных чисел. Но, оказывается, гарантированно получить такой набор — не такая простая задача. Программа всегда строго следует алгоритму и в результате ее работы могут быть сгенерированы лишь псевдослучайные числа. При этом нет уверенности, что данный ряд чисел не может быть повторен или сгенерирован подобной программой. Настоящий хаос можно найти только в событиях реальной жизни. Надежными генераторами случайных чисел многие специалисты считают источники радиоактивного излучения. Радиоактивные вещества распадаются в строгом соответствии с теорией вероятности, и повлиять на их активность в обычных условиях практически невозможно. Криптографы для создания надёжных ключей шифрования используют именно радиоактивные образцы. Но есть и более простые решения. Например, Web-сайт Random.org даёт посетителям доступ к генератору случайных чисел, построенному на обычном радиоприёмнике. Этот приёмник подключён к серверу через обычную аудиокарту и настроен на частоту, на которой не ведутся радиопередачи. Источником случайных чисел служит атмосферный радиошум. Это вполне качественный генератор. Специальной программой его результаты можно собирать в файл, и именно из этого источника Майк Голдмен получил 3 мегабайта несжимаемых данных для Патрика Крейга. Что же сделал с ними Патрик Крэйг? Свою версию событий он поместил в Интернете: Патрик Крейг Тот, кто предлагает вам такое пари, наверняка знаком с теорией информации и, скорее всего, предложит для сжатия данные какого-нибудь генератора случайных чисел. Теоретически, такой генератор может выдать всё что угодно, даже осмысленный текст, который можно сжать обычным архиватором, но надеяться на это не стоило, поскольку Майк Голдмен несомненно проверял файл, перед тем как высылать его мне. По условиям пари было достаточно сэкономить всего один байт, при этом ничего не говорилось о сохранении имени исходного файла. Можно было использовать имя файла для сохранения в нём нескольких байт информации, соответственно уменьшив на них общий размер файла. Однако, большинство сочло бы это нечестным трюком. Другой вариант — вводить недостающие байты из командной строки при запуске декомпрессора. Естественно, в этом случае я должен был сообщить Майку, что он должен набрать эти недостающие байты вручную. Фактически, это означало бы сохранение информации в человеческой памяти. Кстати, таким способом можно любой файл уменьшить до нуля, а затем восстановить, набирая байт за байтом на клавиатуре. Однако, это трудно назвать компрессией. К счастью для меня, Майк разрешил использовать несколько сжатых файлов, и этот нюанс позволил легко выполнить условия пари безо всяких, по моему мнению, нечестных приёмов. Александр Костинский Вот что придумал Патрик. Пусть, у нас есть длинный файл случайных данных. Находим в этом файле, допустим букву «А». Теперь на букве «А» мы разрежем файл на две части, а саму букву выбросим. У нас получатся два файла, которые в сумме будут на один байт меньше исходного. Что бы восстановить оригинал, нужно просто склеить две его части, вставив между ними букву «А». Естественно, исходный файл можно разрезать не на две части, а на три и больше, поскольку выбранная нами буква «А» встречается в нём много раз. Если мы имеем дело со случайными данными, то любой символ будет встречаться примерно каждые 255 символов. Таким образом, разрезая один длинный файл в тех местах, где у него находится буква «А» и выбрасывая её, мы превращаем один большой файл в цепочку маленьких, сберегая при этом четыре байта на каждом килобайте. Остаётся только написать простейшую программу, которая могла бы склеивать из множества нарезанных файлов один большой, первоначальный. У Патрика эта программа, которую можно назвать декомпрессором, оказалась размером всего в 156 байт. Исходный файл в 3 мегабайта, можно было разделить приблизительно на 3 тысячи фрагментов, но Патрик решил остановиться после второй сотни, поскольку алгоритм был ясен, а результат очевиден. В среду 4 апреля, профессионал Майк Голдмен получил от находчивого Патрика Крейга письмо, где говорилось, что исходный файл был разделён на 218 частей, суммарная их длина стала на 217 байт короче исходного файла. Программа-декомпрессор имеет размер 156 байт, кое-что ушло на сохранение имени файла. В результате, общий размер уменьшился на 44 байта. Условия, поставленные Майком Голдманом выполнены, следовательно, пора платить обещанные пять тысяч долларов. Обо всем этом возмутитель спокойствия подробно рассказал (http://www.geocities.com/patchnpuki/other/compression.htm) в дискуссионной группе COMP.COMPRESS к общему удовольствию всех подписчиков, которые несколько недель обсуждали неожиданный результат. (http://groups.google.com/groups?hl=en&ic=1&th=f2d47a8426e2de35 ). Между тем, Майк Голдмен не заплатил обещанные пять тысяч и объяснил свои действия так: Майк Голдмен Разрезая файл на две части и отбрасывая один байт в месте разреза, Патрик действительно уменьшал содержимое файлов на один байт. Но, кроме основного содержания, у каждого файла есть еще имя, дата создания, координаты расположения на физическом диске и так далее. В результате два файла, длина которых на один байт меньше третьего, на реальном диске занимают больше места, хотя их видимый размер действительно кажется нам меньше. Александр Костинский На это Патрик Крейг заметил: Патрик Крейг Если операционная система для одного длинного файла требует меньше места, чем для двух коротких, то это её проблемы, а не мои. Александр Костинский Формально он прав и, если понимать условия пари буквально, Голдмен должен признать проигрыш, а не уточнять правила по ходу дела. Кое-кто в дискуссионной группе призывал его «быть мужчиной и заплатить деньги». Однако, Майк ограничился тем, что вернул Патрику 100 долларов залога, сказав, что проделанный трюк никак нельзя назвать компрессий информации, и он сожалеет, что условия пари были сформулированы недостаточно ясно. К чести Патрика Крейга, он не настаивал на награде и признался позже, что вовсе не рассчитывал заработать пять тысяч долларов. Его главной целью было «обхитрить хитреца» — показать, что у самоуверенного Голдмена можно выиграть, причём на его условиях, если рассматривать проблему, как головоломку, используя нечеткую постановку задачи. Эта история оказалось полезной для всех её участников. Патрик Крейг показал незаурядную находчивость. Майк Голдмен понял, как надо изменить условия пари, чт бы в следующий раз не проиграть его. А наблюдавшие за этой историей еще раз убедились, что чудо компрессора быть не может, так как основы теории информации и теории вероятностей стоят на очень и очень прочном фундаменте. Все ссылки в тексте программ ведут на страницы лиц и организаций, не связанных с радио «Свобода»; редакция не несет ответственности за содержание этих страниц.

Сжатие данных с потерями — Википедия

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

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 23 марта 2016; проверки требуют 13 правок. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 23 марта 2016; проверки требуют 13 правок. У этого термина существуют и другие значения, см. Сжатие.

Сжатие данных с потерями (англ. lossy compression) — метод сжатия (компрессии) данных, при использовании которого распакованные данные отличаются от исходных, но степень отличия не существенна с точки зрения их дальнейшего использования. Этот тип компрессии часто применяется для сжатия аудио- и видеоданных, статических изображений, в Интернете (особенно в потоковой передаче данных) и цифровой телефонии. Альтернативой является сжатие без потерь.

Существуют две основных схемы сжатия с потерями:

• В трансформирующих кодеках фреймы изображений или звука обычно трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными методами.

• В предсказывающих кодеках предыдущие и/или последующие отсчеты данных используются для того, чтобы предсказать текущий отсчет изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется.

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

Сжатие с потерями против сжатия без потерь[править | править код]

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

Методы сжатия с потерями часто используются для сжатия аналоговых данных — чаще всего звука или изображений.

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

Много методов фокусируются на физических особенностях органов чувств человека. Психоакустическая модель определяет то, как сильно звук может быть сжат без ухудшения воспринимаемого человеком качества звука. Недостатки, причинённые сжатием с потерями, которые заметны для человеческого уха или глаза, известны как артефакты сжатия.

Фотографии, записанные в формате JPEG, могут быть приняты судом в качестве доказательств несмотря на то, что изображение сжато с потерями.

Недостатки[править | править код]

При использовании сжатия с потерями необходимо учитывать, что повторное сжатие обычно приводит к деградации качества. Однако, если повторное сжатие выполняется без каких-либо изменений сжимаемых данных, качество не меняется. Так например, сжатие изображения методом JPEG, восстановление его и повторное сжатие с теми же самыми параметрами не приведёт к снижению качества. То же справедливо и для метода JPEG-LS в режиме сжатия с ограниченными потерями. Но в общем случае, когда декодированные данные подвергаются редактированию, несжатый оригинал целесообразно сохранять (или сжимать без потери данных).

Методы сжатия данных с потерями (примеры)[править | править код]

Компрессия изображений[править | править код]

Компрессия видео[править | править код]

Компрессия звука[править | править код]

Музыка[править | править код]

Речь[править | править код]

• CELP
• G.711
• G.726
• HILN (англ.)
• Speex (отличается отсутствием патентных ограничений)
• iLBC (Кодек со свободными условиями лицензирования)

Сжатие данных без потерь

Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 11 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, базовый уровень) | Сжатие данных без потерь

Содержание урока

Основные понятия

Алгоритм RLE

Префиксные коды

Алгоритм Хаффмана

Сжатие с потерями

Выводы

Вопросы и задания

Задачи

Вопросы и задания

1. За счёт чего удаётся сжать данные без потерь? Когда это сделать принципиально невозможно?
2. Какие типы файлов сжимаются хорошо, а какие — плохо? Почему?
3. Текстовый файл, записанный в однобайтной кодировке, содержит только 33 заглавные русские буквы, цифры и пробел. Ответьте на следующие вопросы:

• какое минимальное число битов нужно выделить на символ при передаче, если каждый символ кодируется одинаковым числом битов?
• сколько при этом будет занимать заголовок пакета данных?
• при какой минимальной длине текста коэффициент сжатия будет больше 1?

4. На чём основан алгоритм сжатия RLE? Когда он работает хорошо? Когда нет смысла его использовать?
5. Что такое префиксный код?
6. В каких случаях допустимо сжатие с потерями?
7. Опишите простейшие методы сжатия рисунков с потерями. Приведите примеры.
8. На чём основан алгоритм JPEG? Почему это алгоритм сжатия с потерями?
9. Что такое артефакты?
10. Для каких типов изображений эффективно сжатие JPEG? Когда его не стоит применять?
11. На чём основано сжатие звука в алгоритме MP3?
12. Что такое битрейт? Как он связан с качеством звука?
13. Какое качество звука принимается за эталон качества на непрофессиональном уровне?
14. Какие методы используются для сжатия видео?

Подготовьте сообщение

а) «Программы для сжатия данных»
б) «Алгоритмы сжатия изображений»
в) «Аудиокодеки»
г) «Видеокодеки»

Следующая страница Задачи

Cкачать материалы урока

Сжатие данных без потерь

Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 11 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю) | Сжатие данных без потерь

Содержание урока

Основные понятия

Алгоритм RLE

Префиксные коды

Алгоритм Хаффмана

Сжатие с потерями

Выводы

Вопросы и задания

Задачи

Вопросы и задания

1. За счёт чего удаётся сжать данные без потерь? Когда это сделать принципиально невозможно?
2. Какие типы файлов сжимаются хорошо, а какие — плохо? Почему?
3. Текстовый файл, записанный в однобайтной кодировке, содержит только 33 заглавные русские буквы, цифры и пробел. Ответьте на следующие вопросы:

• какое минимальное число битов нужно выделить на символ при передаче, если каждый символ кодируется одинаковым числом битов?
• сколько при этом будет занимать заголовок пакета данных?
• при какой минимальной длине текста коэффициент сжатия будет больше 1?

4. На чём основан алгоритм сжатия RLE? Когда он работает хорошо? Когда нет смысла его использовать?
5. Что такое префиксный код?
6. В каких случаях допустимо сжатие с потерями?
7. Опишите простейшие методы сжатия рисунков с потерями. Приведите примеры.
8. На чём основан алгоритм JPEG? Почему это алгоритм сжатия с потерями?
9. Что такое артефакты?
10. Для каких типов изображений эффективно сжатие JPEG? Когда его не стоит применять?
11. На чём основано сжатие звука в алгоритме MP3?
12. Что такое битрейт? Как он связан с качеством звука?
13. Какое качество звука принимается за эталон качества на непрофессиональном уровне?
14. Какие методы используются для сжатия видео?

Подготовьте сообщение

а) «Программы для сжатия данных»
б) «Алгоритмы сжатия изображений»
в) «Аудиокодеки»
г) «Видеокодеки»

Следующая страница Задачи

Cкачать материалы урока

Какой архиватор сильнее сжимает файлы? WinRar, WinUha, WinZip или 7Z?

В сети сегодня популярны десятки архиваторов, причем, в описание у каждой программы можно встретить что ее алгоритм самый-самый… Решил взять несколько популярных в сети архиваторов, а именно: WinRar, WinUha, WinZip, KGB archiver, 7Z и проверить их в «боевых» условиях.

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

Таблица сравнения сжатия

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

Как видно из небольшой таблички, что самая высокая степень сжатия достигается у программы KGB Archiver 2 — в 23 раза уменьшился исходный размер файла! Т.е. если у вас на жестком диске несколько гигабайт различной документации, которой вы не пользуетесь и хотите удалить (но не покидает чувство, а вдруг пригодится) — не проще ли сжать такой программой и записать на диск…

Но обо всех «подводных камнях» по порядку…

KGB Archiver 2

В общем то не плохой архиватор, по заявлениям разработчиков их алгоритм сжатия один из самых «сильных». Сложно не согласиться…

Только вот скорость сжатия оставляет желать лучшего. Например, файл в примере (около 3 мб) программа сжимала около 3 мин! Нетрудно прикинуть, что один CD диск она будет сжимать пол дня, если не больше.

Но особое удивление вызывает не это. Распаковка файла длиться по времени столько же, сколько компрессия! Т.е. если вы потратили пол дня на то, чтобы сжать часть своих документов, то столько же времени вы потратите, чтобы достать их из архива.

Итог: программу можно использовать для небольших объемов информации, особенно, когда важен минимальный размер исходного файла (например, файл нужно разместить на дискете, или на небольшой по вместимости флешке). Но опять таки, угадать заранее размер сжатого файла нельзя, и возможно, время на сжатие вы потратите впустую…

WinRar

Знаменитая программа на постсоветском пространстве, установлена на большинстве компьютеров. Наверное, если бы она не показывала такие хорошие результаты, у нее бы и не было столько поклонников. Ниже скриншот на котором показаны настройки сжатия, ничего особенного, разве только степень сжатия была поставлена на максимум.

На удивление WinRar сжал файл за несколько секунд, причем размер файла уменьшился  в 17 раз. очень достойный результат, если еще учесть что время затраченное на обработку ничтожно мало. А время на распаковку файла — еще меньше!

Итог: отличная программа, показывающая одни из самых лучших результатов. В процессе настроек сжатия можно так же указать максимальный размер архива и программа его разобьет на несколько частей. Это очень удобно, чтобы перенести файл с одного компьютера на другой на флешке или CD/DVD диске, когда целиком файл на  не запишешь…

WinUha

Сравнительно молодой архиватор. Назвать его сверх-популярным нельзя, но интерес у многих пользователей к нему кто часто работает с архивами — есть. И не случайно, ведь по заявлениям разработчиков архиватора, его алгоритм сжатия сильнее чем у RAR и 7Z.

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

Кстати, при установке выбирайте английский язык, на русском — программа выдает «крякозабры».

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

7Z

Очень популярный бесплатный архиватор. Многие утверждают что степень сжатия в 7z реализована даже лучше чем в WinRar. Вполне возможно, но при сжатии с уровнем «Ультра» на большинстве файлов он проигрывает WinRar’у.

Итог: неплохая альтернатива WinRar’у. Вполне сопоставимая степень сжатия, хорошая поддержка русского языка, удобное встраивание в контекстное меню проводника.

WinZip

Легендарный, один из самых популярных некогда архиваторов. В сети, наверное, самые часто-встречающиеся архивы — это «ZIP». И не случайно — ведь несмотря на не самую высокую степень сжатия, скорость работы — просто поражает. Например, Windows открывает такие архивы как обычные папки!

К тому же не следует забывать, что этот архиватор и формат сжатия намного старше новомодных конкурентов. Да и далеко не у всех сейчас стоят мощные компьютеры, которые позволят быстро работать с новыми форматами. А формат Zip поддерживают все современные архиваторы!