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). Mówi ono, że 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.
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.

Source: Wiki