Mam plik zawierający uporządkowane liczby binarne od do 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.
information-theory
data-compression
DSblizzard
źródło
źródło
Odpowiedzi:
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
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, √n Kawałki wielkości N , aby amortyzować koszty znalezienian, zachowując dobrą niezawodność.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).
źródło
Oczywiście, że istnieją algorytmy. Oto mój algorytm:
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.
źródło
Wszystko, co korzysta z BWT (transformacja Burrowsa-Wheelera), powinno być w stanie dość dobrze skompresować.
Mój szybki test w języku Python:
(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.
źródło
eval
, wykonując:for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):
ifOut = first.compress(inputData)
.4 times block size
pamię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.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.
źródło
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).
źródło
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óżnicaa'[i] = a[i-1]-a[i]
; odwrotna różnicaa'[i] = a[i]-a[i-1]
; i Xora'[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).
źródło