1 хорошо ли сжимаются разные форматы файлов

Обновлено: 07.07.2024

Здравствуйте! Не могли бы вы объяснить начинающему пользователю, как сжимаются файлы всякими архиваторами? Хотя бы в общих чертах. А то я с трудом себе представляю, как это вообще может быть.

Совершенно верно, Виталий, это действительно не так просто себе представить, тем более, если не знаешь алгоритма. Но читателям журнала «Компьютер» повезло ;), поскольку я в свое время много интересовался алгоритмами сжатия данных и, как программист, даже пробовал писать собственный архиватор.

Сжатие данных (англ. data compression) – алгоритмическое преобразование данных, производимое с целью уменьшения их объема. Применяется для более рационального использования устройств хранения и передачи данных. Процесс сжатия еще называют упаковкой данных или компрессией. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

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

Итак, давайте начнем с простого примера. Допустим, у нас есть текстовый файл, который содержит строку текста:

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

Таким образом, вместо 22 символов мы получили 16 символов. Конечно, такие тексты как наш исходный встречаются довольно редко, не говоря уже о бессмыслице, которая заключена в нем. Но ведь файлы, подвергающиеся сжатию, бывают не только текстовые, но и всякие картинки, музыка, видео, программы.

Данный пример довольно упрощен и не отражает эффективность, которую обычно демонстрируют при сжатии архиваторы. Так у нас получилось сжатие в 22/16 = 1,375 раза, хотя архиваторы, как правило, способны сжимать файлы в 2-10000 раз. Все зависит от повторяемости значений байт в файле.

Например, во времена незабвенной MS-DOS были архиваторы ARJ, PKZIP, HA, RAR, ARC, ACE и упаковщики программ LZEXE и PKLITE. Позднее для операционной системы Windows были созданы WinAce, WinZIP, WinRAR, 7Zip и известный мне упаковщик UPX.

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

Сжатие с потерями можно назвать адаптивным сжатием, и применяется для упаковки изображений, видео и звука, поскольку такие данные сжатию без потерь поддаются весьма незначительно (всего примерно до 2 раз).

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

Действительно, например, текстовые файлы могут сжиматься весьма плотно. Так, например, книга Аркадия и Бориса Стругацких «Трудно быть богом» размером 354 329 байт архиватором WinRAR сжимается до 140 146 байт, т.е. в 2,5 раза.

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

Для этого существуют упаковщики программ на подобие UPX и др. Например, мой текстовый редактор Superpad.exe размером 524 288 байт упаковщиком UPX сжимается до 179 200 байт (в 2,9 раза) и при этом может по-прежнему запускаться самостоятельно как программа.

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

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

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

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

Для сравнения, возьмем красивого лягушонка (рис. 1) разрешение 799x599 пикселей (точек) и сохраним в разные форматы хранения изображений. Получим файлы:

frog.bmp - размер 1 437 654 байта и тут, по сути, никакого сжатия и никаких потерь качества, поскольку картинка занимает положенные ей байты в формате Ширина x Высота x 3 байта на пиксель + заголовок формата файла BMP согласно качеству True colors (24 бит/пиксель). Т.е. каждая точка представлена тремя компонентами RGB (Red-красный, Green-зеленый и Blue-синий), каждая из которых занимает один байт.

frog24.jpg - 617 059 байт, сжатие в 2,33 раза и без потерь – основное свойство формата PNG-24. Данные BMP и PNG практически идентичны.

frog_256colors.jpg - 261 956 байт (рис. 2), сжатие в 5,48 раза с потерями, базовая палитра 256 цветов (8 бит/пиксель). Уловить разницу между этим файлом и оригиналом в BMP довольно сложно, как в той игре «Найди десять отличий».

frog_64colors.jpg - 187 473 байта (рис. 3), сжатие в 7,67 раза с потерями, базовая палитра уплотнена до 64 цветов (6 бит/пиксель). А вот тут цвета уже блеклые, но вполне сходное с оригиналом изображение. Особенно это заметно, если посмотреть на глаз лягушонка.

Особое место занимает в сжатии и хранении изображений формат JPEG. Поэтому ему хочу уделить особое внимание. Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет.

