Wydajna kompresja prostych danych binarnych

Mam plik zawierający uporządkowane liczby binarne od do 2 n - 1 :$0$$2^n - 1$

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z nie skompresował tego pliku bardzo wydajnie (dla n = 20 22 MB zostało skompresowanych do 300 kB).

Czy istnieją algorytmy, które potrafią rozpoznać bardzo prostą strukturę danych i skompresować plik do kilku bajtów? Chcę też wiedzieć, w jakim obszarze CS lub teorii informacji badane są takie inteligentne algorytmy. „AI” byłoby zbyt szerokie, sugeruj bardziej konkretne słowa kluczowe.
Pojęcie symetrii powinno odgrywać podstawową rolę w kompresji danych, ale wyszukiwane hasła „symetria w kompresji danych” i „teoria grup w kompresji danych” nieoczekiwanie nie zwracają prawie nic istotnego.

Wydaje się, że jest to oczywisty przypadek użycia do kompresji delta . Jeśli jest znane a priori, jest to trywialne: zapisz pierwszy numer dosłownie, a dla każdego następnego zapisz tylko różnicę w stosunku do poprzedniego. W twoim przypadku to da$n$

0
1
1
1
1
...

Można to następnie z prostym kodowaniem długości przebiegu zapisać w przestrzeni , ponieważ istnieją tylko grupy O ( 1 ) (a mianowicie dwie) o różnych deltach.$\mathcal{O}(n)$$\mathcal{O}(1)$

Jeśli nie jest znane, najprostszą rzeczą byłoby poszukiwanie siły słowa brute-force dla rozmiaru słowa, dla którego ta reprezentacja delta / przebiegu jest najkrótsza. Być może wykonuj tylko wyszukiwanie losowo wybranych, $n$Kawałki wielkości N , aby amortyzować koszty znalezienian, zachowując dobrą niezawodność.$\sqrt{N}$$n$

W przeciwieństwie do propozycji DW „wszystko albo nic”, kompresja delta z kodowaniem długości przebiegu może faktycznie zapewnić rozsądne współczynniki kompresji dla niektórych prostych rzeczywistych treści, takich jak dźwięk o niskiej rozdzielczości. (Jest więc odpowiedni do kompresji dźwięku niskiej jakości, o bardzo niskim opóźnieniu i niskiej mocy).

Oczywiście, że istnieją algorytmy. Oto mój algorytm:

1. $0$$2^n-1$$n$$n$

2. Jeśli nie, wypisz 1 bit, a następnie wypisz kompresję pliku 7z.

Jest to niezwykle wydajne w przypadku plików o tej konkretnej strukturze.

Chodzi o to: nie ma darmowego lunchu w kompresji danych. Możliwe, że będziesz w stanie zbudować algorytm kompresji, który dobrze kompresuje jeden typ pliku, kosztem gorszej kompresji innych. Ale jeśli wiesz a priori coś o naturze plików, które chcesz skompresować, możesz zoptymalizować algorytm dla tego konkretnego typu pliku.

Obszar ten obejmuje „kompresję danych”. Zobacz nasz tag kompresji danych i czytaj podręczniki dotyczące kompresji danych.

Wszystko, co korzysta z BWT (transformacja Burrowsa-Wheelera), powinno być w stanie dość dobrze skompresować.

Mój szybki test w języku 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

(Liczby tutaj to „first_compressor second_compressor time_taken bytes_out”)

(BWT pochodzi stąd )

To wciąż „nie tylko kilka bajtów”, ale i tak jest znacznie lepsze niż sam gzip. Na przykład BWT + bz2 sprowadza się do 237 bajtów z 1114111 dla 16-bitowego wejścia.

Niestety, BWT są zbyt wolne i wymagają dużej ilości pamięci do wielu zastosowań. Zwłaszcza, że ​​jest to naiwna implementacja w Pythonie - na moim komputerze brakuje mi pamięci RAM przed 2 ** 20.

Dzięki Pypy mogłem uruchomić pełne wejście 2 ** 20 i kompresuje je ono do 2611 bajtów za pomocą BWT, a następnie bz2. Ale zajmuje ponad 3 minuty i osiąga ponad 4 GB pamięci RAM ...

Niestety, podejście to wciąż jest przestrzenią wyjściową O (2 ^ n), wydaje się - przynajmniej z dopasowywania krzywej 1..20.

