Kompresja bezstratna (ang. lossless compression) to ogólna
nazwa takich metod upakowywania informacji do postaci zawierającej zmniejszoną
liczbę bitów tak, aby całą informację dało się z tej postaci odtworzyć do
identycznej postaci pierwotnej.
Najważniejszym twierdzeniem o kompresji bezstratnej jest:
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)
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.