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 .