Что такое сжатие без потерь и как оно работает

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

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

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

Есть два принципиальных вида сжатия — с потерями и без.

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

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

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

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

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

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

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

Вот пример: берём песню Beyonce — All The Single Ladies. Там есть два таких пассажа:

All the single ladies

Now put your hands up

…

If you like it then you shoulda put a ring on it

Don’t be mad once you see that he want it

If you like it then you shoulda put a ring on it

Здесь 281 знак. Мы видим, что некоторые строчки повторяются. Закодируем их:

ТАБЛИЦА СЖАТИЯ

\a\ All the single ladies

\b\ Now put your hands up

\c\ If you like it then you shoulda put a ring on it

\d\ Don’t be mad once you see that he want it

ТЕКСТ ПЕСНИ

\a\ \a\ \a\ \b\

…

\c\ \c\ \d\ \c\

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

Сжатие без потерь на примере аудио

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

Для таких ситуаций используют сжатие без потерь: оно уменьшает файл в 2–3 раза, не искажая звук. Алгоритмы, которые сжимают аудио, называются кодеками. FLAC и Apple Lossless — два популярных кодека для сжатия аудио без потерь.

Сравните сами размер и качество двухминутного аудио:

Оригинал — без сжатия, формат WAV, 23 мегабайта

Сжатие без потерь — формат FLAC с теми же параметрами, что и WAV, 10 мегабайт

Где ещё применяется сжатие без потерь

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

Myspace потеряла архивы за 12 лет. Как не потерять свои

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