Я думал о сжатии, и, похоже, для сжатия, который может быть применен к нему, должен быть какой-то предел, иначе он будет одним байтом.
Итак, мой вопрос: сколько раз я могу сжать файл раньше:
Являются ли эти две точки одинаковыми или разными?
Где появляется точка убывающих результатов?
Как можно найти эти точки?
Я не говорю о каком-либо конкретном алгоритме или конкретном файле, как правило,.
Для сжатия без потерь единственный способ узнать, сколько раз вы можете получить, повторно сжимая файл, попробуйте. Это будет зависеть от алгоритма сжатия и файла, который вы сжимаете.
Два файла никогда не могут сжиматься до одного и того же выхода, поэтому вы не можете перейти к одному байту. Как один байт может представлять все файлы, которые вы могли бы распаковать?
Причина, по которой второе сжатие иногда срабатывает, заключается в том, что алгоритм сжатия не может делать всезначительное идеальное сжатие. Там есть компромисс между работой, которую он должен делать, и временем, которое требуется для этого. Ваш файл изменяется со всех данных на комбинацию данных о ваших данных и самих данных.
Пример
В качестве примера возьмем кодировку длины пробега (возможно, самое простое сжатие).
04 04 04 04 43 43 43 43 51 52 11 байт
Эта серия байтов может быть сжата как:
[4] 04 [4] 43 [-2] 51 52 7 байтов (я помещаю метаданные в скобки)
Если положительное число в скобках - это число повторений, а отрицательное число в скобках - это команда для извлечения следующих -n символов по мере их нахождения.
В этом случае мы могли бы попробовать еще одно сжатие:
[3] 04 [-4] 43 fe 51 52 7 байт (fe - ваш 2-й вид как два дополнительных данных)
Мы ничего не получили, и мы начнем расти на следующей итерации:
[- 7] 03 04 fc 43 fe 51 52 8 байт
Мы будем расти на один байт за итерацию какое-то время, но это будет действительно хуже. Один байт может содержать только отрицательные числа до -128. Мы начнем расти на два байта, если файл превышает 128 байтов. Рост будет еще хуже, так как файл становится больше.
Там встречный поток против программы сжатия - метаданные. А также для реальных компрессоров заголовок прикреплен к началу файла. Это означает, что в конечном итоге файл начнет расти с каждым дополнительным сжатием.
RLE является отправной точкой. Если вы хотите узнать больше, посмотрите LZ77 (который возвращается в файл для поиска паттернов) и LZ78 (который создает словарь). Компрессоры, такие как zip, часто пытаются использовать несколько алгоритмов и использовать лучший.
Вот некоторые случаи, когда я могу думать о том, как сработало несколько сжатий.
Обычно предел является одним сжатием. Некоторые алгоритмы приводят к более высокой степени сжатия, и использование плохого алгоритма, за которым следует хороший алгоритм, часто приводит к улучшениям. Но использование хорошего алгоритма в первую очередь - это правильная вещь.
Существует теоретический предел того, насколько может быть сжат заданный набор данных. Чтобы узнать больше об этом, вам нужно будет изучить теорию информации .
В целом для большинства алгоритмов сжатие более одного раза не полезно. Однако есть специальный случай.
Если у вас есть большое количество дубликатов файлов, формат zip будет зависеть каждый независимо, и вы можете затем заархивировать первый zip файл, чтобы удалить дублируемую информацию о zip. В частности, для 7 идентичных файлов Excel размером 108 Кбит, застегнув их с 7-zip-результатами в архив 120 КБ. Zipping снова приводит к архиву 18kb. Проходя мимо, вы получаете уменьшающиеся прибыли.
Предположим, что у нас есть файл N бит длиной, и мы хотим сжать его без потерь, чтобы мы могли восстановить исходный файл. Существует 2 ^ N возможных файлов длиной N бит, поэтому наш алгоритм сжатия должен изменить один из этих файлов на один из 2 ^ N возможных других. Однако мы не можем выразить 2 ^ N разных файлов меньше, чем N бит.
Поэтому, если мы можем взять некоторые файлы и сжать их, мы должны иметь некоторые файлы, длина которых находится под сжатием, чтобы сбалансировать те, которые сокращаются.
Это означает, что алгоритм сжатия может только сжимать определенные файлы, и на самом деле он должен удлинять некоторые. Это означает, что в среднем сжатие случайного файла не может сократить его, но может удлинить его.
Практические алгоритмы сжатия работают, потому что мы обычно не используем случайные файлы. Большинство файлов, которые мы используем, имеют какую-то структуру или другие свойства, будь то текстовые или программные исполняемые файлы или значащие изображения. Используя хороший алгоритм сжатия, мы можем значительно сократить файлы типов, которые мы обычно используем.
Однако сжатый файл не является одним из этих типов. Если алгоритм сжатия хорош, большая часть структуры и избыточности были сжаты, а то, что осталось, похоже на случайность.
Нет алгоритма сжатия, как мы видели, может эффективно сжимать случайный файл, и это относится и к случайному файлу. Поэтому попытка сжимать сжатый файл не будет значительно сокращать его и, возможно, удлинит его.
Итак, нормальное число раз, когда алгоритм сжатия может быть с успехом выполнен, - это один.
Коррупция происходит только тогда, когда мы говорим о сжатии с потерями. Например, вы не можете восстановить изображение точно из файла JPEG. Это означает, что компрессор JPEG может надежно сократить файл изображения, но только за счет того, что он не сможет точно его восстановить. Мы часто готовы делать это для изображений, но не для текста и, в частности, для не исполняемых файлов.
В этом случае нет стадии начала коррупции. Он начинается, когда вы начинаете сжимать его, и ухудшается, когда вы сжимаете его больше. Именно поэтому хорошие программы обработки изображений позволяют указать, сколько сжатий вы хотите сделать при создании JPEG: чтобы вы могли сбалансировать качество изображения с размером файла. Вы находите точку остановки, рассматривая стоимость размера файла (что более важно для сетевых подключений, чем хранение, в целом) по сравнению со стоимостью сниженного качества. Нет очевидного правильного ответа.
Обычно сжатие один раз достаточно хорошо, если алгоритм хорош.
Фактически, сжатие несколько раз может привести к увеличению размера
Ваши две точки разные.
Теперь рассмотрим некоторые исключения или варианты,
Вы можете сжимать бесконечные времена. Тем не менее, второе и дополнительное сжатие обычно приводит к тому, что файл будет больше, чем предыдущий. Поэтому нет смысла в сжатии более одного раза.
Вы можете сжимать файл столько раз, сколько хотите. Но для большинства алгоритмов сжатия результирующее сжатие со второго раза будет незначительным.
Сколько раз я могу сжать файл до того, как он не станет меньше?
В общем, даже не один. Какой бы алгоритм сжатия вы ни использовали, всегда должен существовать файл, который вообще не сжимается, иначе вы всегда можете сжимать несколько раз, пока не достигнете 1 байта, по тому же аргументу.
Сколько раз я могу сжать файл до того, как он станет поврежденным?
Если программа, которую вы используете для сжатия файла, выполняет свою работу, файл никогда не будет поврежден (конечно, я думаю об уменьшении сжатия).
Сжатие (я думаю, что без потерь) в основном означает выражение чего-то более сжатого. Например
111111111111111
может быть более выражен как
15 X '1'
Это называется кодировкой длины. Другим методом, который может использовать компьютер, является поиск шаблона, который регулярно повторяется в файле.
Очевидно, что существует ограничение на то, насколько эти методы могут быть использованы, например, кодирование длины пробега не будет влиять на
15 X '1'
поскольку нет повторяющихся паттернов. Аналогичным образом, если методы замены шаблонов преобразуют длинные шаблоны в 3 char, их повторное применение будет иметь малое влияние, поскольку только оставшиеся повторяющиеся шаблоны будут иметь длину 3 или меньше. Обычно применение сжатия к уже сжатому файлу делает его немного большим, из-за различных накладных расходов. Применение хорошего сжатия к плохо сжатому файлу обычно менее эффективно, чем применение только хорошего сжатия.
Вот окончательный алгоритм сжатия (в Python), который путем повторного использования сжимает любую строку цифр до размера 0 (он оставил в качестве упражнения для читателя, как применить это к строке байтов).
def compress(digitString):
if digitString=="":
raise "already as small as possible"
currentLen=len(digitString)
if digitString=="0"*currentLen:
return "9"*(currentLen-1)
n=str(long(digitString)-1); #convert to number and decrement
newLen=len(n);
return ("0"*(currentLen-newLen))+n; # add zeros to keep same length
#test it
x="12";
while not x=="":
print x;
x=compress(x)
Вывод программ 12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 затем пустая строка. Он не сжимает строку на каждом проходе, но с достаточным количеством проходов сжимает любую строку цифр до нулевой длины. Убедитесь, что вы записываете, сколько раз вы отправляете его через компрессор, иначе вы не сможете его вернуть.
Это очень хороший вопрос. Вы можете просматривать файлы с разных точек зрения. Возможно, вы знаете априори, что этот файл содержит арифметические ряды. Позволяет просматривать его как поток данных "байты", "символы" или "образцы".
Некоторые ответы могут дать вам "теорию информации" и "математическую статистику", Пожалуйста, проверьте монографию этих исследователей для глубокого понимания:
Одна из основных концепций теории информации - entropy. Если у вас есть поток "байтов"... Энтропия этих байтов не зависит от значений ваших "байтов" или "выборок"... Если был определен только частоты, с помощью которых байты извлекают разные значения. Максимальная энтропия имеет место для полного случайного потока данных. Минимальная энтропия, равная нулю, имеет место для случая, когда ваши "байты" имеют одинаковое значение.
Он не становится меньше?
Итак, энтропия - это минимальное количество бит на ваш "байт", который вам нужно использовать при записи информации на диск. Конечно, это так, если вы используете алгоритм Бога. Эвристические алгоритмы без потерь в реальном времени не так.
Файл поврежден?
Я не понимаю смысла вопроса. Вы не можете записать бит на диск, и вы напишете поврежденный файл на диск с размером, равным 0 бит. Конечно, он поврежден, но его размер равен нулю.
Я хотел бы заявить, что сам предел сжатия на самом деле не был адаптирован к этому полному пределу. Так как каждый пиксель или написанный язык написан черным или напишите контур. Можно написать программу, которая может безупречно декомпилироваться в то, что она была, скажем, книгой, но могла бы сжать шаблон пикселей и слова в лучшую систему сжатия. Значение. Вероятно, сжатие займет гораздо больше времени, но поскольку системный файл получает большие гигабайты или террабайты, повторяющиеся буквы P и R и q, а также черно-белые отклонения могут быть сжаты в геометрической прогрессии в сложную автоматизированную формулу. Mhcien не нужны данные, чтобы иметь смысл, он просто может сделать игру с высокой степенью сжатия. Это, в свою очередь, позволяет нам создавать специальный механизм чтения для сжатия. То есть теперь у нас есть реальная сила сжатия. Дизайн всего движка, который может восстановить информацию на стороне пользователя. У движка есть свой собственный язык, который является оптимальным, без пробелов, просто заполняйте черные и белые пиксельные блоки самого маленького набора или даже пишите свой собственный шаблонный язык. Таким образом, он может в то же самое время для производительности mostoptiaml выдавать уникальный шифр или декомпрессионную формулу, когда он выключен, и, таким образом, файл оптимально сжимается и имеет пароль, который уникален для механизма его последующего распаковывания. Машина может сделать максимально возможное количество итераций для дальнейшего сжатия файла. Это все равно что иметь открытую книгу и поместить все написанные истории человечества на один лист формата А4. Я не знаю, но это другая теория. Таким образом, происходит разделение тома, поскольку формула для распаковки будет иметь свой собственный размер, даже если имя папки и/или информация о значке имеют размер, так что можно пойти дальше, чтобы поместить каждую форму данных в строку информации. хмм..
Пример более сложной техники сжатия с использованием "двойной таблицы или кросс-матрицы" Также устраняет экстренные символы unnessacry в алгоритме
[ПРЕДЫДУЩИЙ ПРИМЕР] В качестве примера возьмем кодировку длины пробега (возможно, самое простое полезное сжатие).
04 04 04 04 43 43 43 43 51 52 11 байт
Эта серия байтов может быть сжата как:
[4] 04 [4] 43 [-2] 51 52 7 байтов (я помещаю метаданные в скобки)
[ВЫКЛЮЧАЕТ В] 04.43.51.52 ЦЕННОСТИ 4.4. ** - 2 COMPRESSION
Дальнейшее сжатие с использованием добавочных символов в качестве замещающих значений
04.A.B.C ЦЕННОСТИ 4.4. ** - 2 COMPRESSION
В теории мы никогда не узнаем, это бесконечная вещь:
В информатике и математике термин полная теорема о занятости был использован для обозначения теоремы, показывающей, что ни один алгоритм не может оптимально выполнять определенную задачу, выполняемую некоторым классом профессионалы. Имя возникает потому, что такая теорема гарантирует, что существует бесконечная возможность продолжать поиск новых методов для улучшения как минимум какая-то конкретная задача. Например, полный теорема о занятости для авторов компиляторов утверждает, что таких как доказательно совершенный компилятор, оптимизирующий размер, как таковое доказательство поскольку компилятор должен был бы обнаруживать не завершающие вычисления и сводите их к бесконечному циклу с одной инструкцией. Таким образом, существование убедительно совершенный компилятор, оптимизирующий размер, будет подразумевать решение проблема остановки, которая не может существовать, что делает доказательство само по себе неразрешимая проблема.
Все зависит от алгоритма. Другими словами, вопрос может заключаться в том, сколько раз файл может быть сжат с использованием этого алгоритма сначала, а затем следующий...