Какие файлы можно сжимать без потерь

Обновлено: 05.07.2024

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

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

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

Совсем немного теории для непрофессионалов

Позволю себе начать эту весьма серьезную тему со старой шутки. Беседуют два пенсионера:

— Вы не могли бы сказать мне номер вашего телефона? — говорит один.

— Вы знаете, — признается второй, — я, к сожалению, точно его не помню.

— Какая жалость, — сокрушается первый, — ну скажите хотя бы приблизительно…

Действительно, ответ поражает своей нелепостью. Совершенно очевидно, что в семизначном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной. Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна — что произойдет в подобном случае? Для наглядности рассмотрим себе конкретный пример: телефонный номер 233 34 44.

Соответственно запись «Двсти трцать три трицть четре сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается. Это связано с тем, что наш язык имеет определенную избыточность, которая, с одной стороны, увеличивает длину записи, а с другой — повышает надежность ее передачи. Объясняется это тем, что вероятность появления каждого последующего символа в цифровой записи телефона одинакова, в то время как в тексте, записанном словами русского языка, это не так. Очевидно, например, что твердый знак в русском языке появляется значительно реже, чем, например, буква «а». Более того, некоторые сочетания букв более вероятны, чем другие, а такие, как два твердых знака подряд, невозможны в принципе, и так далее. Зная, какова вероятность появления какой-либо буквы в тексте, и сравнив ее с максимальной, можно установить, насколько экономичен данный способ кодирования (в нашем случае — русский язык).

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

Избыточность естественных языков

R = (Hmax — H)/ Hmax

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

Кодирование информации

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

Говоря о кодах сжатия, различают понятия «сжатие без потерь» и «сжатие с потерями». Очевидно, что когда мы имеем дело с информацией типа «номер телефона», то сжатие такой записи за счет потери части символов не ведет ни к чему хорошему. Тем не менее можно представить целый ряд ситуаций, когда потеря части информации не приводит к потери полезности оставшейся. Сжатие с потерями применяется в основном для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где в силу огромных размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не существенными для восприятия этой информации человеком. Особые возможности для сжатия информации имеются при компрессии видео. В ряде случаев большая часть изображения передается из кадра в кадр без изменений, что позволяет строить алгоритмы сжатия на основе выборочного отслеживания только части «картинки». В частном случае изображение говорящего человека, не меняющего своего положения, может обновляться только в области лица или даже только рта — то есть в той части, где происходят наиболее быстрые изменения от кадра к кадру.

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

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

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

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

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

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

Наиболее известны два алгоритма сжатия без потерь: это кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам имен создателей Lempel, Ziv, Welch), которые представляют основные подходы при сжатии информации. Кодирование Хаффмена появилось в начале 50-х; принцип его заключается в уменьшении количества битов, используемых для представления часто встречающихся символов и соответственно в увеличении количества битов, используемых для редко встречающихся символов. Метод LZW кодирует строки символов, анализируя входной поток для построения расширенного алфавита, основанного на строках, которые он обрабатывает. Оба подхода обеспечивают уменьшение избыточной информации во входных данных.

Кодирование Хаффмена

Статическое кодирование

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

Динамическое кодирование

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

LZW-сжатие

Алгоритм LZW [2], предложенный сравнительно недавно (в 1984 году), запатентован и принадлежит фирме Sperry.

Какой же выбрать архиватор?

Наверное, читателю будет интересно узнать, какой же архиватор лучше. Ответ на этот вопрос далеко не однозначен.

Если посмотреть на таблицу, в которой «соревнуются» архиваторы (а сделать это можно как на соответствующем сайте в Интернете [3], так и на нашем CD-ROM), то можно увидеть, что количество программ, принимающих участие в «соревнованиях», превышает сотню. Как же выбрать из этого многообразия необходимый архиватор?

Если вас не волнуют меркантильные соображения, то прежде всего необходимо уяснить, что имеется целый ряд архиваторов, которые оптимизированы на решение конкретных задач. В связи с этим существуют различные виды специализированных тестов, например на сжатие только текстовых файлов или только графических. Так, в частности, Wave Zip в первую очередь умеет сжимать WAV-файлы, а мультимедийный архиватор ERI лучше всех упаковывает TIFF-файлы. Поэтому если вас интересует сжатие какого-то определенного типа файлов, то можно подыскать программу, которая изначально предназначена специально для этого.

Существует тип архиваторов (так называемые Exepackers), которые служат для сжатия исполняемых модулей COM, EXE или DLL. Файл упаковывается таким образом, что при запуске он сам себя распаковывает в памяти «на лету» и далее работает в обычном режиме.

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

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

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

Поддержка различных форматов

Большинство программ поддерживают один или два формата. Однако некоторые, такие, например, как программа WinAce, поддерживают множество форматов, осуществляя компрессию в форматах ACE, ZIP, LHA, MS-CAB, JAVA JAR и декомпрессию в форматах ACE, ZIP, LHA, MS-CAB, RAR, ARC, ARJ, GZip, TAR, ZOO, JAR.

Умение создавать solid-архивы