Kodowanie PNG robi dokładnie to, co chcesz. Działa również na rzeczywistych danych, nie tylko na wyjątkowo zorganizowanych danych.

W PNG każdy wiersz jest kodowany za pomocą filtra, z których 4 są określone. Jednym z nich jest „zakoduj ten piksel jako różnicę między jego wartością a wartością piksela jeden nad nim”. Po filtrowaniu dane są następnie skompresowane przy użyciu DEFLATE.

To filtrowanie jest specyficznym przykładem kodowania delta wspomnianego przez lewo w jego odpowiedzi, z tym wyjątkiem, że zamiast śledzić go za pomocą kodowania długości przebiegu, podążasz za nim za pomocą mocniejszego algorytmu DEFLATE. Osiąga ten sam cel, tylko DEFLATE obsłuży większą różnorodność danych wejściowych, jednocześnie zapewniając pożądane współczynniki kompresji.

Innym narzędziem często używanym w danych naukowych, gdzie prosty filtr + DEFLATE nie jest tak skuteczny, jest kodowanie RICE. W RICE bierzesz blok wartości i wyprowadzasz najpierw wszystkie najbardziej znaczące bity, a następnie wszystkie 2. najbardziej znaczące bity, aż do najmniej znaczących bitów. Następnie kompresujesz wynik. W przypadku danych, które nie będą tak skuteczne, jak filtrowanie w stylu PNG (ponieważ są one idealne do filtrowania w formacie PNG), ale w przypadku wielu danych naukowych zwykle prowadzi to do dobrych wyników. W wielu danych naukowych widzimy, że najbardziej znaczący bit zmienia się powoli, a najmniej znaczący jest prawie losowy. Oddziela to wysoce przewidywalne dane od wysoce entropicznych danych.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits

Każdy praktyczny algorytm wyszukujący określone struktury byłby ograniczony tylko do struktur na stałe w nim zakodowanych. Możesz załatać 7z, aby rozpoznać tę konkretną sekwencję, ale jak często ta konkretna struktura będzie występować w prawdziwym życiu? Niezbyt często, aby uzasadnić czas potrzebny na sprawdzenie danych wejściowych dla tego wejścia.

Pomijając praktyczne aspekty, idealną kompresor można sobie wyobrazić jako algorytm, który próbuje skonstruować najkrótszy program generujący dane wyjście. Nie trzeba dodawać, że nie ma praktycznych sposobów na zrobienie tego. Nawet jeśli spróbujesz wyliczyć wszystkie możliwe programy z użyciem brutalnej siły i sprawdzisz, czy wygenerowały one pożądane wyjście ( nie jest to całkowicie szalony pomysł ), napotkasz problem Halting , co oznacza, że ​​będziesz musiał przerwać biegi próbne po określonej liczbie kroków wykonania, zanim się zorientujesz, czy ten program zdecydowanie nie może wygenerować pożądanego wyniku.

Drzewo wyszukiwania dla takiego podejścia z użyciem siły brutalnej rośnie wykładniczo wraz z długością programu i nie jest praktyczne dla wszystkich, ale dla najprostszych programów (coś w rodzaju instrukcji o długości 5-7).

Współczynniki kompresji zależą całkowicie od docelowego dekompresora. Jeśli dekompresor nie może dekodować kolejnych 4-bajtowych liczb w bardziej kompaktowy sposób niż 4 bajty na liczbę, oznacza to, że jesteś SOL.

Istnieją różne rzeczy, które pozwoliłyby na kodowanie kolejnych numerów. Na przykład kodowanie różnicowe. Bierzesz n bajtów naraz, a następnie bierzesz różnicę lub xor bitów, a następnie kompresujesz wynik. Dodaje tutaj 4 opcje do wypróbowania dla każdej liczby bajtów: tożsamość a'[i] = a[i]; różnica a'[i] = a[i-1]-a[i]; odwrotna różnica a'[i] = a[i]-a[i-1]; i Xor a'[i] = a[i]^a[i-1]. Oznacza to dodanie 2 bitów w celu wybrania metod i liczby bajtów dla 3 z 4 opcji.

Jednak nie wszystkie dane są sekwencją rekordów o stałej długości. Różnicowe kodowanie nie ma w tym sensu (chyba że kompresor może empirycznie udowodnić, że działa na odrobinę danych).