Kompresja bezstratna

Ten artykuł od 2021-02 zawiera treści, przy których brakuje odnośników do źródeł.

Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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