Технология сжатия везде в жизни, сохраненная на данных жесткого диска, передача телевизионных сигналов, передаваемых страницами, потоковых носителей, видеоигр ...... Современные вычисления вряд ли важной областью без использования технологии сжатия.
Так что же, в конце концов, представляет собой технология сжатия?
Использовали ли вы компьютерное программное обеспечение для сжатия в течение многих лет или никогда не задумывались об этом, в этой статье мы попытаемся объяснить, что именно происходит с данными в файле, когда вы сжимаете его или передаете видео. Мы будем искать ответы на эти важные вопросы и, возможно, попутно поднимем некоторые новые.
- Что значит сжать сжатый объект?
- Как сделать целевой объект меньше исходного?
- Как реализовать технологию сжатия конкретно
Давайте ответим на них один за другим!
Базовые знания
Перед изучением методов сжатия и цифровой информации, вот простое для понимания введение в методы сжатия. Давайте посмотрим на английские буквы ниже:
Взгляните на символы, которые мы используем для представления этого слова (Дерево), которые в сумме дают 4:
Это выглядит нормально. Что произойдет, если мы используем китайские иероглифы?
МОЙ БОГ! Был использован только один символ! Изменили ли мы его значение и какое-либо сообщение? нисколько. Однако мы уменьшили веб-пространство на 75%, чтобы выразить значение слова «дерево». Итак, что именно мы сделали?
В этом нет ничего волшебного — мы просто по-другому вкладываем смысл. Мы выбрали другой и более эффективный способ подачи информации. Спойлер: Далее самая важная часть этой статьи, пожалуйста, прочитайте ее внимательно.
Так что, если это изображение на уровне пикселей?
Вы можете быть удивлены, как приведенный выше пример может быть применен к точным цифровым данным изображения? Давайте рассмотрим категорию данных, ставшую очень популярной в последнее время, — картинки. А пока давайте начнем с простых изображений на уровне пикселей, вместо того чтобы пытаться сжать изображение высокого разрешения из Instagram или другое столь же сложное изображение прямо из коробки.
Не очень красиво правда? Потому что это моя собственная картина. Выше показана сетка 10 * 10, каждый цвет может быть «B», «Y» и «G» представлен одним символом.
Как мы можем представить приведенное выше изображение в цифровом виде? Файл, хранящий это изображение в исходном виде, может содержать следующее:
Все, что мы сделали, это написали символ, представляющий его цвет, для каждого пикселя слева направо и сверху вниз. Как и следовало ожидать, всего будет 100 символов. Предположим, что эти 100 символов займут 100 байт на жестком диске. Этот метод хранения определяет разумный верхний предел размера файла хранилища. Любой другой метод хранения, если его размер файла больше, чем указанный выше метод, не имеет смысла или пытается сохранить информацию, отличную от данных изображения (например, метаданные или другие данные). Думаю, вы должны согласиться со мной в этой точке зрения.
Прежде чем смотреть вниз, включите мозг. Если бы я попросил вас представить это изображение менее чем в 100 символов, что бы вы сделали? Выпей чаю, подумай хорошенько, я жду тебя.
Думаете как-нибудь? Отлично, я тоже об одном подумал.
Я собираюсь назвать свой метод какАлгоритм сжатия длин серий (RLE). Шучу, не я придумал этот метод и не назвал его. Это была основная техника сжатия, по крайней мере, с шестидесятых годов. Бьюсь об заклад, некоторые из вас только что придумали этот метод.
Мы применили алгоритм сжатия длин серий к изображению выше. Выше мы написали множество строк символов одного цвета. Давайте начнем с тех символов 'B'. Так можем ли мы сжать эти повторяющиеся символы?
конечно может! Отказаться следующим образом:
Вместо:
Это похоже на пьесу. Сократив эту длинную строку одинаковых символов, мы сократили 17 символов до 3. Кстати, назовем эти повторяющиеся строкиruns. такалгоритм сжатия длин серийЧерез нотуrunsДлина данных, а не запись каждого символа, сжимает кодировку данных. В этом методе сжатия нет потери информации. Программа, способная анализировать предыдущий файл, с небольшой модификацией сможет анализировать наш новый формат файла. Изображения, проанализированные двумя, должны быть одинаковыми.
В приведенной ниже живой демонстрации показано необработанное изображение и его 2 кодировки для хранения: исходная версия и версия, закодированная со сжатием длины цикла.
Нажав на любой пиксель, вы можете изменить его цвет, и соответственно изменятся сохраненные символы под ним.
Примечание редактора: здесь есть демонстрация в оригинальном английском тексте. Эта статья не может быть воспроизведена. Пожалуйста, проверьте ее на https://unwttng.com/compression-decompressed.
Продолжая изменять цвета пикселей исходного изображения, вы обнаружите, что соотношение, которое мы можем сжать, зависит от самого изображения. Если все изображение имеет только один цвет или цветовой континуум очень длинный, мы можем получить очень маленькие выходные данные. Минимальный размер хранилища, который можно получить с помощью алгоритма сжатия длин серий, составляет 4 байта:
Конечно, этот алгоритм также будет работать очень плохо в некоторых сценариях. На самом деле файлы, сжатые с помощью этого алгоритма, могут быть больше, чем исходное попиксельное представление. Вы обнаружите, что когда ему нужно представить «1B» или «1G», он использует 2 символа. Что произойдет, если в вашем пиксельном изображении длина продолжения каждого цвета будет равна всего 1 ?
Удивляться.
Пора изучить терминологию.
Степень сжатия
Как мы можем измерить, насколько наш алгоритм сжатия действительно сжимает данные? Как вы уже догадались — вычислить соотношение размеров до и после сжатия данных.
Например, если мы используем алгоритм для сжатия 100-байтового пиксельного изображения до 42 байт, мы вычисляем коэффициент сжатия (100/42) ≈ 2,38. В лучшем случае это изображения только с одним цветом, и этот алгоритм сжимает до (100/4) = 25! Однако, когда алгоритм работает с изображением с длиной серии всего 1 для каждого цвета, коэффициент сжатия составляет всего (100/200) = 0,5. Совет: степень сжатия меньше 1 просто ужасна.
Мы видим, что степень сжатия этого базового алгоритма RLE очень чувствительна к структуре входных данных. Это явление характерно для таких простых алгоритмов. Алгоритм делает несколько предположений о структуре данных.Чтобы алгоритм выдавал идеальные результаты, в исходных входных данных должны повторяться соседние одинаковые байты. Более разумная реализация алгоритма RLE может попытаться сжать данные, используя повторяющиеся подстроки.
Даже если я опишу эту картинку прямо английским текстом, степень сжатия будет больше 2! Используя этот метод, данные можно сжать и сохранить в удобном, компактном формате файла, что является небольшим шагом с первой попытки.
Насколько малы данные могут быть сжаты?
Это большой, широкий вопрос. Конечно, считается, что для любых входных данных разумно разработанный алгоритм сжатия должен иметь возможность хотя бы немного сжимать данные (немного здесь, как в просторечии, так и в академическом).
К сожалению, все не так просто. Предположим, у нас есть алгоритм A, который для любых входных данных способен сохранять коэффициент сжатия строго больше 1. Для некоторых входных данных коэффициент сжатия может быть равен 2,5, для других коэффициент сжатия может быть равен 1,000000002.
Если такой алгоритм существует, мы можем вызывать его итеративно до бесконечности. Для некоторых входных данных мы вычисляем A(A(A(data))), непрерывно вызывая A() для каждого вывода. Каждый раз, когда мы делаем вызов, размер данных хотя бы немного сжимается. Нетрудно заметить, что в конце концов мы можем сжать данные до 1 байта или даже до 0 байт?
Это не кажется реалистичным. это правда. Нам даже не нужно использовать рекурсию, чтобы доказать работоспособность этого алгоритма, просто представьте себе такую ситуацию: есть 9 разных файлов, и нет возможности сжать все 9 файлов до 3 слов без потери данных Festival.
3 байта могут представлять только 8 различных данных: 000, 001, 010, 100, 011, 101, 110, 111. Даже если у нас есть очень мощный алгоритм сжатия, который может сжать первые 8 файлов в первые 8-байтовые представления, 9-й файл может быть сжат только в одно из них. Для этого алгоритма более 8 фрагментов несжатых данных не могут быть представлены более чем 3 разными байтами.
Вот важный принцип:Для сжатия общих данных скорость сжатия любого алгоритма имеет строгий предел. Вы можете продолжать сжимать данные с помощью алгоритма до тех пор, пока вы не сможете сжимать их меньше, а затем попробовать другой алгоритм. Этот подход может сжимать данные меньше (на самом деле, многие онлайн-программы делают это), но в конечном итоге вы получите данные, которые больше никогда не сможете сжать. Фактически, ваши повторные вызовы разных алгоритмов в конечном итоге становятся еще одним алгоритмом сжатия. Это правило действует до сих пор.
сложность Короткова
Вы можете быть еще более разочарованы, увидев ниже. Для размера степени сжатия существует не только теоретический предел алгоритма — большое влияние на него будет иметь и сложность самих данных
Давайте посмотрим на следующие 2 строки:
а также:
Оба имеют одинаковую длину, однако, как вы можете легко видеть, последний значительно сложнее. Чтобы быть более конкретным, используя алгоритм сжатия RLE, мы можем сжать первую строку максимум до 3 символов («24a»).
сложность Короткова(советский математикAndrey Nikolaevich KolmogorovВеликое изобретение ) очень хорошо объясняет вышесказанное. Конечно, есть много способов измерить вещь, и сложность Короткова — относительно хорошая мера.Коротковская сложность данных относится к кратчайшей длине строки, которая может быть описана компьютерной программой..
Очевидно, что для сложности Короткова верхней границей длины любой строки S является она сама. Приведенное выше утверждение в определенной степени упрощает алгоритм, ведь сложность данных по Короткову нужно прибавить к длине всей программы, включая интерпретатор или компилируемый код. Но для целей этой статьи это не обязательно. Просто подумайте об этом как о самой короткой длине этих данных, которые вы можете сгенерировать.
Сложность Короткова не очень чувствительна к тому, какой язык программирования вы выберете. Выбор языка программирования влияет только на постоянный коэффициент сложности. Важно следующее предложение:Независимо от того, какой язык вы выберете для описания данных, результирующая вариация длины ограничена.. Для представления некоторых данных требуется больше места, чем миллион зеленых пикселей, и их нельзя уменьшить.
данные потеряны
Но не теряйте надежды. То, что мы обсуждали раньшесжатие без потерь. средства сжатия без потерь,Через сжатые данные исходные данные до сжатия могут быть полностью восстановлены. То есть, если C — наш алгоритм сжатия, а D — соответствующий алгоритм распаковки, D(C(x)) = x всегда выполняется для любых входных данных x.
Сжатие без потерь очень полезно! При сжатии некоторых текстовых данных, таких как литература или сообщения в блогах, налоговые архивы, пиксельные изображения с низким разрешением и т. д., вы определенно хотите использовать сжатие без потерь. Для этих данных важно обеспечить точность данных и порядок каждого символа.
Но есть и другие варианты. Сжатие с потерями означает, что нет гарантии, что сжатые данные после распаковки точно такие же, как данные до сжатия. Этот алгоритм сжатия очень распространен.
Широко используется сжатие с потерями. Человеческие чувства более терпимы к незначительным ошибкам или недостаткам. Потеря данных в основном проявляется при сжатии файлов изображений, аудио (или видео).
Нужен пример? Взгляните на 2 изображения Обамы ниже.
Второе изображение является результатом сохранения первого изображения в формате JPEG, сжатия с потерями, при котором теряется много данных. Размер второго изображения составляет около 22 килобайт, а степень сжатия по сравнению с исходным изображением составляет около 15. Такая большая степень сжатия не означает, что потеря данных будет серьезной.
Вы видите разницу между этими двумя картинками? Может быть, немного. Если вы подошли как можно ближе к экрану, прищурьтесь и поверните голову, чтобы посмотреть на картинку. Затем вы смотрите на детали его волос, считаете волосы один за другим, вы найдете какое-то размытие там, где нет волос. Дело не в том, является ли второй образ идеальной копией, а в том, достаточно ли он хорош для использования. Когда вы передаете данные через Интернет, сжатие в пятнадцать раз более ценно, чем изображение PNG без потерь.
Но это не значит, что он так хорош в любой ситуации. JPEG должен потерять много данных, чтобы достичь такого сжатия, и хотя он пытается избежать потери слишком большого количества данных, вы можете попытаться изучить его пределы. В приведенной ниже демонстрации в реальном времени вы можете увидеть, насколько может быть снижен нижний предел качества изображения в формате JPEG. При этом обращайте внимание на качество картинки, пока четкость картинки не стала невыносимой. Как я уже говорил, зрительная толерантность человека очень высока.
Примечание редактора: в оригинальном английском тексте есть демонстрация, эта статья не может быть воспроизведена, проверьте ее на https://unwttng.com/compression-decompressed.
Сервисы потокового видео, такие как Netflix и YouTube, а также сервисы потокового аудио на Spotify и Soundcloud используют сжатие с потерями. Буферизация или задержка невыносимы для пользователя, поэтому эти сервисы стараются максимально сжимать данные, сохраняя при этом качество звука и видео. Вы часто будете видеть динамическое сжатие данных, видео сначала будет размытым, и когда он обнаружит, что скорость вашей сети может принять более низкую степень сжатия, четкость видео соответственно увеличится.
Видите анимацию ниже с сайта Giphy? Здесь также применяется динамическое сжатие данных. Посмотрите, как они справляются с загрузкой gif в медленном интернете (да, я сделал gif этого процесса загрузки на сайте Giphy и встроил его, видите, что не так??):
Это выглядит странно, верно? Во-первых, они загрузили первое изображение GIF в низком разрешении. Затем, когда были переданы большие данные, появилось движущееся изображение. Но не совсем, всего несколько кадров. Затем передаются все новые и новые кадры, пока, наконец, вся анимация не загрузится полностью.
Это современная технология потокового сжатия: стратегии гибридного сжатия почти полностью разработаны для доставки плавного контента пользователю как можно меньшим количеством байтов (меньший размер, более короткая продолжительность). Методы сжатия файлов без потерь, такие как упомянутый выше RLE, также имеют место, и он остается основным модулем многих лучших инструментов сжатия файлов для настольных компьютеров. Однако благодаря сжатию с потерями вы можете плавно смотреть «Игру престолов» на телевизоре.
Сжатие данных повсюду
Мы начнем эту статью о технологии сжатия здесь, но это только вершина айсберга.
Мы изучили основные идеи техник сжатия и вывели из этих техник важную философскую истину:
Изображения, текст, видео, музыка — нет единственно правильного представления любых данных. Разница заключается просто в том, сколько допустимых способов представления данных.
Технология сжатия постоянно ищет более эффективные способы хранения ваших данных, самый мощный алгоритм сжатия, для любых данных она может найти эффективный способ их сжатия.
Спасибо за чтение, если вы согласны с демонстрационными примерами в реальном времени, которые я сделал в статье, не стесняйтесь поделиться ими со своими друзьями.
2 лайка1 Избранное1 Комментарий