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

[Carder]

Вам нужно сжать ваши файлы?
Если вы загружаете много программ и файлов из Интернета, вы, вероятно, уже сталкивались с файлами ZIP. Эта система сжатия - очень удобное изобретение, особенно для пользователей Интернета, поскольку она позволяет уменьшить общее количество бит и байтов в файле, чтобы его можно было передавать быстрее по более медленным Интернет-соединениям или занимать меньше места на диске. После загрузки файла ваш компьютер с помощью такой программы, как WinZip или Stuffit, вернет файл к исходному размеру. Если все работает правильно, расширенный файл идентичен исходному файлу до его сжатия.
На первый взгляд это кажется очень загадочным. Как можно уменьшить количество битов и байтов, а затем добавить эти точные биты и байты позже? Как оказалось, основная идея этого процесса довольно проста. В этой статье мы рассмотрим этот простой метод, когда мы проведем очень маленький файл через основной процесс сжатия.
Большинство типов компьютерных файлов достаточно избыточны - в них снова и снова перечисляется одна и та же информация. Программы сжатия файлов просто избавляются от избыточности. Вместо того, чтобы перечислять часть информации снова и снова, программа сжатия файлов перечисляет эту информацию один раз, а затем обращается к ней всякий раз, когда она появляется в исходной программе.
В качестве примера давайте посмотрим на тип информации, с которым все мы знакомы: слова.
В инаугурационной речи Джона Ф. Кеннеди в 1961 году он произнес знаменитую фразу:
«Не спрашивайте, что ваша страна может сделать для вас - спрашивайте, что вы можете сделать для своей страны».
Цитата состоит из 17 слов, состоящих из 61 буквы, 16 пробелов, одного тире и одной точки. Если каждая буква, пробел или знак препинания занимают одну единицу памяти, мы получаем общий размер файла 79 единиц. Чтобы уменьшить размер файла, нам нужно искать дубликаты.

Сразу замечаем, что:

• "спросить" появляется два раза
• "что" появляется два раза
• "ваш" появляется два раза
• "страна" появляется дважды
• "банка" появляется два раза
• "делать" появляется два раза
• "для" появляется два раза
• "ты" появляется два раза

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

Содержание

1. Избыточность и алгоритмы
2. Поиск паттернов
3. Сжатие с потерями и без потерь

Избыточность и алгоритмы​

Большинство программ сжатия используют вариант алгоритма на основе адаптивного словаря LZ для сжатия файлов. «LZ» относится к Лемпелю и Зиву , создателям алгоритма, а «словарь» относится к методу каталогизации фрагментов данных.
Система размещения словарей может быть разной, но она может быть такой же простой, как нумерованный список. Когда мы просматриваем известные слова Кеннеди, мы выбираем повторяющиеся слова и помещаем их в пронумерованный указатель. Затем мы просто пишем число вместо того, чтобы писать все слово.

Итак, если это наш словарь:

1. Просить
2. Какие
3. Ваш
4. Страна
5. Может
6. За
7. Ты

Наше предложение теперь гласит: «1, а не 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4».
Если бы вы знали систему, вы могли бы легко восстановить исходную фразу, используя только этот словарь и числовой шаблон. Это то, что делает программа расширения на вашем компьютере, когда расширяет загруженный файл. Вы также могли столкнуться со сжатыми файлами, которые открываются сами собой. Чтобы создать такой файл, программист включает простую программу расширения со сжатым файлом. Он автоматически восстанавливает исходный файл после его загрузки.
Но сколько места мы на самом деле сэкономили с помощью этой системы? «1 не 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4» определенно короче, чем «Не спрашивайте, что ваша страна может сделать для вас; спрашивайте, что вы можете сделать для своей страны»; но имейте в виду, что нам нужно сохранить сам словарь вместе с файлом.
В реальной схеме сжатия определение различных требований к файлам было бы довольно сложным; но для наших целей давайте вернемся к идее, что каждый символ и каждое место занимает одну единицу памяти. Мы уже видели, что полная фраза занимает 79 единиц. Наше сжатое предложение (включая пробелы) занимает 37 единиц, а словарь (слова и числа) также занимает 37 единиц. Это дает нам размер файла 74, поэтому мы не очень сильно уменьшили размер файла.
Но это всего лишь одно предложение! Вы можете представить, что если бы программа сжатия проработала остальную часть речи Кеннеди, она обнаружила бы, что эти и другие слова повторяются много раз. И, как мы увидим в следующем разделе, он также переписывает словарь, чтобы получить наиболее эффективную организацию.

Поиск паттернов​

