Что значит «неограниченное» сжатие?

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

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

Экспертное мнение сходится на том, что «всегда сжатие достигается за счет устранения статистической избыточности в представлении информации. Ни один компрессор не может сжать любой файл. После обработки любым компрессором размер части файлов уменьшится, а оставшейся части — увеличится или останется неизменным. […] Поэтому невозможен „вечный“ архиватор, который способен бесконечное число раз сжимать свои же архивы. […] В области сжатия без потерь, т.е. собственно сжатия, такие революции невозможны» (Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатия изображения и видео. — М.: ДИАЛОГ-МИФИ, 2003. — 384 с. ISBN 5-86404-170-x С. 18-19). Кстати на тех же страницах этой книги (она доступна в сети) убедительно доказывается, почему энтропийное кодирование не способно преодолеть энтропийный предел сжатия.

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

«Революции невозможны»?

Итак, возможен ли вообще тип кодирования, способный преодолеть энтропийный предел сжатия?
Да возможен. Рассмотрим это на простом примере. Вот десятичные данные с уровнем энтропии близким к максимальному:


Итак 2185 десятичных цифр ( = 7258.4 бит = 907.3 байт) с примерно равными частотами распределений. Что может нам дать энтропийное кодирование? Практически ничего. Сжатие, даёт по формуле Шеннона, в лучшем случае 7255.526792 бит = 906.940849 байт. То есть выигрыш сжатия всего лишь 2.886095013 бит. И при этом к сжатым данным ещё необходимо будет добавить данные о 10 частотах распределений этих цифр, а значит, получим на выходе количество данных превышающее исходное. Есть ещё идеи? Похоже, что в рамках энтропийного кодирования нет.

Нужно выйти за эти пределы. Тогда можно записать эти 2185 цифр всего 7 знаками.

5^(5^5)

То есть, расширив алфавит кодирования лишь на три знака: ), ( и ^ мы формально получаем 7*log2(13)=25.9 бит ( = 3.24 байт). Теперь выигрыш сжатия составил -7232.5 бит + необходимо будет добавить некоторые служебные данные описания нового алфавита кодирования. То есть преодолеть энтропийный предел сжатия в каких-то случаях теоретически возможно. А практически?

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

Как это работает

Если случайные данные с почти равными (на то они и случайные) частотами распределений и, следовательно, с уровнем энтропии близким к максимальному. Энтропийное кодирование тут бессильно.

А что если бы нам удалось уменьшить их энтропию без потерь информации? Например, изменив частоты распределений символов алфавита. Ведь достаточно изменить частоту хотя бы одного символа алфавита (например, удвоить его количество по сравнению с остальными символами алфавита), и затем вполне можно использовать энтропийное кодирование, которое отлично работает с неравномерно распределенными знаками алфавита. Вопрос только в том, как это сделать. Причём желательно сделать безнаказанно (ничего не прибавляя к первоначальному объему данных).

Идея заключается в том, чтобы использовать энтропию против энтропии. Но конечно просто перемешивать и перетасовывать данные в надежде, что в них, наконец, появится какая-то неравномерность, не вариант. На это уйдут те же самые пресловутые миллиарды лет. А нам нужен не просто хаос, но хаос управляемый.

Итак, порядок сжатия следующий:

1. Допустим, у нас имеются 256-ричные данные (байт-код — БК) с уровнем энтропии близким максимальному (УЭБМ) (все знаки алфавита равномерно распределены). Например, там могут быть уже ранее эффективно сжатые данные. Сжать их существующими способами сжатия не получается поскольку у них УЭБМ и соответственно их избыточность близка к нулю.

2. В этом БК выбираем какой-либо знак алфавита. Поскольку количество всех знаков в БК примерно равно, не столь важно какой знак мы выберем. И для примера, выберем самый последний символ с кодом 255 (обозначим с255).

3. Сохраняем код расположения с255 среди всех остальных символов, после чего его удаляем. Полученные данные без с255 уже представляет собой 255-ричный алфавит.

4. С оставшимися данными производим n раз последовательное сложение по модулю 256, в результате чего в данных опять появляется с255 в количестве примерно равном количеству каждого вида символов (они равновероятны).

5. Теперь согласно коду расположения по пункту 3 вставляем ранее удаленные с255 на их первоначальные места. Теперь количество с255 примерно удвоено по сравнению с остальными символами алфавита.

6. Теперь можно применять энтропийное кодирование. Подсчитаем, какой выигрыш нам это даст: Допустим, всего БК по пункту 1 было 100 миллионов байт. Среднее количество каждого вида по 390625 байтов. В результате вышеуказанных операций мы примерно удвоили количество с255 и получили в среднем 781250 с255. После энтропийного сжатия этих закодированных данных получаем 99972649.54 байт. Выигрыш в результате такого кодирования составляет -27350.46 байт за один проход. И таким образом можно сжимать ранее сжатые данные и дальше.



MD5: 2b38fa5d2d6a9fd5c7cb11ae75ac05f0
SHA256: 62773affb5aa1739fd66bd5061469eaf82dc728df454ac823626b811bfca45c3
Вот демо-версия программы (гарантированно работает с файлами до 60 Мб)

Порядок обратного восстановления данных:

1. Разжимаем энтропийным декодером сжатые данные по пункту 6 порядка сжатия.

2. Далее, поблочно, например, с длиной блока m=2560 байт восстанавливаем исходные данные в следующем порядке:

3. Поскольку данные о расположение старых и новых с255 по пункту 5 порядка сжатия мы не сохранили, производим последовательный перебор всех комбинаций с255 (старые-новые). Среднее количество с255 при m=2560 примерно равно 20. Количество всех комбинаций старые-новые с255 равно 2^20=1048576.

4. При вышеуказанном переборе комбинаций, для каждой комбинации удаляем из блока предположительно старые с255 и производим операцию обратную произведённой по пункту 4 порядка сжатия (в обратном порядке выполняем вычитание по модулю 256 для восстановления исходных данных).

5. В случае нахождения верной комбинации все с255 исчезают, поскольку мы восстанавливаем данные в их первоначальном виде как они были по пункту 3 порядка сжатия и представляли собой 255-ричный алфавит (среди них отсутствовал с255).

6. Перебор комбинаций в текущем блоке прекращаем и продолжаем операции восстановления данных по пунктам 4-5 с остальными блоками данных пока не будут восстановлены все исходные данные.

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

Подсчитаем время на восстановление данных всех блоков путем переборов вышеуказанных комбинаций:
При 1048576 комбинациях указанного блока, если осуществлять перебор при помощи достаточно мощной видеокарты (ATI Radeon HD 5870 Eyefinity или AMD Radeon HD 7970 (x3)) со скоростью 2000 MH/S то получаем среднее время полного перебора всех комбинаций блока длиной m=2560 0.000524288 с. Для вышеуказанного примера суммарное общее время составит 20.48 с для одного прохода.

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