Методы сжатия данных: алгоритмы и инструменты

Методы сжатия данных. Показываем, какие есть алгоритмы и инструменты. Рассматриваем реальные примеры и кейсы ✔ Tproger Наверняка вы сталкивались с zip–архивами, сохраняли фото в jpeg или смотрели видео в 144p — всё это примеры сжатых данных.

Когда мы говорим о сжатии (компрессии), то имеем в виду уменьшение исходного размера без потери содержимого. Так можно хранить больше информации, быстрее её передавать и считывать. Методы сжатия данных принято делить на 2 категории: с потерей и без потери. Рассмотрим их подробнее. При сжатии данных с потерями мы безвозвратно удаляем часть информации. Но делаем это так, чтобы не потерять общую суть. Например, надо сжать картинку для сайта, чтобы он быстрее прогружался. Ниже два варианта одного изображения. Один исходник, второй сжатый. Как думаете — какой где? По идее исходник должен уступать оригиналу в визуальном плане, однако разницы между этими изображениями практически не видно. Оригинал — первое изображение в формате png. Второе — сжатый вариант в формате jpeg. Казалось бы, вариант 2 должен был потерять качество, и это произошло. При компрессии были удалены некоторые похожие оттенки цветов и лишние детали, а размер файла уменьшился с 2.38МБ до 145 КБ. При этом визуально он все еще выглядит неплохо. То же самое происходит и при работе с аудио и видео. В файле могут содержаться звуки, которые не воспринимает человеческое ухо, статичные элементы, которые не изменяются от кадра к кадру. Всё это излишки, которые можно отбросить без потери смысла. При методах сжатия без потерь мы не удаляем лишние данные, а стараемся упаковать их более компактно. Допустим, нам нужно составить список покупок. Мы можем записать его так: Однако некоторые продукты повторяются здесь несколько раз, поэтому эту запись можно сделать более компактной вот так: Давайте рассмотрим три наиболее распространенных метода сжатия без потерь. Метод Хаффмана позволяет нам компактно закодировать данные при помощи манипуляций с частотой объектов и выстраивания дерева. А еще его включают в себя многие другие алгоритмы и форматы сжатия. Рассмотрим пошагово кодирование Хаффмана на примере сжатия слова: «compression». Определяем, сколько раз тот или иной символ встречался в тексте. Записываем символы в таблицу в порядке убывания. Под ними указываем частоту. Записываем символы как листья дерева. Их частотность будет весом. Находим два крайних правых листа и строим над ними новый. Записываем в него символы и сумму их частот. Мы создали лист «in» с весом 2. Формируем листы дальше. Теперь мы построили лист «ein» с весом 3 из «in» и «e». Продолжаем до тех пор, пока не создадим последний лист. Мы закончили строить дерево. Теперь можно приступить к кодированию знаков. Вершина «oscmprein» является корнем нашего дерева, так как обладает наибольшим весом — 11. Каждая линия означает один бит. Для линий справа это единица, слева — ноль. Теперь при помощи битов линий мы кодируем каждый символ. Для этого необходимо представить путь от корня до нужного знака. Сочетание битов линий на пути будет нашим кодом. Например, между «o» и корнем «oscmprein» есть только одно ребро, которое равно нулю. Следовательно, «o» это 0. От корня до «s» ведут две линии: один и ноль. Значит, код будет 10. И так до узла «n», код которого 11111111.

Источник: tproger.ru — tproger.ru/articles/metody-szhatiya-dannyh—algoritmy-i-instrumenty-251908