С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселями приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW.

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

JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, к сожалению, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.

frog100%.jpg – 216 168 байт, сжатие в 6,65 раза, потери якобы 0%, т.е. 100%-е качество картинки, но даже на это рассчитывать я бы не стал. Поверьте, отличия есть, правда, на глаз абсолютно неотличимые.

frog60%.jpg – 85 910 байт, сжатие в 16,7 раза, т.е. качество картинки 60%, но картинка снова кажется одинаковой, хотя, если присмотреться к участкам с однородным фоном или мелким деталям, то заметны артефакты в виде смазанности или квадратных одноцветных сегментов.

frog20%.jpg – 36 426 байт, сжатие в 39,5 раз, качество картинки 20% от исходного изображения, но по-прежнему картинка еще способна обмануть неискушенный глаз, но на однородном фоне отчетливо видны одноцветные угловатые сегменты, а мелкие детали окончательно потеряли свои четкие очертания.

Это один из самых первых и самых распространенных форматов хранения видео. Несколько раз модернизировался. Но в упрощенном виде, можно сказать, что алгоритм очень напоминает сжатие как в JPEG, но с учетом того, что первый кадр видео всегда является исходным и оригинальным, а последующие кадры хранят лишь разницу между предыдущим и следующим кадрами. Благодаря этому каждый последующий кадр является предсказуемым с точки зрения распаковки (рис. 4 и 5).

Рис. 5. Межкадровая разница без применения алгоритмов компенсации движения

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

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

Компенсация движения (англ. Motion Compensation) – один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует сходство соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8).

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

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

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

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

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

Звук и музыка могут без потерь, либо с потерями храниться в формате WAV. Например, формат WAV (Windows PCM) не предусматривает сжатие и хранит звуковой сигнал в оригинале, если можно так выразиться.

Формат WAV (ACM Waveform), по сути, является контейнером и может хранить звук, сжатый по алгоритму MPEG layer 3, либо хранить музыку в формате MP3, хотя много и других форматов OGG, FLAC и д.р.

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

Какие форматы сжатия файлов вы бы использовали? Скорее всего, именно Zip, RAR, 7z, ведь они самые популярные. Было проведено несколько тестов, которые помогут определиться, какой формат сможет дать максимальный уровень сжатия и какой самый удобный в использование.

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

Сжатие файлов эталонов популярными архиваторами

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

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

Первой стала Bastion (Бастион), установленная игра имела размер около 863 мегабайт: музыки, графических и исполняемых файлов, плюс ко всему этому разные типы документов и вот что было получено:

• Zip (Windows 8.1): 746 МБ (86.4% от оригинального размера);
• Zip (WinZip): 745 МБ (86.3% от оригинального размера);
• RAR (WinRAR): 746 МБ (86.4% от оригинального размера);
• 7z(7-Zip): 734 МБ (85 % от оригинального размера).

Следующей для проведения тестирования была выбрана игра Hotline Miami (Горячая линия Маями), которая имела размер 654 Мб:

• Zip (Windows 8.1): 316 MB (48.3% от оригинального размера)
• Zip (WinZip): 314 MB (48% от оригинального размера)
• RAR (WinRAR): 307 MB (46.9% от оригинального размера)
• 7z (7-Zip): 301 MB (46% от оригинального размера)

Кто же стал лидером файлового сжатия на основе тестов

Лидером чистого сжатия становится формат 7z, что на самом деле это не является удивительным для этого популярного формата. Если вы хотите, что ни будь сжать и использовать при этом как можно меньше места для хранения, нужно использовать именно 7z. Если ко всему этому воспользоваться настройками программы для экономии ещё большего места, то сжать необходимый файл можно ещё лучше. При этом, время сжатия и дальнейшей распаковки тоже увеличится.

Результаты RAR и Zip были очень близки друг к другу, а для интегрированной в Windows 8.1 WinZip не составит труда открыть формат Zip.
Для максимально сжатия лучше использовать 7-Zip с 7z, а вот для большего удобства и максимальной совместимости лучшим будет создание Zip-файлов, с помощью интегрированного в операционной системе функционала.

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

