Сжатие данных без потерь информации. Формат Lossless - что такое? Музыка высокого качества в формате Lossless

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

Если вы возьмете обыкновенный Audio CD диск с аналоговым звуком запишете его в формате WAV для звука без компрессии, затем выполните компрессию WAV с использованием кодека lossless, далее полученный звуковой файл декомпрессируете в WAV и результат запишете на чистый CD, то можете получить два совершенно идентичных Audio CD.

Преимущество lossless для хранения звуковой коллекции состоит в том, что качество записей намного выше, чем у lossy кодеков, а места они занимают меньше, чем несжатое аудио. Правда, файлы lossy меньше по размеру, чем музыкальные файлы без потери качества. Большая часть современных программ-плееров понимают формат lossless. Те программы, которые не в состоянии его воспроизводить, могут легко этому научиться, используя плагин lossless. Что такое звуковые форматы lossless?

Звуковые форматы без потери качества

Подлинного любителя музыки вряд ли устроит звучание музыки, записанной в форматах со сжатием Ogg Vorbis или MP3. Конечно, если аудиозаписи прослушивать на бытовой аудиоаппаратуре, недостатки звучания невозможно уловить на слух, но если попытаться проиграть сжатый файл на высококачественной аппаратуре класса Hi-Fi, сразу обнаружатся недочеты звука. Безусловно, создать коллекцию качественной музыки на CD или виниловых пластинках нелегко. Есть разумная альтернатива этому пути для любителей качественного звука - lossless музыка. Ее можно хранить на ПК в виде, дающем возможность сохранить неизменными исходные параметры музыки, даже если применено сжатие. Этот путь одновременно решает проблемы высокого качества музыки и компактного ее хранения, ведь аудиоаппаратура для прослушивания (наушники, колонки, усилители) имеет вполне доступную цену.

Несжатые форматы звука без потери качества:

• CDDA — является стандартом аудио CD;
• WAV — Microsoft Wave;
• IFF-8SVX;
• IFF-16SV;
• AIFF;

Сжатые форматы:

• FLAC;
• APE - Monkey’s Audio;
• M4A - Apple Lossless - формат качественной музыки от Apple;
• WV - WavPack;
• WMA - Windows Media Audio 9;
• TTA - True Audio.
• LPAC;
• OFR - OptimFROG;
• RKA - RKAU;
• SHN - Shorten.

Формат FLAC

Самым распространенным форматом является формат От аудиокодеков с потерями его отличает то, что из звукового потока при его использовании не удаляется никаких данных. Это дает возможность с успехом использовать его для воспроизведения музыки на Hi-Fi- и Hi-End-оборудовании, а также для создания архива коллекции аудиозаписей.

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

Формат APE

В отличие от FLAC, для формата APE имеются только лишь кодеки и плагины, рассчитанные на платформу Windows. Для других платформ имеются дорогие решения от сторонних производителей ПО. Алгоритм способен достичь сжатия звуковой информации без потерь примерно в 1,5-2 раза. В него входит три главных этапа кодирования, из которых лишь один основан на применении свойств, присущих звуку для сжатия. Остальные схожи с обычными архиваторами. Несмотря на то что алгоритм сжатия распространяется бесплатно, ограничения лицензии таковы, что для музыкантов-любителей он практически недоступен.

Формат Apple Lossless

Музыка высокого качества lossless может прослушиваться с использованием кодека сжатия звука без ущерба качеству от компании Apple. Этот формат разработан компанией Apple для использования в собственных устройствах. Формат совместим плеерами iPod, имеющими специальные док-разъемы и новейшие прошивки. В формате не применен специфический инструментарий управления правами (DRM), но формат контейнера содержит такие возможности. Также он поддерживается приложением QuickTime и входит в качестве функции в программу iTunes.

