Wydajna kompresja prostych danych binarnych

27

Mam plik zawierający uporządkowane liczby binarne od do 2 n - 1 :02n1

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.

DSblizzard
źródło
11
Sprawdź złożoność Kołmogorowa, która jest w pewnym sensie optymalną kompresją (aż do stałej addytywnej). Niestety złożoności Kołmogorowa nie można obliczyć ...
Yuval Filmus
12
Dlaczego musisz skompresować te dane? Czy nie możesz go zregenerować w dowolnym momencie? (Co jest ściśle związane z podejściem złożoności Kołmogorowa wspomnianym przez @YuvalFilmus: złożoność Kołmogorowa jest zasadniczo długością najkrótszego programu, który generuje dane wyjściowe).
David Richerby,
7
Takiego algorytmu napisałem w szkole średniej, 20 lat temu. Biorąc pod uwagę twój wkład, byłby skompresowany do „kilku bajtów” (około 3 500 000: 1 w optymalnym scenariuszu). Jednak dane rzadko tak wyglądają, więc nie jest praktyczne posiadanie takiego algorytmu. Ogólne algorytmy kompresji muszą radzić sobie ze złożonymi wzorcami, a nie prostymi. Każdy może napisać algorytm do przechowywania danych liniowych, ale przechowywanie interesujących danych jest wyzwaniem.
phyrfox
3
W jaki sposób n = 20 daje 22 MB? Dostaję 4,2 MB, jeśli używam 4-bajtowych liczb całkowitych
njzk2
3
@JiK och, ok. byłoby to pierwsze pojęcie kompresji, bez użycia 8 bitów do reprezentowania jednego bitu.
njzk2

Odpowiedzi:

27

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 dan

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.O(n)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, nKawałki wielkości N , aby amortyzować koszty znalezienian, zachowując dobrą niezawodność.Nn

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).

po lewej stronie
źródło
44

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

  1. 02n1nn

  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 i czytaj podręczniki dotyczące kompresji danych.

DW
źródło
5
Zadaniem kompresora jest rozpoznawanie typowych wzorców i ich wykorzystywanie. To nie jest tak, że ten wzór jest rzadki lub niejasny. Zatem naturalnym pytaniem jest, dlaczego nie jest ono wykorzystywane. Mówienie mu, że jest kompromis, lub dawanie mu algorytmu, który zawodzi we wszystkim, z wyjątkiem tego, że ten wzór jest całkowitym wyjściem.
Mehrdad
17
Na pewno wygląda dla mnie niecodziennie. Pojawiałoby się to bardzo rzadko w rzeczywistych danych, w porównaniu z wzorami, których szukają dobre sprężarki.
amalloy
17
@Mehrdad To nie jest ponury wyrzutek: chodzi o sedno . Dla każdego wzorca X, który jest po prostu generowany i po prostu sprawdzany, istnieje algorytm kompresji, który wyszukuje ten wzorzec i zajmuje się nim. To jest odpowiedź na każde pytanie w stylu „Czy istnieje algorytm kompresji, który zajmuje się takim X?” Jasne, zawsze istnieje algorytm, który szuka nieco bardziej złożonych wzorców. I jest taki, który szuka nieco bardziej skomplikowanych wzorów niż ten również w nieskończoność . Twój sprzeciw jest bezzasadny.
David Richerby,
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Gilles „SO- przestań być zły”
Ekstremalnym zastosowaniem tej zasady są ogniwa z magnesami bittorrent, w których dowolny plik lub zbiór plików o dowolnej wielkości są po prostu reprezentowane (kompresowane) do ustalonych 160 bitów danych. Istnieje oczywiście ryzyko kolizji skrótu.
slebetman
17

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.

TLW
źródło
Można się go pozbyć eval, wykonując: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):i fOut = first.compress(inputData).
kasperd
@kasperd - jak wydrukować nazwiska w takim przypadku? Osobiście jest łatwiej (i mniej podatne na błędy) wykonanie ewaluacji, niż próba synchronizacji nazw i referencji.
TLW
5
Najpierw bwt, a następnie bz2 kompresuje to wyjątkowo dobrze. Jest to wyjątkowo dziwne zachowanie i prawdopodobnie z powodu tego właśnie wzorca. Zauważ, że robisz BWT dwa razy ( BZ2 jest oparty na BWT), co zwykle skutkuje gorszą kompresją. Zauważ też, że dzisiaj bwt zwykle działa w 4 times block sizepamięci (np. ~ 4 MB do tego) i przy prędkościach >10 MB/s(jestem autorem takiego biblioteki / algorytmu kompresji bwt), który jest całkiem użyteczny dla wielu aplikacji. Zauważ, że nawet gzip daje bardzo dobre wyniki kompresji. Dzięki za udostępnienie Nie znam żadnych badań dotyczących dwukrotnego użycia BWT.
Christoph
3
@Christoph - Wiem, że bz2 jest oparty na BWT ... Właściwie zacząłem pisać odpowiedź na efekt „po prostu użyj bz2”, ale odkryłem, że nie kompresuje się tak dobrze, jak się spodziewałem, poszedł „huh ”i postanowiłem sprawdzić, czy mój własny BWT poradziłby sobie lepiej. Tylko ja potrzebowałem kompresora do wyjścia i poszedłem „równie dobrze mogę wypróbować różne kompresory, aby zobaczyć, co się stanie”.
TLW,
1
@Christoph - spojrzałem jeszcze raz. 2 bwts tych danych generują coś, co jest wyjątkowo podatne na kodowanie RLE. Tak jak w przypadku, gdy policzysz liczbę par RLE wymaganych dla 0, 1, 2, ... zagnieżdżonych BWT na 16-bitowym wejściu, otrzymasz 622591 1081343 83 ...
TLW
10

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
Cort Ammon - Przywróć Monikę
źródło
5

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).

Roman Starkov
źródło
n
1
nnn+1n1
Narzędzia takie jak Mathematica znajdują funkcje dla wielu sekwencji ...
Raphael
3

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).

maniak zapadkowy
źródło