Сжатие данных из песочницы

Этим вопросом начал интересоваться достаточно давно. Идея экономия памяти, места на дисках витала давно и наверно у всех. Первая попытка написать свой алгоритм сжатия схожий на алгоритм RLE была в 2000 году, затем было еще несколько оригинальных концепций сжатия, но дальше предварительных тестов дело не пошло. В 2005 году взялся за идею сжатия всерьёз. Спустя 6 лет делюсь некоторыми выдержками из исследований.

Чтобы понять и осмыслить данную статью введем некоторую терминологию:

• N — Натуральное число
• Слово — N Bit то есть N бит с группировано в слово (байт это 8 битное слово)
• Комбинаций в слове — 2^N (два в степени N) (в байте 256 комбинаций)
• Блок (предложение) — N*2^N (Слово*Комбинаций слов)
• Комбинаций в блоке — 2^(N*2^N)
• Уникальных слов в блоке — 2^N
• Таблица распределений блоков — N строк (в строке количество комбинаций блоков с N уникальным словом)
• Таблица вхождений — N строк (в строке количество вхождений блоков с N уникальным словом)
• Входящий поток — конечное количество байт в фрагменте информации

Определение уникальных слов в блоке — количество не повторяющихся комбинаций слов в блоке. Пример:
1 1 1 1 1 1 1 1 одно уникальное слово
8 8 8 8 8 8 8 8 одно уникальное слово
1 8 2 5 1 5 1 2 четыре уникальных слова
4 6 7 3 3 3 3 3 четыре уникальных слова

Нахождение уникальных слов в блоке при N=3

Перебрав все комбинации в блоке получаем таблицу распределений блоков. Пример:
1 4
2 84
3 144
4 24

Сумма 256 (8 бит) Комбинаций в блоке - 2^(N*2^N)

Таблица распределений блоков N=2

01 16
02 7864080
03 23996064960
04 7504175995680
05 574579238688000
06 15768930151054080
07 189225474428390400
08 1111400775560275200
09 3407360398041600000
10 5630409646557696000
11 5045340384103219200
12 2403608358767616000
13 577538743541760000
14 62977597562880000
15 2510734786560000
16 20922789888000

Сумма 18446744073709551616 (64 бита) Комбинаций в блоке - 2^(N*2^N)

Таблица распределений блоков N=4

При N=4 и более таблицу распределений блоков методом перебора за несколько секунд уже не получить.

Первая часть алгоритма состоит в анализе входящего потока (создании Таблицы вхождений). Входящий поток делится на блоки, которые проверяются на количество уникальных слов. Номер уникального слова принимается за номер строки в Таблице вхождений. Значение в строке наращивается на единицу. Получив Таблицу вхождений можно увидеть некоторые свойства. Привожу пару примеров:

Построение графика по Таблице вхождений при N=8, файлы можно скачать здесь

Построение графика по Таблице вхождений при N=8, файлы можно скачать здесь

Построение графика по Таблице вхождений при N=8, файлы можно скачать здесь

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

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

Демонстрация спецального алгоритма

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

P.S. Первый алгоритм выполняется слишком долго, видео его работы не стал делать. Второй алгоритм показан на видео. Работает примерно на той же идеи что и BTW алгоритм, то есть сначала подготавливает данные, а потом эти данные сжимаються классическим алгоритмом.