Популярные форматы, которые уже интегрированные в операционные системы:

• Windows: только zip. Эта функция была добавлена ещё во времена Windows XP, скорее всего каждый пользователь системы Windows сможет создавать и извлекать zip файлы.
• Mac OS X: формат сжатия zip поддерживается, а для прочих форматов архивов как tar, gz, bz2, 7z и rar потребуется установка стороннего программного обеспечения.
• Linux: Zip поддерживается прямо после установки, да большинство форматов сжатия могут быть использованы, но не без дополнительного программного обеспечения
• Crome OS: zip и rar поддерживаются, как и tar, gz, tar и bz2, но для этих расширений так же придётся установить дополнительные приложения.

Windows по умолчанию поддерживает только Zip файлы, так как Zip наиболее популярный и универсальный формат, но, если вам приходится работать с Mac или Linux вы, конечно же, можете использовать такой формат сжатия как 7z, но тогда вам придётся установить приложение для его открытия.

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

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

Доброго времени суток.
Сегодня я хочу коснуться темы сжатия данных без потерь. Несмотря на то, что на хабре уже были статьи, посвященные некоторым алгоритмам, мне захотелось рассказать об этом чуть более подробно.
Я постараюсь давать как математическое описание, так и описание в обычном виде, для того, чтобы каждый мог найти для себя что-то интересное.

В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.

Сжатие. Нужно ли оно в наше время?

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

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

Конечно, можно придумать еще множество различных ситуаций, в которых сжатие окажется полезным, но нам достаточно и этих нескольких примеров.

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

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

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

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

Данные восстанавливаются с точностью до бита, что не приводит к каким-либо потерям информации. Однако, сжатие без потерь показывает обычно худшие степени сжатия.

Итак, перейдем к рассмотрению алгоритмов сжатия без потерь.

Универсальные методы сжатия без потерь

В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.

Вторая группа методов – это статистические методы сжатия. В свою очередь, эти методы делятся на адаптивные (или поточные), и блочные.
В первом (адаптивном) варианте, вычисление вероятностей для новых данных происходит по данным, уже обработанным при кодировании. К этим методам относятся адаптивные варианты алгоритмов Хаффмана и Шеннона-Фано.
Во втором (блочном) случае, статистика каждого блока данных высчитывается отдельно, и добавляется к самому сжатому блоку. Сюда можно отнести статические варианты методов Хаффмана, Шеннона-Фано, и арифметического кодирования.

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon's source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики

Если вероятность появления элемента s_i равна p(s_i), то наиболее выгодно будет представить этот элемент — log₂p(s_i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log₂p(s_i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = i)> неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента s_i распределение вероятностей F примет некоторое значение F_k, то есть для каждого элемента F= F_k и H= H_k.

Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей p_k(s_i) для всех элементов s_i.

Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как

Где P_k — вероятность нахождения источника в состоянии k.

Итак, на данном этапе мы знаем, что сжатие основано на замене часто встречающихся элементов короткими кодами, и наоборот, а так же знаем, как определить среднюю длину кодов. Но что же такое код, кодирование, и как оно происходит?

Кодирование без памяти

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

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a₁, a₂,… ,a_n) словом, а число n — длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

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

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием.

Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a₁ <-> B₁
a₂ <-> B₂
…
a_n <-> B_n

Это соответствие называют схемой, и обозначают ∑.
В этом случае слова B₁, B₂,…, B_n называют элементарными кодами, а вид кодирования с их помощью — алфавитным кодированием. Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование. Теперь введем понятие префикс.

Пусть слово B имеет вид B=B'B''. Тогда B' называют началом, или префиксом слова B, а B'' — его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять — это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово B_i не является префиксом слова B_j.
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.

Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.

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

Алгоритм Хаффмана использует частоту появления одинаковых байт во входном блоке данных, и ставит в соответствие часто встречающимся блокам цепочки бит меньшей длины, и наоборот. Этот код является минимально – избыточным кодом. Рассмотрим случай, когда, не зависимо от входного потока, алфавит выходного потока состоит из всего 2 символов – нуля и единицы.

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов — < a₁, a₂, a₃, a₄>. Предположим также, что вероятности появления этих символов равны соответственно p₁=0.5; p₂=0.24; p₃=0.15; p₄=0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

1. Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p'.
2. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
3. Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p''.
4. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
5. Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее:

Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:

Поскольку ни один из данных кодов не является префиксом какого-нибудь другого (то есть, мы получили пресловутое префиксное множество), мы можем однозначно определить каждый код в выходном потоке.
Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот.
Если предположить, что изначально для хранения каждого символа использовался один байт, то можно посчитать, насколько нам удалось уменьшить данные.

Пусть на входу у нас была строка из 1000 символов, в которой символ a₁ встречался 500 раз, a₂ — 240, a₃ — 150, и a₄ — 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑p_il_i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

Напомню, что согласно Шеннону, средняя длина кодов составляет . Подставив в это уравнение наши значения вероятностей, мы получим среднюю длину кодов равную 1.75496602732291, что весьма и весьма близко к полученному нами результату.
Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.

Заключение

Итак, в этой статье я постарался рассказать об общих принципах, по которым происходит сжатие без потерь, а также рассмотрел один из канонических алгоритмов — кодирование по Хаффману.
Если статья придется по вкусу хабросообществу, то я с удовольствием напишу продолжение, так как есть еще множество интересных вещей, касающихся сжатия без потерь; это как классические алгоритмы, так и предварительные преобразования данных (например, преобразование Барроуза-Уилира), ну и, конечно, специфические алгоритмы для сжатия звука, видео и изображений (самая, на мой взгляд, интересная тема).

Как всегда, начну со старческого брюзжания. Вот лет двадцать назад… Собственно говоря, двадцать лет назад и выбора-то особо не было.

реклама

Потому что были компакт-диски, которые превращались в WAV-файлы, занимавшие пространство среднего «винчестера» – ну и на ОС немножко места оставалось. И на BBS. И на игры. И на архив файлов. И все. Потому что средний размер жесткого диска тогда составлял какие-то сказочные сегодня 850 мегабайт. Да, именно что 850 – и именно мегабайт. Толчок всему дало появление формата MP3 в 1997 году, и это был очень знаменательный год!

Я очень хорошо помню те времена. Тогда мы с другом «возрадовались до плеши» и принялись активно кодировать компакт-диски в самые популярные 128 кбит/с с joint stereo (это когда фактически пишется один канал, и к нему добавляется информация об отличиях второй дорожки – если они есть). Еще бы, теперь альбом занимал смешные 50-70 мегабайт, и компьютерные пластиковые колонки казались вершиной прогресса. Различные звуковые карты за 200,500 или 800 долларов в журналах казались чем-то страшным и далеким. Зачем? Ведь есть MP3 128 кбит/с, смотрите, какое крутое качество!

Шли месяцы и годы (скорее ближе к месяцам). Менялись колонки, развивался MP3, и мы тогда, юные падаваны старшего школьного и начального студенческого возраста, экспериментировали с битрейтами и появившимся тогда первым конкурентом MP3 – таинственным Vorbis OGG. Сколько часов на самой разной акустике (а мы тогда уже открыли, что даже советская «Вега» уделывала все эти пластиковые недоразумения за десять баксов) было отслушано – не сосчитать.

В итоге выводы выкристаллизовались такие: OGG круче MP3 на средних битрейтах, а на высших все равны. Но преимущество OGG было в том, что на средних битрейтах файл не только лучше звучал, но и занимал меньше места. Недостатком – то, что при всех этих достоинствах OGG питался большим количеством оперативной памяти и ресурсов процессора. А в те времена мощности были, как понимаете, совсем не те.

MSI RTX 3070 сливают дешевле любой другой, это за копейки Дешевая 3070 Gigabyte Gaming - успей пока не началось

Почему я так подробно пишу об отличиях OGG от MP3? Потому что уже начался рассказ про форматы, и все эти выводы справедливы и по сей день. Ну вот, теперь вы знаете почти все про OGG: а больше знать и не надо, поскольку его сегодня поддерживают не так уже много устройств.

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

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

