To jest wersja przejrzana tej strony
Kompresja bezstratna (ang. lossless compression) – metodakompresji 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.
Niemożliwe jest skonstruowaniefunkcji, przekształcającej odwracalnie każdą informację na informację (czyli funkcji kompresji bezstratnej), która nie wydłuża jakiejś informacji o przynajmniej 1bit, chyba że nie kompresuje ona żadnej informacji.
Dowód:
Załóżmy, że dana funkcja kompresuje choć jedną wiadomość do długościN bitów z dowolnej większej długości.
JestX wiadomości o długości nie większej odN 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 przynajmniejX+1 wiadomości o długości nie większej niżN bitów.
PonieważX jest skończone, toX+1>X, a więc jest to sprzeczne z założeniem, że takich wiadomości jestX. Co należało udowodnić.
Skonstruowanie funkcji, która wydłuża o nie więcej niż 1 bit, jest trywialne.Dla dowolnej funkcjif(x), niechf′(x) będzie:
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:
Najczęściej używane metody kompresji bezstratnej można podzielić nasłownikowe i statystyczne, choć wiele metod lokuje się pośrodku: