Kompresja bezstratna () – 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 () 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 bitów z dowolnej większej długości.
Jest wiadomości o długości nie większej od bitów.
Jeśli żadna z wiadomości zawierających nie więcej niż bitów nie została wydłużona, to w wyniku otrzymujemy przynajmniej +1 wiadomości o długości nie większej niż bitów.
Ponieważ jest skończone, to +1>, a więc jest to sprzeczne z założeniem, że takich wiadomości jest . Co należało udowodnić.
Skonstruowanie funkcji, która wydłuża o nie więcej niż 1 bit, jest trywialne. Dla dowolnej funkcji (), niech () będzie: dla () zawierającego mniej bitów niż : ()=<0,()>; dla () zawierającego więcej bitów niż : ()=<1,>; dla () zawierającego tyle samo bitów co : ()=<0,()> lub ()=<1,> (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ą ' ' krótszą ilością bitów niż jest potrzebna na zakodowanie 4 niezwiązanych znaków. Jednak znajomość symbolu ' ' nie pociąga za sobą usprawnień w kompresowaniu ' ' czy ' '. 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ż kompresja stratna złożoność Kołmogorowa kodek formaty plików dźwiękowych
Linki zewnętrzne Testy różnych metod kompresji Optymalizacja PNG (materiały dydaktyczne AGH)
Kategoria:Kompresja