Tøm luften ud
Deflate er en tabsfri komprimeringsalgoritme , der bruger en kombination af LZ77- og Huffman-algoritmerne . Det blev oprindeligt beskrevet af Phil Katz for den anden version af hans PKZIP- arkiver , som senere blev defineret i RFC 1951 (1996).
Deflate anses for at være fri for alle eksisterende patenter, og mens patentet for LZW (det gælder i GIF -format ) stadig var gældende, førte dette til brugen af Deflate ikke kun i ZIP -formatet , som Katz oprindeligt designede det til, men også i gzip- kompressoren/dekomprimeringen og i PNG-billeder .
Datastrømsformat
Den tømte strøm indeholder en række blokke. Hver blok er indledt af en tre-bit header:
- En smule: sidste blokflag.
- 1: sidste blok.
- 0: Blokken er ikke den sidste.
- To bit: Metoden, hvorved dataene blev kodet.
- 00: data er ikke kodet (i blokken er direkte outputdata).
- 01: Statiske Huffman -kodede data .
- 10: Data kodet ved hjælp af den dynamiske Huffman -metode .
- 11: reserveret værdi (fejl).
De fleste blokke er kodet ved hjælp af metode 10 (dynamisk Huffman), som giver et optimeret Huffman-kodetræ for hver ny blok. Instruktionerne til oprettelse af Huffman-kodetræet følger umiddelbart efter blokoverskriften.
Kompression udføres i to trin:
- udskiftning af gentagne strenge med pointere (algoritme LZ77);
- udskiftning af tegn med nye tegn baseret på hyppigheden af deres brug (Huffman-algoritme).
Links
- RFC 1951 - DEFLATE komprimeret dataformat specifikation version 1.3
- Deflate-dekodning - Beskrivelse af Deflate-datakomprimeringsformatet , E.V. Mikhalchik