Demonstrator kompresji
Jak plik może się zmniejszyć, nie tracąc ani jednej litery? Dzięki temu, że się powtarza. Wklej tekst lub wybierz przykład i obserwuj trzy klasyczne metody w działaniu: LZ77 wskazuje wstecz na tekst, który już się pojawił, LZW podczas czytania uczy się słownika ciągów, a kodowanie długości serii liczy serie tego samego znaku. Wynik każdej metody jest ponownie dekompresowany, aby pokazać, że nic nie zginęło, a wykres porównuje metody z ZIP i z granicą entropii. Wpisz lub wklej tekst albo wybierz przykład, a następnie wskaż metodę. LZ77 zastępuje powtórzenia odwołaniami do wcześniejszego tekstu: kliknij wyróżniony fragment, aby zobaczyć, co kopiuje. LZW podczas czytania buduje słownik ciągów i wysyła ich numery. RLE ściska serie tego samego znaku. Wykres porównuje każdą metodę z ZIP i z granicą entropii, a aplikacja ponownie dekompresuje wynik, aby sprawdzić, że nic nie zginęło.
Jak to działa
- Wpisz lub wklej tekst albo wybierz przykład: akapit, piosenkę z refrenem, rząd pikseli, tabelę danych, losowe litery lub DNA.
- Wybierz LZ77, LZW lub RLE. Dla LZ77 ustaw, jak daleko wstecz może szukać, i kliknij wyróżnione odwołanie, aby zobaczyć wcześniejszy tekst, który kopiuje.
- Porównaj rozmiary na kafelkach i na wykresie z ZIP i z granicą entropii; test pod tekstem potwierdza, że dekompresja oddaje oryginał.
Kluczem są powtórzenia
Kompresja bezstratna działa, ponieważ prawdziwe dane się powtarzają. LZ77 przechowuje okno z właśnie przeczytanym tekstem; gdy kolejne znaki wystąpiły już w tym oknie, zapisuje zamiast nich krótkie odwołanie: cofnij się o tyle i skopiuj tyle znaków. Odwołanie kosztuje stałą liczbę bitów niezależnie od długości kopii, więc najwięcej oszczędzają długie i częste powtórzenia. LZW osiąga ten sam efekt inaczej: dodaje do słownika każdy nowy ciąg, który napotka, i odtąd wysyła numer tego ciągu.
Dlaczego niektóre dane się nie kurczą
Metoda, która zmniejsza niektóre pliki, musi powiększać inne: krótkich plików jest mniej niż długich, więc nie wszystkie mogą się skrócić. Kompresja wygrywa na danych ze wzorcami, takich jak tekst, tabele i proste obrazy, a przegrywa na danych bez nich. Losowe litery, dane zaszyfrowane i pliki już skompresowane nie dają metodom niczego, do czego mogłyby się odwołać, więc wynik wychodzi tak duży jak dane wejściowe albo większy. Najwyraźniej widać to przy kodowaniu długości serii: na tekście bez serii podwaja ono rozmiar.
Często zadawane pytania
Czym różni się kompresja bezstratna od stratnej?
Kompresja bezstratna oddaje dokładnie oryginał, bit po bicie; jest niezbędna dla tekstu, programów i danych, a ten demonstrator pokazuje wyłącznie metody bezstratne. Kompresja stratna, jak w zdjęciach JPEG, muzyce MP3 i wideo, odrzuca szczegóły, których ludzie prawie nie zauważają, i daje znacznie mniejsze pliki, ale oryginału nie da się odzyskać.
Jak ZIP kompresuje pliki?
ZIP i gzip używają metody deflate, która najpierw stosuje LZ77 z oknem 32 KB, a potem zapisuje literały i odwołania kodami Huffmana: krótkimi kodami dla częstych wartości i długimi dla rzadkich. To ten drugi krok sprawia, że ZIP zwykle wypada lepiej niż pokazane tu proste LZ77, które na każdy token zużywa stałą liczbę bitów.
Czy LZ77 może zejść poniżej entropii?
Pokazana entropia liczy znaki pojedynczo, bez kontekstu. LZ77 i LZW korzystają z kontekstu, bo odwołanie kopiuje cały fragment wcześniejszego tekstu, więc na tekście z powtórzeniami mogą tę liczbę pobić z dużym zapasem. Nigdy jednak nie pobiją prawdziwej entropii źródła, która uwzględnia cały kontekst.
Dlaczego rozmiary różnią się od prawdziwego pliku ZIP?
Demonstrator liczy tylko bity zakodowanych danych. Prawdziwy plik ZIP dodaje nagłówki, nazwę pliku, sumę kontrolną i tablice Huffmana, przez co bardzo małe pliki stają się raczej większe niż mniejsze.
Czy mój tekst jest gdzieś wysyłany?
Nie. Każda metoda, łącznie z porównaniem z ZIP, działa w twojej przeglądarce, a twój tekst zostaje w lokalnej pamięci tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora