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.

Popularne metody to:

• BZIP2
• Deflate
• Kodowanie Huffmana
• GIF
• Kodowanie arytmetyczne
• LZ77
• LZW
• Move To Front
• PCX
• PNG
• RLE
• transformata Burrowsa-Wheelera
• PPM

Zobacz też

• kompresja stratna
• złożoność Kołmogorowa
• kodek

Kompresja

Bezeztrátová komprese | Verlustfreie Datenkompression | Lossless data compression | Compressione dati lossless | 可逆圧縮 | Icke-förstörande komprimering