det är inte riktigt, det är gjort.

förlustfria datakomprimeringsalgoritmer kan inte garantera komprimering för alla indatauppsättningar. Med andra ord, för alla förlustfria datakomprimeringsalgoritmer kommer det att finnas en inmatningsdatauppsättning som inte blir mindre när den bearbetas av algoritmen, och för alla förlustfria datakomprimeringsalgoritmer som gör minst en fil mindre kommer det att finnas minst en fil som den gör större. Detta bevisas enkelt med elementär matematik med hjälp av ett räkningsargument, enligt följande:

Antag att varje fil representeras som en sträng bitar av någon godtycklig längd.Antag att det finns en komprimeringsalgoritm som omvandlar varje fil till en utdatafil som inte är längre än originalfilen, och att minst en fil kommer att komprimeras till en utdatafil som är kortare än originalfilen.

låt M vara det minsta antalet så att det finns en fil F med Längd m bitar som komprimerar till något kortare. Låt N vara längden (i bitar) av den komprimerade versionen av F.

eftersom N<M, behåller varje fil med längd N sin storlek under komprimering. Det finns 2N sådana filer. Tillsammans med F gör detta 2n+1-filer som alla komprimerar till en av 2N-filerna med längd N.

men 2N är mindre än 2n + 1, Så enligt pigeonhole-principen måste det finnas någon fil med längd N som samtidigt är utgången från komprimeringsfunktionen på två olika ingångar. Den filen kan inte dekomprimeras på ett tillförlitligt sätt (vilket av de två originalen ska det ge?), vilket strider mot antagandet att algoritmen var förlustfri.

Vi måste därför dra slutsatsen att vår ursprungliga hypotes (att komprimeringsfunktionen inte gör någon fil längre) nödvändigtvis är osann.

https://en.wikipedia.org/wiki/Lossless_compression#Limitations

https://en.wikipedia.org/wiki/Kolmogorov_complexity