Kompresja bezstratna

Z Wikipedii

Kompresja bezstratna (ang. lossless compression) to ogólna nazwa metod upakowania informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem, że metoda ta gwarantuje, że informację można z tej postaci odtworzyć do identycznej postaci pierwotnej.

Najważniejszym twierdzeniem o kompresji bezstratnej jest:

Spis treści

1 Twierdzenie o zliczaniu (counting theorem)
2 Algorytmy kompresji bezstratnej
- 2.1 Popularne metody
3 Zobacz też

[edytuj] Twierdzenie o zliczaniu (counting theorem)

Niemożliwe jest skonstruowanie funkcji przekształcającej odwracalnie informację na informację (czyli funkcji kompresji bezstratnej), która nie wydłuża jakieś informacji o przynajmniej 1 bit, chyba że nie kompresuje ona żadnej informacji.

Dowód:

Załóżmy, że dana funkcja kompresuje choć jedną dowolną 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)

[edytuj] 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 (w praktyce trudne, choć teoretycznie bardzo dobrze kompresowalne),
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.