Формат входит в состав библиотек, находящихся в свободном доступе, что дает возможность организовать прослушивание файлов в приложениях Windows. В 2011 году компания Apple обнародовала исходные коды формата, что открывает широкие перспективы перед кодеком. В будущем он может составить серьезную конкуренцию прочим форматам. Тесты продемонстрировали неплохие результаты. Сжатые файлы имеют размер от 40-60% от размера оригиналов. Впечатляет также скорость декодирования, что оправдывает его применение для мобильных устройств, производительность которых невелика.

Одним из недостатков кодека является совпадение расширения звуковых файлов с аудиокодеком Это приводит к путанице, ведь AAC не является форматом музыки высокого качества. Поэтому решено было данные хранить в MP4 контейнере с расширением.m4a.

Из других форматов стоит упомянуть Windows Media Audio 9 Lossless, входящий в состав приложения Windows Media. Он работает с Windows и Mac OS X. Правда, пользователи отзываются о нем не очень одобрительно. Часто возникают проблемы с совместимостью кодека, да и количество поддерживаемых каналов ограничено шестью.

Формат WavPack

WavPack - еще один свободно распространяемый аудиокодек, сжимающий звуковую информацию без потерь качества. В WavPack интегрирован эксклюзивный комбинированный режим, позволяющий создавать два файла. Один из файлов в таком режиме создается сравнительно небольшого потерями качества.wv, который можно проигрывать самостоятельно. Второй файл «.wvc» корректирует предыдущий «.wv» и в комбинации с ним дает возможность в восстановить оригинал в полной мере. Некоторым пользователям такой подход может показаться перспективным, ведь не нужно выбирать между двумя видами сжатия - всегда будут реализованы оба.

Заслуживает также внимания видеокодек с высококачественным звуком - lagarith lossless codec. Он работает быстро и качественно.

Софт для прослушивания lossless-аудио

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

Плеер WinAmp

Способен справиться практически со всеми форматами воспроизведения музыки без потерь качества lossless. Что такое хороший плеер lossless, можно понять на его примере. Он способен корректно справляться с обработкой отдельных треков в формате lossless. Это типичная проблема кодеков FLAC или APE. Она состоит в том, что оцифровывается сразу весь звуковой диск и записывается одним файлом без разделения на треки. Проблему разделения на треки призван решить добавочный файл, имеющий расширение.cue. Он содержит описание параметров доступа к каждому треку альбома. Обыкновенный плеер воспроизводит весь lossless файл целиком. Проигрыватель для lossless AIMP замечательно воспроизводит большую часть звуковых форматов и распознает треки в файле lossless формата.

Цифровые плееры с поддержкой lossless

Хорошо отзываются пользователи о цифровых плеерах jetAudio, Foobar2000, Spider Player. Кардинальных отличий между ними нет. Выбор любого устройства основывается на субъективном мнении меломана об удобстве интерфейса для воспроизведения lossless. Что такое lossless формат, можно узнать протестировав эти плееры.

Формат Apple Lossless проигрывается с использованием iTunes. Кроме того, данный кодек поддерживается популярным видеоплеером VLC.

Хозяева компьютеров, совместимых с Apple, могут использовать две интересные программы: Vox и Cog.

Они поддерживают такие lossless форматы:

• Apple Lossless;
• FLAC;
• Monkeys Audio;
• Wavpack.

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

Владельцы компьютеров с системой Windows могут использовать любое приложение, которое совместимо с кодеками музыки без потери качества: Foobar2000 или WinAmp. Для Winamp требуются специальные плагины. Lossless музыка хорошо воспроизводится на iTunes и KMPlayer. Достоинство iTunes, которого нет в других плеерах - возможность поддержки тегов.

Устройства, совместимые с lossless

Вряд ли хозяин фонотеки захочет расходовать время на то, чтобы преобразовать файлы из формата FLAC в MP3, чтобы иметь возможность прослушивания записей на своем гаджете. У смартфона или планшета ограниченные возможности, несравнимые с компьютером, но тем не менее многие из мобильных устройств проигрывают lossless-форматы.

Например, владельцы устройств под управлением Android могут воспользоваться плеером andLess. Он способен проигрывать файлы в форматах FLAC, APE, несжатый WAV и другие форматы, поддерживаемые Android.

Хуже обстоят дела у владельцев устройств на платформе Blackberry. Лишь обладатели моделей Bold 9000 и 8900 и более поздних версий могут прослушивать lossless формат.

Обладатели устройств Apple без проблем могут использовать кодек ALAC. Он поддерживается плеером iPod (кроме shuffle), телефоном iPhone и планшетом iPad. Для формата FLAC можно скачать FLAC Player в App Store.

Кодек FLAC поддерживается устройствами Samsung Galaxy, некоторыми смартфонами Sony Ericsson и плеерами iriver.

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

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

Аппаратура для прослушивания

Чтобы получить настоящее удовольствие от качества звука, необходима специальная аппаратура: наушники, усилители, колонки. Проще всего, конечно, с наушниками. Если вы намерены наслаждаться музыкой сидя за компьютером, они подойдут лучше всего. Хорошо отзываются пользователи о продукции компаний Koss и Sennheiser. Особенное внимание нужно обратить на размер мембраны. Чем он больше, тем лучше звучание. Важно не обмануться. Некоторые производители ставят маленькую мембрану в большие амбушюры - выглядят такие наушники солидно, а звук пригоден лишь для прослушивания mp3.

Почитателям аппаратуры качественного звука (Hi-Fi или Hi-End) трудно что-либо рекомендовать. Выбор в этой области ограничивается лишь бюджетом и вкусами. Эквалайзер, усилитель, акустика - выбор этих устройств имеет множество вариантов. Владельцам ПК, выбирающим себе качественную лучше остановиться на бюджетных мониторных колонках любого известного бренда. Хорошо отзываются пользователи об акустике Microlab серии SOLO. Чтобы музыка в lossless качестве звучала хорошо, важно приобрести акустику с наличием сабвуфера. не под силу справиться с воспроизведением нижней полосы частот.

Итоги

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

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

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

Когда необходимо сжатие данных?

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

Передача по электронной почте.

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

Публикация данных на интернет -сайтах и порталах.

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

Экономия свободного места на диске.

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

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

Способы сжатия информации

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

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

Сжатие без потери информации

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

Пример 1

Приведем простой пример. Русский язык включает в себя $33$ буквы, $10$ цифр и еще примерно $15$ знаков препинания и других специальных символов. Для текста, записанного только прописными русскими буквами (например как в телеграммах) вполне хватило бы $60$ разных значений. Тем не менее, каждый символ обычно кодируется байтом, содержащим, как нам известно, 8 битов, и может выражаться $256$ различными кодами. Это один из первых факторов, характеризующих избыточность. Для телеграфного текста вполне хватило бы и $6$ битов на символ.

Пример 2

Рассмотрим другой пример. В международной кодировке символов ASCII для кодирования любого символа выделяется одинаковое количество битов ($8$), в то время, как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, к примеру, в азбуке Морзе буквы «Е» и «Т», которые встречаются очень часто, кодируются $1$ знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ($ - -$) и «Ц» ($- - $), кодируются $4$ знаками.

Замечание 1

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

Алгоритмы, в основу которых положено перекодирование информации, называются алгоритмами Хаффмана.

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

В данном алгоритме сжатие информации осуществляется путем статистического кодирования или на основе словаря, который предварительно был создан. Согласно статистическому алгоритму Хаффмана каждому входному символу присваивается определенный код. При этом наиболее часто используемому символу - наиболее короткий код, а наиболее редко используемому - более длинный. В качестве примера на диаграмме приведено распределение частоты использования отдельных букв английского алфавита (рис.1). Такое распределение может быть построено и для русского языка. Таблицы кодирования создаются заранее и имеют ограниченный размер. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия статистический метод требует больших объемов памяти.