В нашем предыдущем примере мы выбрали все повторяющиеся слова и поместили их в словарь. Для нас это наиболее очевидный способ составления словаря. Но программа сжатия видит это совершенно иначе: в ней нет концепции отдельных слов - она только ищет шаблоны. А чтобы максимально уменьшить размер файла, он тщательно выбирает, какие шаблоны включить в словарь.
Если подойти к фразе с этой точки зрения, мы получим совершенно другой словарь.
Если программа сжатия просканирует фразу Кеннеди, первая повторяемость, с которой она столкнется, будет состоять всего из пары букв. В словах «не спрашивайте, что у вас» есть повторяющийся узор из буквы «т», за которой следует пробел - в «не» и «что». Если программа сжатия записала это в словарь, она могла бы записывать «1» каждый раз, когда за буквой «t» следует пробел. Но в этой короткой фразе этого шаблона недостаточно, чтобы его можно было использовать, поэтому программа в конечном итоге его перезапишет.
Следующее, что программа может заметить, - это «ou», которое встречается как в «your», так и в «country». Если бы это был более длинный документ, запись этого шаблона в словарь могла бы сэкономить много места - «ou» - довольно распространенная комбинация в английском языке. Но по мере того, как программа сжатия прорабатывала это предложение, она быстро нашла лучший выбор для словарной статьи: не только повторяется «ou», но и повторяются целые слова «ваша» и «страна», и они фактически повторяются. вместе, как словосочетание «твоя страна». В этом случае программа заменит словарную статью для «ou» записью «ваша страна».
Фраза «могу сделать для» также повторяется, один раз за ней следует «ваш» и один раз за ней следует «вы», что дает нам повторяющийся шаблон «могу сделать для вас». Это позволяет нам писать 15 символов (включая пробелы) с одним числовым значением, в то время как «ваша страна» позволяет нам записывать только 13 символов (с пробелами) с одним числовым значением, поэтому программа перезапишет запись «ваша страна» как просто «r страна", а затем напишите отдельную запись для" могу сделать для вас". Программа действует таким образом, собирая все повторяющиеся биты информации и затем вычисляя, какие шаблоны следует записать в словарь. Эта способность переписывать словарь является «адаптивной» частью алгоритма, основанного на адаптивном словаре LZ .Data-Compression.com.
Независимо от того, какой конкретный метод вы используете, эта система глубокого поиска позволяет сжимать файл гораздо эффективнее, чем если бы вы просто выбирали слова.

Используя шаблоны, которые мы выбрали выше, и добавив «__» для пробелов, мы получили более крупный словарь:

1. Просить__
2. Какие__
3. Ты
4. r__страна
5. __могу__сделать__для__тебя

И это меньшее предложение: "1not__2345 __ - __ 12354"
Предложение теперь занимает 18 единиц памяти, а наш словарь занимает 41 единицу. Таким образом, мы сократили общий размер файла с 79 до 59 единиц! Это всего лишь один способ сжатия фразы, и не обязательно самый эффективный. (Посмотрите, сможете ли вы найти лучший способ!)
Так насколько хороша эта система? Коэффициент уменьшения файла зависит от ряда факторов, включая тип файла, размер файла и схему сжатия.
В большинстве языков мира определенные буквы и слова часто встречаются вместе в одном образце. Из-за этой высокой степени избыточности текстовые файлы очень хорошо сжимаются. Уменьшение на 50 процентов или более типично для текстового файла хорошего размера. Большинство языков программирования также очень избыточны, потому что они используют относительно небольшой набор команд, которые часто идут вместе в заданном шаблоне. Файлы, содержащие много уникальной информации, например графику или файлы MP3, не могут быть сильно сжаты с помощью этой системы, потому что они не повторяют многие шаблоны (подробнее об этом в следующем разделе).
Если в файле много повторяющихся шаблонов, скорость уменьшения обычно увеличивается с размером файла. Вы можете убедиться в этом, просто взглянув на наш пример - если бы у нас было больше речи Кеннеди, мы могли бы чаще обращаться к шаблонам в нашем словаре и таким образом получать больше от файлового пространства каждой записи. Кроме того, в ходе более продолжительной работы могут появиться более распространенные шаблоны, что позволит нам создать более эффективный словарь.
Эта эффективность также зависит от конкретного алгоритма, используемого программой сжатия. Некоторые программы особенно подходят для улавливания шаблонов в файлах определенных типов и поэтому могут сжимать их более лаконично. У других есть словари в словарях, которые могут эффективно сжимать файлы большего размера, но не файлы меньшего размера. Хотя все программы сжатия подобного типа работают с одной и той же основной идеей, на самом деле существует множество вариантов выполнения. Программисты всегда пытаются построить лучшую систему.

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

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