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).
źródło
Odpowiedzi:
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.
źródło
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.
źródło
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.
źródło
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.
źródło
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.
źródło