Czy istnieje znane maksimum dla tego, ile ciągów zer i jedynek można skompresować?

38

Dawno temu czytałem artykuł w gazecie, w którym pewien profesor powiedział, że w przyszłości będziemy mogli skompresować dane do zaledwie dwóch bitów (lub czegoś takiego).

To oczywiście nie jest poprawne (i może być tak, że moja pamięć tego, co dokładnie stwierdził, jest nieprawidłowa). Zrozumiałe jest, że nie byłoby praktyczne kompresowanie żadnego ciągu zer i jedynek do zaledwie dwóch bitów, ponieważ (nawet jeśli było to technicznie możliwe), zbyt wiele różnych rodzajów ciągów skończyłoby się kompresowaniem do tych samych dwóch bitów (ponieważ mamy tylko '01 ”i„ 10 ”do wyboru).

W każdym razie, to sprawiło, że pomyślałem o możliwości kompresji dowolnego ciągu zer i jedynek według jakiegoś schematu. Czy dla tego rodzaju łańcucha istnieje znana zależność między długością łańcucha (stosunek między 0 a 1 prawdopodobnie nie ma znaczenia) i maksymalną kompresją?

Innymi słowy, czy istnieje sposób na określenie minimalnej (najmniejszej możliwej) długości, do której można skompresować ciąg zer i jedynek?

(Tutaj interesuje mnie matematyczna maksymalna kompresja, a nie to, co jest obecnie technicznie możliwe).

data-compression

— x457812
źródło

7

Do wyboru mielibyśmy również „00” i „11”. Ale argument jest taki sam, jeśli użyjesz ich, możesz skompresować tylko cztery różne ciągi.

— RemcoGerlich,

3

mathoverflow.net/q/160099/34859 : Pl patrz tutaj, że vide zasady szuflady zawsze będzie nieskończona liczba ciągów, których nie można skompresować ... Niezależnie od zastosowanego algorytmu (patrz sekcja zatytułowana „Tło” w pytanie

— ARi,

4

Kompresja zależy od posiadanej wiedzy na temat struktury danych. Był artykuł o kompresji ruchów szachowych, który pokazuje, w jaki sposób dodawanie wiedzy pomaga zwiększyć kompresję.

— spectras

1

Czy możesz wyjaśnić: Kompresja może być „stratna” lub „bezstratna” (lub też „hybrydowa”, która może korzystać z obu). Czy mówisz o maksymalnej kompresji przy użyciu tylko „bezstratnych” metod kompresji, czy też włączasz (zezwalasz) na stosowanie „kompresji stratnej”. Innymi słowy, wydaje mi się, że istnieją 3 możliwości: szukanie „maksymalnej kompresji” gdzie (1) dane muszą zawsze być w stanie dekompresować dokładnie tak, jak przed kompresją, (2) dane muszą mieć możliwość dekompresji, ale dopuszczalna jest pewna „utrata” (3), nie jest wymagana dekompresja danych.

— Kevin Fegan

Cześć @KevinFegan, w tym przypadku musiałaby to być opcja 1: „dane zawsze muszą być w stanie dekompresowane dokładnie tak, jak przed kompresją”

— x457812

45

Złożoność Kołmogorowa to jedno podejście do sformalizowania tego matematycznie. Niestety, obliczenie złożoności łańcucha Kołmogorowa jest problemem nieobliczalnym. Zobacz także: Przybliżenie złożoności Kołmogorowa .

Lepsze wyniki można uzyskać, analizując źródło ciągu, a nie sam ciąg . Innymi słowy, często źródło może być modelowane jako proces probabilistyczny, który losowo wybiera łańcuch według jakiegoś rozkładu. Entropia tego rozkładu mówi następnie najlepszą matematycznie możliwą kompresję (do pewnej małej stałej addytywnej).

W przypadku niemożności doskonałej kompresji możesz być zainteresowany następującymi informacjami.

— DW
źródło

ale kompresja jest jedną z technik szacowania entropii. Czy kompresja i entropia mogą być dwoma aspektami tego samego?

— Paul Uszak

1

@PaulUszak, tak, są one bardzo ściśle powiązane: patrz np . Twierdzenie Shannona . Pamiętaj jednak, że komentarze należy wykorzystywać wyłącznie w celu zasugerowania ulepszeń / wyjaśnień w poście, a nie zadawania dalszych pytań. Aby zadać nowe pytanie, użyj linku „Zadaj pytanie” w prawej górnej części strony.

— DW

35

$N$ $\log_2 N$

Ponadto w wielu przypadkach nie zależy nam na dokładnej rekonstrukcji. Nazywa się to kompresją stratną i polega na kompresji muzyki i filmów. W tym przypadku dolna granica podana powyżej nie obowiązuje, ale możesz wymyślić inne dolne granice.

— Yuval Filmus
źródło

1

N

$N$

\log_{2} N

$\log_2 N$

27

Oto prosty schemat, który może kompresować dowolne ciągi bitowe bezstratnie, przy czym najmniejszy wynik to tylko jeden bit:

JEŚLI ciąg znaków jest identyczny z zapisem dziewiątej symfonii Beethovena, czwartego ruchu, w formacie AAC, który jest przechowywany na twardym dysku mojego komputera, wówczas wyjście jest pojedynczym bitem „0”.

JEŻELI ciąg znaków jest czymkolwiek innym, wówczas wynikiem jest pojedynczy bit „1”, po którym następuje identyczna kopia oryginalnego łańcucha.

Ten schemat zmniejsza jedno możliwe wejście do dokładnie jednego bitu i zwiększa każde inne wejście pod względem długości. Istnieje ogólna zasada: jeśli algorytm kompresji może odwzorować dowolny ciąg wejściowy na skompresowany ciąg, i istnieje pasujący algorytm dekompresyjny, który odwzorowuje dowolny skompresowany ciąg z powrotem na oryginalny ciąg, a algorytm kompresji odwzorowuje każde wejście na krótszy ciąg, następnie musi odwzorować niektóre ciągi wejściowe na dłuższe.

— gnasher729
źródło

2

Dobra robota, aby odpowiedź była jasna i oczywista. Warto zauważyć, że jest to podobne do tego, co próbuje zrobić dobry algorytm kompresji - dla danej domeny wejściowej spróbuj skrócić najczęściej oczekiwane typy danych wejściowych w zamian za wydłużenie mniej powszechnych danych wejściowych.

— JBentley

6

Dla każdego schematu kompresji, jaki można wymyślić, możliwe jest wygenerowanie danych, które nie będą podlegały kompresji. Więc nawet jeśli twój schemat kompresji jest bardzo wydajny w przypadku niektórych typów danych, nigdy nie będzie konsekwentnie kompresowany do określonego współczynnika.

Sposób na utworzenie przykładu danych nieściśliwych dla konkretnego algorytmu kompresji jest prosty: weź dowolny rodzaj danych i przeprowadź go wielokrotnie przez algorytm kompresji, aż rozmiar się nie zmniejszy.

Zatem ściśliwość ciągu bitów nie jest tak naprawdę funkcją długości ciągu, ale jego złożoności w stosunku do algorytmu kompresji.

— m69 '' snarky and unelcoming ''
źródło

Witamy! Pamiętaj, że dotyczy to tylko kompresji bezstratnej. Kompresja stratna może kompresować wszystkie łańcuchy (przynajmniej tak długo, jak długo akceptujesz algorytm „Zwróć pusty łańcuch” jako algorytm kompresji stratnej; ;-)).

— David Richerby

@DavidRicherby To prawda, oczywiście. Odniosłem jednak wrażenie, że OP zadaje pytanie o kompresję bezstratną, ponieważ dyskutowanie o maksymalnej kompresji schematu stratnego nie ma sensu; pomysł, że możesz doprowadzić go do bezużytecznych ekstremów, jest nieodłącznym elementem koncepcji kompresji stratnej.

— m69 '' snarky and unelcoming ''

Tak, myślę, że to rozsądna interpretacja.

— David Richerby

-2

Istnieje interesujący i zupełnie inny algorytm wykorzystywany w korporacyjnych systemach tworzenia kopii zapasowych. Chodzi o to, że jeśli masz firmę z 10 000 komputerów, wiele z nich zawiera wiele identycznych plików. Na przykład wiadomość e-mail wysłana do wszystkich w firmie może skończyć jako identyczny plik na każdym dysku twardym.

Dlatego system kopii zapasowej próbujący wykonać kopię zapasową pliku powinien oczywiście spróbować skompresować plik, aby zaoszczędzić miejsce, ale najpierw system kopii zapasowej sprawdza, czy absolutnie identyczny plik jest już zapisany! Więc zamiast kopii zapasowych wszystko , wszystko, system backup robi to na przykład pamiętać, że masz numer pliku 1,487,578 na system tworzenia kopii zapasowych na dysku twardym.

Jest to szczególnie wydajne, na przykład gdy 10 000 użytkowników ma identyczny system operacyjny i zainstalowane aplikacje. Dla pojedynczych użytkowników nie jest to wcale bardzo przydatne.

— gnasher729
źródło

4

To ciekawe, ale nie rozumiem, jak to odpowiada na pytanie. Pytanie dotyczy ograniczeń kompresji, a nie ogólnej dyskusji na temat kopii zapasowych przedsiębiorstw.

— David Richerby

Nazywa się to deduplikacją i odbywa się za pomocą skrótów. Przechowywanie 128-bitowego skrótu dla każdego bloku na dysku wymaga dużo pamięci RAM. ZFS może to zrobić, aby oportunistycznie sprawić, aby niektóre bloki współdzieliły przestrzeń do kopiowania przy zapisie. Ale tego rodzaju problem kompresji (gdy próbujesz skompresować ogromny zestaw danych, do którego potrzebujesz losowego dostępu, a który zmienia się zbyt szybko, aby uzyskać normalną kompresję strumienia, ale ma nadmiarowość na poziomie bloku), nie jest istotny jako odpowiedź na to pytanie pytanie.

— Peter Cordes,