реклама

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

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

• Форматы без сжатия (WAV, AIFF);
• Со сжатием без потерь – lossless в простонародье (FLAC, APE);
• Со сжатием с потерями – он же lossy (MP3, OGG).

Все, это была минутка Википедии.

И да, я раскрою вам правду на то, стоит ли тратить терабайты на lossless.

MP3: скорее отстреляться

Конечно, начать надо с MP3. И, перефразируя название фильма, – «и это все об MP3». Безусловно, все вы про него знаете, и быть Капитаном Очевидность здесь не вижу смысла. Все, что воспроизводит звук сегодня, поддерживает MP3, вплоть до максимума.

В чем его главные нарекания и минусы? В основном – в срезе верхних частот и «прореживании» всех остальных.

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

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

Но плюс в том, что у него нет DRM и прочих видов защит от копирования, которые редиски-владельцы авторских прав могут ставить на свою музыку.

Отдельного абзаца заслуживает VBR. VBR – это сокращение от Variable BitRate, переменный битрейт. Основная идея VBR – то, что кодек автоматически выбирает нужный битрейт в зависимости от контента. Это происходит еще на этапе кодирования, и главное декларируемое преимущество технологии – меньший размер файла при вроде бы том же высоком качестве (разумеется, кодирование происходит все-таки «вокруг» заданной частоты).

В реальности же качество VBR заметно проигрывает своему оппоненту CBR (Constant BitRate – постоянный битрейт), плюс ко всему заметно нагружает процессор. Конечно, на современных многоядерных ЦП это не так что бы заметно, но – «как-то, доктор, неаккуратненько». В общем, смысл тут прост: VBR лучше не пользоваться, поскольку выигрыш в размерах минимален, microSD сегодня дешевы, HDD тоже не состояние стоят, а проблем от них больше. И, опять же, качество хромает.

Чем сегодня кодируют MP3? На заре формата было очень много разных декодеров, сегодня их тоже можно найти, если постараться, кто-то постоянно тоже изобретает велосипед, но безусловный авторитет уже долгие годы – LAME. Несмотря на стебный перевод названия (вольно – «хромуля»), кодек справляется со своей задачей блестяще.

Какой программой пользоваться для кодирования – тоже понятно, общепринятым авторитетом является грозный EAC (Exact Audio Copy, и он точно соответствует своему названию). И то, и другое распространяется совершенно бесплатно (более того – LAME в принципе встроен почти во все по умолчанию), так что можете попробовать свои силы в кодировании того, что и так уже сто раз кодировано.

реклама

WMA: все плохо, как всегда

Компания Microsoft разработала WMA как альтернативу MP3. Но, как и в случае с платформой Windows Phone, люди посмотрели на него, потыкали пальцем – и забросили на полку.

Потому как файл WMA изобилует мелкими неприятностями, которые сами по себе вроде бы и не так страшны (например, плохая устойчивость к ошибкам: чуть поврежденный файл про кодировании или передаче становится непригодным полностью), но в совокупности WMA становится несерьезным. К тому же, опять же декларировалось, что при меньшем битрейте WMA будет качественным. Серьезно?

Конечно, WMA сегодня поддерживает все, что поддерживает MP3. Конечно, декларируется, что поддерживается lossless-кодирование, начиная с версии 9.1. Ну поддерживается. А дальше-то что? Кто-то этим пользуется?

реклама

Плюс ко всему – в WMA можно зашивать DRM-защиту. От такого фактора потирают жадные лапки правообладатели, но говорят «фи» рядовые пользователи. Еще один гвоздь в крышку гроба WMA.

В общем, формат мутный и явно нежизнеспособный. Как и платформа Windows Phone. Как и Surface. У Microsoft хорошо получалось делать операционные системы, но вот сторонние проекты – слабовато.

Читайте также:

  
• Samsung xe500t1c h01ru driver wi fi как установить
  
• Excel если не равно тексту то
  
• Openserver не открывает сайт в браузере
  
• Контрольная работа по эксель вычислите значение выражения
  
• Как провести оплату в 1с унф