Создание solid-архивов — это архивирование, при котором увеличение сжатия возрастает при наличии большого числа одновременно обрабатываемых коротких файлов. Часть архиваторов, например ACB, всегда создают solid-архивы, другие, такие как RAR или 777, предоставляют возможность их создания, а некоторые, например ARJ, этого делать вообще не умеют.

Возможность создавать многотомные архивы

Многотомные архивы необходимы, когда файлы переносятся с компьютера на компьютер с помощью дискет и архив не помещается на одной дискете.

Возможность работы в качестве менеджера архивов

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

Возможность парольной защиты

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

Удобство в работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что дальше

В следующей части разберём, как работает сжатие с потерями и почему благодаря этому у нас есть ТикТок и Ютуб.

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

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

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

Разумеется, да. Конечно, все мы понимаем, что сейчас нам доступны и носители информации большого объема, и высокоскоростные каналы передачи данных. Однако, одновременно с этим растут и объемы передаваемой информации. Если несколько лет назад мы смотрели 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 (сумма всех вероятностей, очевидно, равна единице).

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

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

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

Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 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, что весьма и весьма близко к полученному нами результату.
Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.

Заключение

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

Вопрос от пользователя

Здравствуйте, Александр.

Можно ли как-нибудь сжать видео без потери качества? Не так давно скачал программу (про которую написали подобное) и попробовал — видео все-таки стало смотреться хуже, качество заметно упало.

Вообще, довольно популярный вопрос, и часто начинающие видео-любители попадаются на это "удочку" — сжать то можно любое видео, только почти всегда будет потеря в качестве!

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

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

Ликбез по сжатию видео — уменьшение размера видеофайла

Немного теории: что нужно знать для правильного сжатия

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

Вообще, почти все видео (99,9%), которые вы находите в сети (смотрите, скачиваете и т.д.) уже сжаты каким-то кодеком. Не сжатое видео — занимает довольно большой размер на диске (например, один фильм в высоком качестве может занять несколько терабайт!) .

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

Таким образом, чтобы можно было сжать видео без потери качества, нужно исходить из 2-х моментов:

если видео было сжато "слабым" кодеком (который обеспечивает далеко не макс. сжатие) — то его можно пережать и уменьшить размер видеофайла, при этом не ухудшая качество картинки (кстати, как правило, в этом случае - нужен более мощный ПК для просмотра. Например, MPEG2 видео можно смотреть на более слабом ПК (без рывков и задержек), чем, скажем, MP4, ну об этом я еще пару слов скажу ниже) ;
от устройства, на котором вы хотите смотреть видео . Например, если вы смотрите видео на небольшом экране с низким разрешением - то разницу в качестве видео (будь оно 1 ГБ или, скажем, 300 МБ) — вы просто не заметите! Чтобы увидеть разницу, вам нужно открыть видео на каком-нибудь большом экране ТВ.

Т.е., думаю, мой посыл ясен: если вы смотрите видео на экране с разрешением 1024x768 (или в таком "окошке" Windows, а в соседнем работаете. ) , а качество видео у вас 1920x1080 — это видео вполне можно сжать до более низкого разрешения и более оптимальным кодеком.

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

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

К примеру, максимальный битрейт при создании Blu-Ray диска составляет 35 mbps. Так вот, разницу между 30 и 35 — заметить не просто, а вот между 5 и 35 — бросится в глаза.

Примечание: сейчас популярно загружать видео на телефон/планшет, а затем, где-нибудь в дороге смотреть их. Так вот, такое видео не только можно, а даже рекомендуется сжать, и затем уже загрузить на ваше мобильное устройство.

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

О кодеках и контейнерах: что стоит пробовать сжать, а что нет

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

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

Примечание: кстати, следует различать кодек от контейнера. Например, формат файла AVI (это и есть контейнер), а сжать он может быть различными кодеками: Microsoft VC-1 или x.264 (например).

О Кодеках

x.264/ MPEG-4 AVC — наверное, самый распространенный кодек. Используется в большинстве видео- и фотокамерах, в которых снятые кадры хранятся на жестких дисках, картах памяти, и т.д. x.264, вероятно, становится самым популярным кодеком. Компания Adobe поддерживает его во Flash-роликах, x.264 может использоваться с картинками в HTML 5.

MJPEG (Motion JPEG) . Старый кодек для сжатия видео. На сегодняшний день устарел, мало используем.

MPEG-2 . Есть кодек MPEG-2 (известный как x.262), а также есть формат контейнера MPEG-2. MPEG-2 используется для видео на DVD-дисках и сигналов, передаваемым по эфирным телеканалам. В общем-то, обеспечивает оптимальное соотношение качество/размер файла. Поддерживается практически всеми плеерами.

Microsoft VC-1 . Microsoft VC-1 используется в качестве альтернативы технологии Adobe Flash, применяется в интернет-платформе Microsoft Silverlight. Обеспечивает среднее качество сжатия.

MPEG-1 . Устаревший кодек для сжатия видео (его заменил MPEG2). Раньше такое видео можно было встретить на CD-дисках. Сейчас встречается все реже, хотя, если вы любите поглядывать старые видео - вы наверняка с ним встречаетесь.

