Как работает сжатие файлов?

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

Итак, как это работает?

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

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

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

Возьмите этот короткий фрагмент текста, например:

Алгоритм LZ77 будет смотреть на этот текст, понимать, что он повторяет «howtogeek» три раза, и изменять его следующим образом:

Затем, когда он захочет прочитать текст обратно, он заменит каждый экземпляр (h) на «howtogeek», возвращая нас к исходной фразе..

Мы называем сжатие как «без потерь» - данные, которые вы вводите, совпадают с данными, которые вы получаете. Ничего не потеряно.

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

Так что теперь, когда он доберется до (h), он вернется к «howtogeek» и прочитает это вместо.

Если вам интересно более подробное объяснение, это видео из Computerphile очень полезно.

Теперь это идеализированный пример. В действительности большая часть текста сжимается с помощью клавиш размером всего в несколько символов. Например, слово «the» будет сжато, даже если оно встречается в таких словах, как «там», «их» и «тогда». С повторяющимся текстом вы можете получить некоторые сумасшедшие коэффициенты сжатия. Возьмите этот текстовый файл со словом «howtogeek», повторенным 100 раз. Исходный текстовый файл имеет размер три килобайта. Однако при сжатии он занимает всего 158 байт. Это почти 95% сжатия.

Очевидно, это довольно экстремальный пример, так как мы повторяли одно и то же слово снова и снова. В общей практике вы, вероятно, получите сжатие на 30-40%, используя формат сжатия, такой как ZIP, для файла, который в основном состоит из текста..

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

Как работает сжатие изображений и видео?

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где вы можете иметь сжатие без потерь и данные не будут потеряны, с изображениями у нас есть то, что называется «сжатие с потерями», где вы теряете некоторые данные. И чем больше вы сжимаете, тем больше данных теряете.

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

Вот пример. Это снимок экрана, который я сделал, который не был сжат вообще.

Затем я сделал этот снимок экрана и несколько раз прогонял его через Photoshop, каждый раз экспортируя его в формате JPEG низкого качества. Вот результат.

Выглядит довольно плохо, верно?

Что ж, это только наихудший сценарий, каждый раз экспорт с качеством JPEG 0%. Для сравнения вот JPEG с 50% качеством, который почти неотличим от исходного изображения PNG, если вы не взорвете его и не посмотрите внимательно.

Размер PNG для этого изображения составлял 200 КБ, но этот JPEG-файл с качеством 50% составляет всего 28 КБ..

Так как же сэкономить так много места? Ну, алгоритм JPEG - это инженерный подвиг. Большинство изображений хранят список чисел, каждый из которых представляет один пиксель.

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

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

Это изображение ужасно. Но незначительное сжатие JPEG может оказать значительное влияние на размер файла, и это делает JPEG очень полезным для сжатия изображений на веб-сайтах. Большинство изображений, которые вы видите в сети, сжимаются, чтобы сэкономить время загрузки, особенно для мобильных пользователей с плохой передачей данных. Фактически, все изображения в How-To Geek были сжаты, чтобы ускорить загрузку страниц, и вы, вероятно, никогда не замечали.

Сжатие видео

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

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

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

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

Еще одна вещь, о которой следует помнить о видео, - это битрейт, то есть объем данных, допускаемый в каждую секунду. Например, если ваш битрейт составляет 200 кбит / с, ваше видео будет выглядеть очень плохо. Качество повышается с увеличением битрейта, но после пары мегабайт в секунду вы получаете убывающую отдачу.

Это увеличенный кадр, взятый из видео медузы. Один слева имеет скорость 3 Мбит / с, а другой справа - 100 Мбит / с..

30-кратное увеличение размера файла, но незначительное увеличение качества. Как правило, видео на YouTube работают со скоростью 2-10 Мбит / с в зависимости от вашего соединения, так как ничего более вероятно не будет замечено.

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

Сжатие звука

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

MP3 также использует битрейт, начиная от нижнего уровня 48 и 96 кбит / с (нижний предел) до 128 и 240 кбит / с (довольно неплохо) до 320 кбит / с (высококачественный звук), и вы, скорее всего, услышите разницу только с исключительно хорошими наушниками ( и уши).

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