Эффективное сжатие простых двоичных данных

27

У меня есть файл, содержащий упорядоченные двоичные числа от до 2 n - 1 :02n1

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z не сжимал этот файл очень эффективно (при n = 20 22 МБ были сжаты до 300 кБ).

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

DSblizzard
источник
11
Обратите внимание на колмогоровскую сложность, которая в некотором смысле является оптимальным сжатием (с точностью до аддитивной постоянной). К сожалению, сложность Колмогорова не вычислима ...
Юваль
12
Зачем вам нужно сжимать эти данные? Разве вы не можете просто восстановить его в любое время, когда вам это нужно? (Что тесно связано с подходом сложности Колмогорова, упомянутым @YuvalFilmus: сложность Колмогорова - это, по сути, длина самой короткой программы, которая генерирует выходные данные).
Дэвид Ричерби,
7
Я написал такой алгоритм в старшей школе 20 лет назад. Учитывая ваш вклад, он сжался бы до «нескольких байтов» (приблизительно 3 500 000: 1 в оптимальном сценарии). Однако данные редко когда-либо выглядят так, поэтому нецелесообразно иметь такой алгоритм. Общие алгоритмы сжатия имеют дело со сложными шаблонами, а не с простыми. Любой может написать алгоритм для хранения линейных данных, но задача сохранения интересных данных является сложной задачей.
phyrfox
3
Как n = 20 дает вам 22 МБ? Я получаю 4,2 МБ, если использую 4 байта целых чисел
njzk2
3
@ JiK о хорошо хорошо, это было бы первым понятием сжатия, не используя 8 битов, чтобы представить единственный бит.
njzk2

Ответы:

27

n

0
1
1
1
1
...

O(n)O(1)

nNn

В отличие от предложения DW «все или ничего», дельта-сжатие с кодированием по длине прогона может фактически дать разумные коэффициенты сжатия для некоторых простых реальных видов контента, таких как аудио с низким разрешением. (Таким образом, он подходит для сжатия звука низкого качества, с очень низкой задержкой и низким энергопотреблением.)

leftaroundabout
источник
44

Конечно, конечно, есть алгоритмы. Вот мой алгоритм:

  1. 02n1nn

  2. Если нет, запишите 1 бит, затем запишите 7z-сжатие файла.

Это чрезвычайно эффективно для файлов этой конкретной структуры.

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

Область "сжатие данных". Смотрите наш тег и читайте учебники по сжатию данных.

DW
источник
5
Работа компрессора заключается в распознавании общих закономерностей и их использовании. Это не так, как этот шаблон необычен или неясен. Так что это естественный вопрос, чтобы спросить, почему он не эксплуатируется. Сказать ему, что есть компромисс, или дать ему алгоритм, который терпит неудачу во всем, кроме того, что паттерн - это полный отговор.
Мердад
17
Конечно, выглядит необычно для меня. В реальных данных это встречается крайне редко по сравнению с типами схем, которые ищут хорошие компрессоры.
Амаллой
17
@ Mehrdad Это не язвительный отговорка: это весь смысл . Для любого шаблона X, который просто генерируется и просто проверяется, существует алгоритм сжатия, который ищет этот шаблон и работает с ним. Так что это ответ на любой вопрос в духе «Есть ли алгоритм сжатия, который имеет дело с таким X?» Конечно, всегда есть алгоритм, который ищет немного более сложные паттерны. И есть тот, который ищет немного более сложные паттерны, чем этот, тоже до бесконечности . Ваше возражение необоснованно.
Дэвид Ричерби,
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Жиль "ТАК - перестань быть злым"
Экстремальное применение этого принципа - битовые торцевые магнитные связи, где любой файл или набор файлов любого размера просто представлены (сжаты) с фиксированными 160 битами данных. Конечно, существует риск того, что может произойти коллизия хешей.
Slebetman
17

Все, что использует BWT (преобразование Берроуза-Уилера), должно быть в состоянии сжать это достаточно хорошо.

Мой быстрый тест на Python:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(Числа здесь 'first_compressor second_compressor time_taken bytes_out')

(BWT взято отсюда )

Это по-прежнему «не просто несколько байтов», но, тем не менее, гораздо лучше, чем просто один gzip. Например, BWT + bz2 уменьшается до 237 байтов с 1114111 для 16-битного ввода.

