Как сжатие файла работает?
Так, я понял сегодня, что я считаю сжатие файла само собой разумеющимся. Способность связать несколько файлов вместе в один, и это вышло меньшее, чем какой-либо из них, что-то, что я просто принимаю как факт, но как это на самом деле работает?
У меня есть ограниченные знания его, которые включают что-то, чтобы сделать с заменой всех дублирующихся записей с указателями, уменьшить тот путь, но кроме того я довольно невежествен!
Поскольку я всегда открыт для нового знания, поскольку я предполагаю, что большинство из нас вот, я думал, что спрошу. Так, SuperUser, как сжатие на самом деле работает?
2 ответа
Сжатие без потерь
Сжатие без потерь состоит в том, где никакие данные не потеряны. Все, что вводится, может быть получено отлично. Это работает хорошо на текстовые или двоичные файлы, где самая маленькая ошибка будет замечена.
Сжатие файла работает путем взятия файла и сканирования для шаблонов и перевода тех шаблонов во что-то еще, что занимает меньше места.
Например, "AAAAAAAA" мог быть превращен в "8 А".
Предоставленный это не то, как это работает точно, потому что затем у Вас есть проблема что, если "8 А" был в простом тексте. Вы распаковали бы файл, и это будет неправильно. Хорошим местом для запуска является или Википедия или Алгоритм сжатия данных LZW.
Существует, некоторые просто psuedo-кодируют для скопированного ниже:
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 Hrz и ниже 100 Hrz, наряду с другими различными вещами. В изображении (статичном), это удаляет различные вещи и объединяет эльфов вместе, наряду с отбрасыванием данных.
Сжатие с потерями является формой кодирования преобразования. Это составляет в среднем данные для сокращения полного размера. Например, блок 10 пикселей в изображении, все немного отличающиеся цвета могут быть объединены вместе с одним цветом и таким образом сжаты.
В сжатии видео часто инструкции будут помещены, чтобы только перерисовать пиксели, которые изменились начиная с последнего кадра или ключевого кадра.
Сжатие работает путем нахождения шаблонов в данных, затем замены этих шаблонов специальным предложением меньшие шаблоны. Распаковка является инверсией: найдите специальные шаблоны и замените их большими шаблонами, которые они представляют. Знание, какие шаблоны вероятны, важно; например, шаблоны, найденные в тексте, могут очень отличаться, чем найденные в изображениях. Некоторые методы сжатия с потерями; они не гарантируют, что расширение восстановит вход точно. Это обычно хорошо для аналоговых данных, таких как музыка и изображения, если потеря является достаточно маленькой. Но данные, такие как текст должны быть сжаты с методами без потерь.
Важно понять, что невозможно сжаться, без потери, случайных данных даже единственным битом. Рассмотрите файл с битами N двоичных данных. Существуют 2^N возможные файлы. Если Вы сжимаете какой-либо из этих файлов единственным битом, таким образом, сжатый файл является N-1 битами в размере, существует только 2^ (N-1) возможные сжатые представления. Другими словами, каждый возможный сжатый файл должен представить больше чем один возможный несжатый файл. Без уникального сжатого представления алгоритм распаковки не может гарантировать распаковку без потерь.