Рисунок 1. Распределение английских букв по их частоте использования

Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский имеет самый высокий уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на $30\%$ больше. Если речь идет о стихотворном тексте, избыточность может быть до $2$ раз выше.

Замечание 2

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

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

Еще одним недостатком кодов является то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и $0,1$, и $0,01$ бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте.

Замечание 3

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

Лекция №4. Сжатие информации

Принципы сжатия информации

Цель сжатия данных - обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного - запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

Виды сжатия

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

Сжатие без потери информации.

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

Методы сжатия этого класса не могут допустить утрату информа­ции, поэтому они основаны только на устранении ее избыточности, а информация имеет избыточность почти всегда (правда, если до этого кто-то ее уже не уплотнил). Если бы избыточности не было, нечего было бы и сжимать.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ( - -) и «Ц» (- - ), кодиру­ются четырьмя знаками. Неэффективная кодировка - второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Наличие повторяющихся фрагментов - третье основание для избыточности. В текстах это встречается редко, но в таблицах и в графике повторение кодов - обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding ).

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

Сжатие с потерей информации.

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

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

В то же время, существуют материалы, в которых стоит пожерт­вовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». Но поскольку при создании этих мате­риалов определенный «шум» все равно присутствует, его неболь­шое увеличение не всегда выглядит критичным, а выигрыш в раз­мерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются.MPG для видео и.МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Код Шеннона-Фэно

Для дальнейших рассуждений будет удобно представить наш исходный файл с текстом как источник символов, которые по одному появляются на его выходе. Мы не знаем заранее, какой символ будет следующим, но мы знаем, что с вероятностью p1 появится буква "а", с вероятностью p2 -буква "б" и т.д.

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

Сумма этих вероятностей составляет, естественно, единицу. Разобьем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов - двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой - цифрой 1.

