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.