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

Question

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

У меня есть ограниченные знания об этом, что включает в себя что-то, что можно заменить заменой всех повторяющихся записей указателями, чтобы сократить этот путь, но кроме этого, я совершенно не понимаю!

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

Answer 1

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

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

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

Например, "AAAAAAAA" можно превратить в "8A".

Конечно, это не так, потому что тогда у вас есть проблема, что если "8А" было в открытом тексте. Вы распакуете файл, и это будет неправильно. Хорошее место для начала - Википедия или Алгоритм сжатия данных LZW.

Ниже приведен простой псевдо-код для этого:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

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

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

"Потерянное" сжатие

Вышеуказанное в основном относится к сжатию без потерь. Другие типы сжатия, используемые в видео / аудио приложениях, такие как MP3, JPG и h.264, являются примерами сжатия с потерями.

Сжатие с потерями работает путем отбрасывания данных, которые с наименьшей вероятностью будут замечены. В аудио это звуки около 30 000 Гц и ниже 100 Гц, наряду с другими различными вещами. В изображении (статическом) он удаляет различные объекты и объединяет пиксели вместе, а также отбрасывает данные.

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

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

Answer 2

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

Важно понимать, что невозможно без потерь сжать случайные данные даже одним битом. Рассмотрим файл с N битами двоичных данных. Есть 2 ^ N возможных файлов. Если вы сжимаете какой-либо из этих файлов одним битом, поэтому размер сжатого файла составляет N-1 бит, существует только 2 ^(N-1) возможных сжатых представления. Другими словами, каждый возможный сжатый файл должен представлять более одного возможного несжатого файла. Без уникального сжатого представления алгоритм распаковки не может гарантировать распаковку без потерь.