Существует ли известный максимум того, сколько строк 0 и 1 могут быть сжаты?

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

Это, конечно, не правильно (и, возможно, моя память о том, что он точно сказал, не верна). Понятно, что было бы нецелесообразно сжимать какую-либо строку из 0 и 1 до двух битов, потому что (даже если это было технически возможно), слишком много разных типов строк заканчивали бы сжатием до тех же двух бит (так как у нас есть только '01 'и' 10 'на выбор).

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

Другими словами, есть ли способ определить, к какой минимальной (наименьшей возможной) длине можно сжать строку из 0 и 1?

(Здесь меня интересует математическое максимальное сжатие, а не то, что в настоящее время технически возможно.)

Колмогоровская сложность - один из подходов к математической формализации. К сожалению, вычисление колмогоровской сложности строки является неисчислимой проблемой. Смотрите также: Аппроксимация колмогоровской сложности .

Можно получить лучшие результаты, если проанализировать источник строки, а не саму строку . Другими словами, часто источник может быть смоделирован как вероятностный процесс, который случайным образом выбирает строку как-то, согласно некоторому распределению. Затем энтропия этого распределения сообщает математически наилучшее возможное сжатие (вплоть до некоторой небольшой аддитивной постоянной).

Что касается невозможности идеального сжатия, вас также может заинтересовать следующее.

• Никакой алгоритм сжатия не может сжать все входные сообщения?
• Функции сжатия практичны только потому, что «битовые цепочки, которые встречаются на практике, далеко не случайны»?
• Существует ли теоретически проверенный оптимальный алгоритм сжатия?

Для любой заданной строки существует схема сжатия, которая сжимает ее до пустой строки. Поэтому не имеет смысла спрашивать , сколько одного строка может быть сжата, а сколько сбор (или распределение ) строк может быть сжато до, в среднем. В общем случае, учитывая набор из строк, любая схема сжатия требует не менее бит или около того для кодирования строки из набора в худшем случае.$N$$\log_2 N$

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

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

Если строка совпадает с записью 9-й симфонии Бетховена, четвертого движения, в формате AAC, которая хранится на жестком диске моего компьютера, то выходной сигнал - один бит «0».

Если строка является чем-то еще, то выводом является один бит «1», за которым следует идентичная копия исходной строки.

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

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

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

Таким образом, сжимаемость строки битов в действительности зависит не от длины строки, а от ее сложности по отношению к алгоритму сжатия.

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

Таким образом, система резервного копирования, пытающаяся выполнить резервное копирование файла, очевидно, должна попытаться сжать файл, чтобы сэкономить место, но сначала система резервного копирования проверяет, сохранен ли абсолютно идентичный файл! Таким образом, вместо резервного копирования чего-либо , все, что делает система резервного копирования, например, запоминает, что у вас есть файл с номером 1,487,578 в системе резервного копирования на вашем жестком диске.

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