Снова разобьем первую группу (А-В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй - цифру 1.

Будем повторять эту операцию до тех пор, пока на каждой вершине нашего "дерева" не останется по одному символу. Полное дерево для нашего алфавита будет иметь 31 узел.

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

Итак, принцип очевиден - часто встречающиеся символы кодируются меньшим числом бит, редко встречающиеся - большим. В результате среднестатистическое количество бит на символ будет равно

где ni - количество бит, кодирующих i-й символ, pi - вероятность появления i-го символа.

Код Хаффмана.

Алгоритм Хаффмана изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

Недостатки методов

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

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

Еще один недостаток кодов - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте. Например, если в тексте на английском языке нам встречается буква q, то мы с уверенностью сможем сказать, что после нее будет идти буква u.

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". («красный, красный, ..., красный» записывается как «N красных»).

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

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF - файла находится палитра - таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

Фрактальное сжатие

Фрактальное сжатие изображений - это алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (IFS, как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры - до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил.

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

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

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

Во-первых, заметим, что и тот, и другой алгоритм оперируют 8-битными (в градациях серого) и 24-битными полноцветными изображениями. Оба являются алгоритмами сжатия с потерями и обеспечивают близкие коэффициенты архивации. И у фрактального алгоритма, и у JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG. Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вероятность появления элемента s i равна p(s i), то наиболее выгодно будет представить этот элемент - log 2 p(s i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log 2 p(s i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = {p(s 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 1 , a 2 ,… ,a n) словом , а число n - длиной этого слова.

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

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

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

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

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

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

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

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

Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?
Оно происходит в три этапа.

1. Составляется алфавит Ψ символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
2. Каждому символу a i из алфавита Ψ ставится в соответствие некое слово B i из префиксного множества Ω.
3. Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.

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

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

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

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

1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
2. Два символа a j-1 и a j входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова B j-1 , и 1 в начало слова B j , которые будут впоследствии являться кодами символов a j-1 и a j соответственно.
3. Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).

Шаги 2 и 3 повторяются до тех пор, пока в алфавите не останется только 1 псевдосимвол, содержащий все изначальные символы алфавита. При этом, поскольку на каждом шаге и для каждого символа происходит изменение соответствующего ему слова B i (путем добавление единицы или нуля), то после завершения этой процедуры каждому изначальному символу алфавита a i будет соответствовать некий код B i .

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов - { a 1 , a 2 , a 3 , a 4 }. Предположим также, что вероятности появления этих символов равны соответственно p 1 =0.5; p 2 =0.24; p 3 =0.15; p 4 =0.11 (сумма всех вероятностей, очевидно, равна единице).

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

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

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

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

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

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

Пусть на входу у нас была строка из 1000 символов, в которой символ a 1 встречался 500 раз, a 2 - 240, a 3 - 150, и a 4 - 110 раз.

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

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

Заключение

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

Литература

• Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.
• Д. Сэломон. Сжатие данных, изображения и звука; ISBN 5-94836-027-Х; 2004г.

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

Вступление

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

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

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

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

Без сжатия

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

Для воспроизведения WAV-файлов вам не потребуется какое-то специальное программное обеспечение, так как этот формат понимают все медиаплееры, включая и встроенный в систему Windows штатный проигрыватель аудиофайлов Windows Media.

Еще одним форматом, использующимся для хранения несжатого аудио, о котором стоит упомянуть, является разработка компании Appleпод названием AIFF (Audio Interchange File Format). Как вы, наверное, уже догадались, наиболее часто он используется в компьютерах Macintosh под управлением систем Mac OS X.

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

Алгоритмы, осуществляющие сжатие аудиофайлов без потерь работают по принципу обычных архиваторов. Обеспечивая не самый высокий уровень сжатия (от 40 до 60%), при этом они практически не влияют на качество звука. Так же стоит отметить, что в этом случае, закодированные данные можно полностью восстановить до первоначального вида. Поэтому использование сжатия без потерь наиболее часто применяется в тех случаях, когда важно сохранить идентичность сжатых данных оригиналу.

Наиболее популярными аудиоформатами в этой группе являются FLAC (Free Lossless Audio Codec), APE (Monkey’s Audio), WMA (Windows Media Lossless) и ALAC (Apple Lossless Audio Codec). У каждого из них есть свои плюсы и свои минусы. Например, кодек APEдает несколько больший выигрыш в сжатии, а FLAC является более распространенным. В общем же, все настоящие меломаны хранят свои музыкальные коллекции именно в lossless-форматах, так как в них не удаляется никаких данных из аудиопотока, а созданные с помощью этих кодеков файлы, можно прослушивать даже на высококачественной звуковой аппаратуре.

Для воспроизведения сжатых без потерь форматов, как правило, используются сторонние плееры (кроме WMA), такие как MPlayer, foobar, AIMP, Winamp, VLC и прочие, так как в них уже встроены все необходимые кодеки. Другим вариантом является отдельная установка пакета дополнительных кодеков (например, K-Lite), после чего прослушивание файлов в lossless-формате становится доступным практически из любого аудиопроигрывателя.

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

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

Для определения качества оцифрованного звука наиболее часто применяется такой показатель, как битрейт - скорость звукового потока, получившаяся после сжатия и измеряемая в килобитах в секунду (kbps). Как мы уже говорили, в среднем минута несжатого звука занимает около 10 Мб, что соответствует аудиопотоку примерно в 1400 кбит/c. После кодирования с потерями, его битрейт может снизиться до 56 кбит/с. При этом, стоит учитывать, что для сохранения естественного звучания скорость потока должна быть не ниже 192 или 256 кбит/c. Если же битрейт потока составляет 320 кбит/c и более, то разница в звучании для большинства людей между сжатым и несжатым аудио практически исчезает.

Самым популярным форматом здесь однозначно считается знаменитый и всеми любимый MP3, разработанный специалистами известной группы MPEG (Moving Picture Experts Group). Наиболее широко он используется для кодирования аудиофайлов, размещаемых в интернете и различных файлообменниках из-за возможности существенно уменьшить размер передаваемых данных, что при низкой скорости подключения к сети немаловажно.

Другими известными форматами из этой серии являются AAC (Advanced Audio Coding) и OGG Vorbis. При этом, будучи менее популярными, их алгоритмы сжатия совершеннее, чем у основного конкурента. Так при одинаковом размере файла, они обеспечивают лучшее качество звукового ряда по сравнению с MP3. Еще одно серьезное преимущество данных форматов - возможность кодирования до 48 звуковых каналов у AAC и 255 у OGG, против всего двух у MP3.

Стоит отметить, что и формат WMA - собственность компании Microsoft, изначально создавался для хранения и трансляции аудиоинформации в сжатом виде с потерями, а кодирование без потери качества добавилось к нему не так давно, начиная с Windows Media Audio 9.1. Номинально этот формат обеспечивает лучшую степень сжатия, чем MP3, что дает возможность разработчикам противопоставлять его в качестве альтернативы конкурирующим алгоритмам AAC и OGG. Правда широкому распространению WMA мешает его закрытость и ограниченность применения на многих платформах (операционных системах). Да и встроенная поддержка цифровой системы управления авторскими правами (DRM) не добавляет популярности детищу Microsoft.

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

И хотя другие форматы пока что такой поддержкой похвастаться не могут, у них тоже все не так уж и плохо. Так AAC нашел широкую поддержку со стороны компании Apple, которая использует его алгоритмы для хранения аудиокниг, подкаст, музыкальных композиций в магазине iTunes и рингтонов. Так что для поклонников компьютеров Macintosh, планшетов iPad, смартфонов iPhone и плееров iPod этот формат можно считать «родным».

Файлы WMA легко воспроизводятся на любом ПК под управлением операционной системы Windows, которая является самой распространенной в мире. При этом многие производители портативных аудиоплееров и стационарных проигрывателей оптических дисков так же поддерживают этот формат. А вот для прослушивания файлов в форматах OGG Vorbis или AAC в Windows-системах придется установить специальные кодеки. Хотя это не проблема. Установка вышеупомянутого бесплатного пакета кодеков K-Lite Codek Pack позволит проигрывать на вашем компьютере с помощью любимого плеера практически любые звуковые файлы.

Заключение

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

Плееры - служат для непосредственного воспроизведения звуковых файлов, а так же часто используются для каталогизации и упорядочивания музыкальных коллекций. Их количество столь огромно, что и не сосчитать. Но все же, что бы несколько облегчить вам выбор, приведем, на наш взгляд, двенадцать самых популярных: Windows Media Player (встроен в систему), Winamp, KMPlayer, iTunes, GOM Player, jetAudio, VLC Media Player (VideoLAN), AIMP, BSPlayer, Real Player, WinDVD и Foobar2000.

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

Рипперы (грабберы) - позволяют извлекать цифровую звуковую информацию с оптических носителей (Audio-CD, DVD) и сохранять ее в различных форматах. Несмотря на многочисленность всевозможным грабберов, на этом поприще наибольшую популярность снискало приложение EAC (Exact Audio Copy), позволяющее делать наиболее точные копии дисков. К другим популярным рипперам относятся: Audiograbber, Reaper, Easy CD-DA Extractor и прочие.

Редакторы - программы, предназначенные для создания, записи и редактирования звуковых данных. В этой группе существуют как довольно простые программы, позволяющие сделать элементарные операции с аудиофайлом (вырезать, обрезать, объединить, нормализовать и т.д.), так и настоящие монстры для профессиональной работы со звуком. Среди небольших редакторов можно выделить приложение Nero WaveEditor, за его скромный размер и при этом довольно высокую функциональность. К наиболее популярным профессиональным решениям обработки звука относятся: Adobe Audition, Sound Forge, Cubase, Sony Vegas Pro и другие.

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

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