Вопрос: Почему zipping zipped-файл не уменьшает его размер?


Основываясь на идее, что zipped-файл является новым двоичным файлом, почему я не могу уменьшить размер Zip, заново его заново и снова - вплоть до очень маленького результирующего файла?


4
2018-01-06 19:40


Источник


Связанный: Могу ли я сжать RAR-файл еще раз, чтобы уменьшить его размер? - slhck


Ответы:


Основываясь на идее, что zipped-файл является новым бинарным файлом, почему я не могу уменьшить его размер, заново его заново и последовательно до очень маленького файла?

Потому что сжатие работает на основе поиска шаблонов и сокращения данных, которые похожи.

Например, RLE (Кодирование по длине) - это простой метод сжатия, при котором данные проверяются, и выполняется списание подобных данных:

AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA

becomes

3ABC3EJ2F10YOO4A5G3A

Как вы можете видеть, заменяя повторяющиеся данные только данными и количеством раз сколько это происходит, вы можете уменьшить этот конкретный пример от 35 байт до 20 байт. Это не огромный но он все еще на 42% меньше. Более того, это небольшой, надуманный пример; более крупные, реальные примеры могут иметь еще лучшее сжатие. (The OO остался один, заменив его 2O ничего не спасет.)

Текстовые файлы часто сжимаются очень хорошо, потому что у них, как правило, много шаблонов, которые можно сжать. Например, слово  очень распространен на английском языке, поэтому вы можете удалить каждый экземпляр слова с помощью идентификатора, который является только одним байтом (или даже меньше). Вы также можете сжимать больше с помощью части слов, похожих на cAKE, bAKE, shAKE, undertAKE, и так далее.

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

Посмотрите на сжатый пример RLE. Как вы можете сжать это дальше? Для сжимания нет одинаковых данных. На самом деле, часто, когда вы пытаетесь сжать файл, который уже сжат, вы можете больше файл. Например, если вы заставили приведенный выше пример перекодировать, вы можете получить что-то вроде этого:

131A1B1C131E1J121F11101Y2O141A151G131A

Теперь данные сжатия (отсчеты) сами обрабатываются как данные, поэтому вы получаете более крупный файл, чем вы начали.

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

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


6
2018-01-06 20:01





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

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

  • Предположим, что каждый файл представлен как строка бит некоторой произвольной длины.
  • Предположим, что есть алгоритм сжатия, который преобразует каждый файл в выходной файл, который больше, чем исходный файл, и что по меньшей мере один файл будет сжат в выходной файл, который короче исходного файла.
  • Пусть M - наименьшее число, такое, что существует файл F с длиной M бит, который сжимается до более короткого. Пусть N - длина (в битах) сжатой версии F.
  • Поскольку N <M, каждый файл длины N сохраняет свой размер во время сжатия. Есть 2N таких файлов. Вместе с F это составляет 2N+1 файлов, которые все сжимают в один из 2N файлы длиной N.
  • Но 2N меньше 2N+1, поэтому по принципу голубинки должен быть некоторый файл длины N, который одновременно является выходом функции сжатия на двух разных входах. Этот файл нельзя надежно декомпрессировать (какой из двух оригиналов должен дать?), Что противоречит предположению, что алгоритм был без потерь.
  • Поэтому мы должны заключить, что наша первоначальная гипотеза (что функция сжатия не делает файл более длинной) обязательно неверна.

https://en.wikipedia.org/wiki/Lossless_compression#Limitations


2
2018-06-24 16:00





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

Давайте представим простой файл, который содержит это.

AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC

Если мы сжимаем его, мы можем сказать, что это 20 A, новая линия, а затем 20 B, новая линия, а затем 20 C. Или что-то вроде 20xA\n20xB\n20xC\n, Как только мы сделали первое сжатие, нет новых шаблонов для сжатия. Каждый бит, если информация уникальна.


1
2018-01-06 20:00





Я бы сказал, вы не можете сжимать произвольный бинарные файлы в значительной степени - подумайте о изображениях JPEG, видео x264 и т. д. Тем более, что вы хотите реконструировать ваш исходный файл в точку (то есть поэтапно), вам необходимо сжатие без потерь,1

Причина этого ограниченного сжатия указана в этом Статья в Википедии об Энтропии  который количественно оценивает ожидаемое значение информации, содержащейся в сообщении:

Энтропия эффективно ограничивает производительность самых сильных без потерь   (или почти без потерь), что может быть реализовано в   теории, используя типичный набор или на практике с использованием Хаффмана,   Lempel-Ziv или арифметическое кодирование. (...)


1Очень сильное «сжатие» изображений JPEG возможно только потому, что некоторая информация отбрасывается (таким образом, что человеческий глаз не может распознать его с первого взгляда; сжатие с потерями).


1
2018-01-06 20:00



I'd say can't compress any binary file Это неверно, вы обычно можете сжимать exectuables совсем немного, следовательно UPX, - Synetech
@Synetech: Вы абсолютно правы, это была языковая ловушка. Я не имел в виду Любые, но произвольном файл (по значению случайных данных). - mpy
О, хорошо, я вижу. Да, файл, содержащий случайные байты, просто ужасен для сжатия. - Synetech