Увы, BWT слишком медленные и требуют много памяти для многих приложений. Особенно учитывая, что это наивная реализация в Python - на моей машине до 2 ** 20 у меня не хватает оперативной памяти.

С Pypy я смог запустить полный ввод 2 ** 20, и он сжимает его до 2611 байт с BWT, за которым следует bz2. Но это заняло более 3 минут и более 4 ГБ оперативной памяти ...

Кроме того, к сожалению, этот подход по-прежнему составляет O (2 ^ n) выходного пространства, как кажется - по крайней мере, из подгонки кривой 1..20.

TLW
источник
Вы можете избавиться от evalэтого: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):и fOut = first.compress(inputData).
Касперд
@kasperd - как мне напечатать имена в этом случае? Лично проще (и менее подвержено ошибкам) ​​сделать eval, чем пытаться синхронизировать имена и ссылки.
TLW
5
Сначала bwt, а затем bz2 сжимают это очень хорошо. Это очень странное поведение и, вероятно, из-за этой точной картины. Обратите внимание, что вы делаете bwt дважды (bz2 основан на BWT), что обычно приводит к ухудшению сжатия. Также обратите внимание, что сегодня bwt обычно работает с 4 times block sizeпамятью (например, ~ 4 МБ для этого) и со скоростью >10 MB/s(я являюсь автором такого алгоритма библиотеки / сжатия bwt), который вполне пригоден для многих приложений. Обратите внимание, что даже gzip дает очень хорошие сжимаемые результаты. Спасибо, что поделились, я не знаю ни одного исследования по использованию bwt дважды.
Кристоф
3
@Christoph - я знаю, что bz2 основан на BWT ... Я действительно начал писать ответ на эффект «просто используй bz2», но обнаружил, что он не сжимается почти так же хорошо, как я ожидал, пошел «да» и решил посмотреть, будет ли лучше мой собственный BWT. Только мне нужен был компрессор для выхода, и он сказал: «С таким же успехом можно попробовать разные компрессоры, чтобы посмотреть, что произойдет».
TLW
1
@ Кристоф - я посмотрел еще раз. 2 бита этих данных генерируют что-то, что чрезвычайно поддается кодированию RLE. Например, если вы посчитаете количество пар RLE, необходимых для 0, 1, 2, ... вложенных BWT на 16-битном входе, вы получите 622591 1081343 83 ...
TLW
10

Кодировка PNG делает именно то, что вы хотите. Он также работает с реальными данными, а не только с чрезвычайно организованными данными.

В PNG каждая строка кодируется с помощью фильтра, из которых 4 указаны. Одним из них является «кодирование этого пикселя как разности между его значением и значением пикселя над ним». После фильтрации данные архивируются с использованием DEFLATE.

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

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

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits
Корт Аммон - Восстановить Монику
источник
5

Любой практический алгоритм поиска конкретных структур будет ограничен только структурами, жестко закодированными в нем. Вы могли бы исправить 7z, чтобы распознать эту конкретную последовательность, но как часто эта конкретная структура будет встречаться в реальной жизни? Не достаточно часто, чтобы гарантировать время, необходимое для проверки входных данных для этого ввода.

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

Дерево поиска для такого подхода грубой силы растет экспоненциально с длиной программы и не практично для всех, кроме самых простых программ (что-то вроде 5-7 инструкций).

Роман Старков
источник
n
1
nnn+1n1
Ну, такие инструменты, как Mathematica, находят функции для многих последовательностей ...
Рафаэль
3

Коэффициенты сжатия полностью зависят от целевого декомпрессора. Если декомпрессор не может декодировать последовательные 4-байтовые числа более компактно, чем 4 байта на число, тогда вы SOL.

Существуют различные вещи, которые позволяют кодировать последовательные числа. Например, дифференциальное кодирование. Вы берете n байтов за раз, затем берете разность или xor битов и затем сжимаете результат. Это добавляет 4 варианта, чтобы попробовать для каждого байта: идентичность a'[i] = a[i]; разница a'[i] = a[i-1]-a[i]; обратная разница a'[i] = a[i]-a[i-1]; и хор a'[i] = a[i]^a[i-1]. Это означает добавление 2 битов для выбора методов и количество байтов для 3 из 4 вариантов.

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

чокнутый урод
источник