Töm luften
Deflate är en förlustfri komprimeringsalgoritm som använder en kombination av LZ77- och Huffman-algoritmerna . Det beskrevs ursprungligen av Phil Katz för den andra versionen av hans PKZIP -arkiverare , som senare definierades i RFC 1951 (1996).
Deflate anses vara fri från alla befintliga patent, och medan patentet för LZW (det gäller i GIF -format ) fortfarande var i kraft, ledde detta till att Deflate inte bara användes i ZIP -formatet , som Katz ursprungligen designade det för, utan också i gzip- kompressorn/dekomprimeraren och i PNG-bilder .
Dataströmformat
Den tömda strömmen innehåller en serie block. Varje block föregås av ett trebitarshuvud:
- En bit: sista blockflaggan.
- 1: sista blocket.
- 0: Blocket är inte det sista.
- Två bitar: Metoden med vilken data kodades.
- 00: data är inte kodad (i blocket är direkt utdata).
- 01: Statisk Huffman -kodad data .
- 10: Data kodad med den dynamiska Huffman- metoden .
- 11: reserverat värde (fel).
De flesta block är kodade med metod 10 (dynamisk Huffman), som ger ett optimerat Huffman-kodträd för varje nytt block. Instruktionerna för att skapa Huffman-kodträdet följer omedelbart efter blockhuvudet.
Kompression utförs i två steg:
- ersättning av upprepade strängar med pekare (algoritm LZ77);
- ersättning av tecken med nya tecken baserat på hur ofta de används (Huffman-algoritmen).
Länkar
- RFC 1951 - DEFLATE komprimerade dataformatspecifikationer version 1.3
- Deflate-avkodning - Beskrivning av Deflate-datakomprimeringsformatet , E.V. Mikhalchik