DEFLATEalgoritme

Het DEFLATE-algoritme is een verliesloze datacompressie-algoritme ontwikkeld door Phil Katz en later gestandaardiseerd in RFC 1951. Het combineert LZ77-achtig zoeken naar herhaling met Huffman-codering en wordt onder andere toegepast in gzip, zlib, PNG en HTTP-deflate. Door de combinatie haalt DEFLATE zowel een goede compressie als snelle uitvoering.

Werking en kernprincipes: DEFLATE opereert met een 32 kilobyte sliding window waarin herhaalde data worden gezocht. Voor elke positie kan een eerder voorkomen tekenreeks worden vervangen door een verwijzing met lengte en afstand. De maximale lengte van een verwijzing is 258. De resulterende symbolen bestaan uit literals (bytes), lengths en distances en worden vervolgens gecodeerd met Huffman-codes. Voor elk blok wordt een Huffman-codering opgebouwd uit de frequenties van de symbolen; er zijn bloktypes met vaste codes en bloktypes met dynamische codes.

Blokkenstructuur en types: DEFLATE verwerkt data in blokken die onafhankelijk gecodeerd kunnen worden. Een blok kan ongecomprimeerd zijn (stored block), gecodeerd met vaste Huffman-codes, of gecodeerd met dynamische Huffman-codes. Dynamische blokken leveren doorgaans de beste compressie op voor variabele data, terwijl vaste blokken snel zijn en voorspelbare prestaties bieden.

Decompressie en toepassingen: bij decompressie bepaalt de parser het bloktype, reconstruyeert de Huffman-sleutels indien nodig en decodeert de symbolen tot de oorspronkelijke data. DEFLATE is lossless en geschikt voor streaming, waardoor het in diverse omgevingen kan worden toegepast zonder aanvullende informatieverlies.

Standaardisatie en gebruik: DEFLATE is opgenomen in RFC 1951 en vormt de kern van veel gangbare formaten en protocollen, waaronder gzip, zlib, PNG en HTTP-deflate. Het is ontworpen als een evenwichtige oplossing tussen compressieverhouding, snelheid en implementatiecomplexiteit.