Kompresja bezstratna
W dzisiejszym świecie Kompresja bezstratna stał się stałym tematem rozmów. W miarę rozwoju społeczeństwa znaczenie Kompresja bezstratna staje się coraz bardziej widoczne w różnych aspektach życia codziennego. Wykazano, że od miejsca pracy po życie osobiste Kompresja bezstratna ma znaczący wpływ na sposób, w jaki ludzie wchodzą w interakcje ze sobą i przebieg różnych sytuacji. Przez lata Kompresja bezstratna wywołał debatę i refleksję i okazał się istotnym tematem w obecnym kontekście. W tym artykule przyjrzymy się różnym perspektywom Kompresja bezstratna i przeanalizujemy jego wpływ na różne obszary współczesnego życia.
Kompresja bezstratna (ang. lossless compression) – metoda kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, gwarantująca możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.
Najważniejszym twierdzeniem o kompresji bezstratnej jest twierdzenie o zliczaniu.
Twierdzenie o zliczaniu (counting theorem)
Niemożliwe jest skonstruowanie funkcji, przekształcającej odwracalnie każdą informację na informację (czyli funkcji kompresji bezstratnej), która nie wydłuża jakiejś informacji o przynajmniej 1 bit, chyba że nie kompresuje ona żadnej informacji.
Dowód:
Załóżmy, że dana funkcja kompresuje choć jedną wiadomość do długości N bitów z dowolnej większej długości.
Jest X wiadomości o długości nie większej od N bitów.
Jeśli żadna z wiadomości zawierających nie więcej niż N bitów nie została wydłużona, to w wyniku otrzymujemy przynajmniej X+1 wiadomości o długości nie większej niż N bitów.
Ponieważ X jest skończone, to X+1>X, a więc jest to sprzeczne z założeniem, że takich wiadomości jest X. Co należało udowodnić.
Skonstruowanie funkcji, która wydłuża o nie więcej niż 1 bit, jest trywialne. Dla dowolnej funkcji f(x), niech f′(x) będzie:
- dla f(x) zawierającego mniej bitów niż x: f′(x)=<0,f(x)>;
- dla f(x) zawierającego więcej bitów niż x: f′(x)=<1,x>;
- dla f(x) zawierającego tyle samo bitów co x: f′(x)=<0,f(x)> lub f′(x)=<1,x> (nie ma to znaczenia).
Algorytmy kompresji bezstratnej
Algorytmy kompresji bezstratnej dobrze kompresują „typowe” dane, czyli takie w których występuje znaczna nadmiarowość informacji (redundancja).
Pewne rodzaje danych są bardzo trudne lub niemożliwe do skompresowania:
- strumienie liczb losowych (niemożliwe do skompresowania)
- strumienie liczb pseudolosowych (trudne do skompresowania, choć teoretycznie łatwe)
- dane skompresowane za pomocą tego samego lub innego algorytmu (w praktyce trudne)
Najczęściej używane metody kompresji bezstratnej można podzielić na słownikowe i statystyczne, choć wiele metod lokuje się pośrodku:
- metody słownikowe poszukują dokładnych wystąpień danego ciągu znaków, np. zastępują 'the ' krótszą ilością bitów niż jest potrzebna na zakodowanie 4 niezwiązanych znaków. Jednak znajomość symbolu 'the ' nie pociąga za sobą usprawnień w kompresowaniu 'they ' czy 'then '.
- metody statystyczne używają mniejszej ilości bitów dla częściej występujących symboli, w przypadku praktycznie wszystkich oprócz najprostszych metod, prawdopodobieństwa zależą od kontekstu. A więc np. dla 'h' występującego po 't' używają mniejszej ilości bitów niż dla innych znaków w tym kontekście.
Popularne metody
- kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne
- LZ77, LZ78 i pochodne (LZSS, LZP, LZW, LZMW)
- RLE
- PPM
- transformata Burrowsa-Wheelera, Move To Front
Zobacz też
Linki zewnętrzne
- Testy różnych metod kompresji (ang.)
- Optymalizacja PNG
- Przetwarzanie sygnałów cyfrowych. dsp.agh.edu.pl. . (materiały dydaktyczne AGH)