WMV . Есть Windows Media Video кодек, а есть одноименный контейнер. Обеспечивает очень высокое качество сжатия видео, при достаточно неплохой картинке. Очень популярен и распространен.

DivX — видеокодек, различные версии которого соответствуют стандартам MPEG-4 part 2, MPEG-4 part 10 (MPEG-4 AVC, H.264).

Xvid (ранее «XviD») — библиотека сжатия видео стандарта MPEG-4 Part 2. Кстати, методы сжатия, используемые в MPEG-4, запатентованы, так что использование Xvid в некоторых странах может быть нелегальным.

О контейнерах

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

AVI (или Audio Video Interleave) – один из самых популярных контейнеров от Microsoft. Чаще всего, видео на ПК встречается именно в этом формате. Кстати, многие почему-то не рекомендуют, современное видео сжимать в этот формат.

MP4 . Этот контейнерный формат разработан Motion Pictures Expert Group. Многие пользователи его называют MPEG-4. Обычно, видео в MP4-файлах закодировано кодеком x.264, а аудио – кодеком AAC. Иногда, могут попадаться и другие кодеки в этом контейнере.

VOB и BDAV MPEG-2 . Используются для упаковки видео на DVD и Blu-ray дисках. В Blu-ray дисков (.m2ts) могут содержаться видео, сжатые кодеками x.264 и VC-1.

ASF (Advanced Systems Format) – встречается в нескольких расширениях .asf, .wma и.wmv. Кстати, вероятнее всего, что файл в формате .wmv сжат кодеком WMV (Windows Media Video), но сам файл помещен в контейнерный файл ASF.

QuickTime . Детище компании Apple. Контейнер поддерживает множество кодеков для аудио и видео. Apple — сторонник x.264, поэтому, файлы QuickTime (форматы: .mov, .qt) чаще всего содержат видео, сжатое кодеком x.264.

Flash. Контейнерный формат Flash от Adobe, довольно популярный, кстати говоря.

Matroska (.mkv, .mk3d, .mka, .mks) — очень популярный и востребованный контейнер на сегодняшний день. Бесплатный, открытый - наверное, поэтому и получил широкое распространение. Многие высококачественные видео распространяются в этом контейнере.

DiVX . Очень распространенный и кодеки, и контейнер. Формат так же одноименный — ".divx". Кстати, кодек имеет "пиратское" происхождение, позволяющий получить высокое качество видео, при сильной компрессии.

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

Какой кодек и контейнер выбрать

Если вы хотите получить максимальное сжатие видео — логично выбрать кодек x.264, обеспечивающий отличную компрессию с хорошим качеством. Однако, имейте ввиду, что не всё оборудование (особенно, не самое новое) позволяет просматривать такие файлы. Если видео в очень высоком разрешении — то даже современные маломощные ПК не смогут его проиграть и показать без задержек и подвисаний. Кстати, если видео сжато не какой-либо вариацией кодека x.264 (например, оно в MPEG1, 2 или еще в каком-то формате) - его можно сжать без потери качество в более "компактный" кодек (скажем, в Divx) .
Если файлы планируете смотреть на DVD-плеерах, различных устройствах и пр. — рекомендуется выбрать кодек и контейнер MPEG2 — он поддерживается практически всем оборудованием;
Для различных фильмов, роликов, нарезок из готового видео - отлично подходит контейнер MP4, как удачный компромисс между степенью сжатия и качеством.

Сжатие видео по шагам: 2 способа

Первый способ

Сайт: http://video-converter.ru/ (прим.: входит в пакет "Видео Студия")

Отличная программа для сжатия и конвертирования различных видео: как фильмов, которые вы хотите уместить на диск или флешку, так и домашних видео, которые нужно сжать. Поддерживает все самые популярные форматы и кодеки, которые только встречаются: AVI, MP4, MPEG, MKV, DIVX, MP3 и т.д.

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

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

Покажу на примере, как конвертировать какой-нибудь ролик или фильм:

Вырезаем лишнее из него

Откроется окно, в котором вы сможете убавить/прибавить яркость, насыщенность и пр. Так же вам будут доступны вкладки:

- кадрирование (для изменения размера видео-разрешения, положения картинки, и изменения пропорции) ;

- текст (можно добавить тестовые поля на видео) ;

- улучшения (например, авто-контраст, понижение шума, устранение дефектов) ;

- поворот (поможет, если нужно повернуть видео на 90 градусов, часто бывает при съемки видео на телефон) ;

- скорость (можно увеличить/уменьшить скорость воспроизведения файла) .

В общем, задавайте настройки под себя!

Выбор контейнера и кодека

Выбор размера и разрешения

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

Второй способ

Movie Shrink & Burn (Ashampoo)

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

Movie Shrink & Burn позволяет записывать DVD/Blu-ray диски, записывать видео для различных устройств, загружать файлы в облако.

Поддерживаемые мобильные устройства: Apple, Sony, Android, Microsoft, видео можно сохранить в разнообразном качестве: 720p, SD (высокое, низкое).

Для каких устройств можно подготавливать видео

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

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

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