फ़ाइल कम्प्रेशन वास्तव में कैसे काम करता है: Huffman Coding, LZ77 और DEFLATE का विस्तृत विवेचन

हर डेवलपर ने कम्प्रेस्ड फ़ाइलों के साथ काम किया है। आप एक पैकेज अनज़िप करते हैं, gzip-encoded रिस्पॉन्स सर्व करते हैं, या PNG एक्सपोर्ट करते हैं — और कम्प्रेशन पर्दे के पीछे चल रहा होता है। लेकिन वह सवाल जिसे अधिकांश ट्यूटोरियल छोड़ देते हैं: यह काम क्यों करता है? आप 500 KB की टेक्स्ट फ़ाइल को एक भी byte खोए बिना 180 KB में क्यों कम कर सकते हैं, लेकिन ZIP फ़ाइल को और कम्प्रेस नहीं कर सकते?

इसका उत्तर information theory और कुछ सुंदर एल्गोरिदम में है। यह लेख असली मैकेनिज्म समझाता है: Shannon entropy से Huffman trees तक, और DEFLATE फ़ॉर्मेट तक जो ZIP, gzip और PNG का आधार है।

फ़ाइलें कम्प्रेस्ड क्यों हो सकती हैं

फ़ाइलें कम्प्रेस्ड हो सकती हैं क्योंकि उनमें redundancy होती है — patterns, दोहराव और predictable sequences जो उनकी raw byte count से कम जानकारी ले जाते हैं।

एक सरल उदाहरण लीजिए। String AAAAAAAAAA (दस A) ASCII में 10 bytes लेती है। लेकिन इसकी information content तुच्छ है: इसे "दस A" के रूप में पूरी तरह describe किया जा सकता है। एक compression algorithm ठीक यही करता है — verbose, redundant data को एक छोटे description से replace करता है।

असली फ़ाइलें इस प्रकार की redundancy से भरी होती हैं:

• हिंदी टेक्स्ट लगातार सामान्य शब्दों और अक्षर combinations का उपयोग करता है। "है", "के", "में" "xqz" से कहीं अधिक बार आते हैं।
• Source code में गहरी repetitive structure होती है: function, return, const, indentation runs, blank lines।
• Bitmap images में लंबे horizontal runs होते हैं identical या near-identical pixels के — विशेषकर flat-color areas में।
• Log files timestamps, hostnames, और status codes हजारों बार repeat करती हैं।

Data जितना redundant होगा, उतना ही compressible होगा। जितना कम redundant — जितना random — compress करना उतना ही कठिन।

Entropy: Compression की कठोर सीमा

Claude Shannon के 1948 के पेपर A Mathematical Theory of Communication ने information content मापने का एक precise तरीका पेश किया: entropy, bits में मापी जाती है।

Shannon entropy इस सवाल का जवाब देती है: इस data source से एक symbol represent करने के लिए औसतन वास्तव में कितने bits चाहिए?

Symbols s₁, s₂, ..., sₙ और probabilities p₁, p₂, ..., pₙ वाले source के लिए formula:

H = -Σ pᵢ × log₂(pᵢ)

व्यवहार में इसका क्या मतलब है। मान लीजिए एक file में सिर्फ दो characters हैं: A (90% समय) और B (10% समय)।

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 bits per symbol

Naive encoding 1 bit per symbol (A के लिए 0, B के लिए 1) use करती है। लेकिन entropy बताती है कि theoretical minimum 0.469 bits per symbol है — आधे से कम। एक अच्छा compression algorithm इस limit के करीब पहुंचता है।

अब एक truly random file सोचिए जहां हर byte value (0–255) equal probability (1/256 प्रत्येक) के साथ आती है:

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 bits per byte

आठ bits per byte — maximum entropy। Exploit करने के लिए कोई redundancy नहीं। यही कारण है कि आप ZIP file को और compress नहीं कर सकते: यह already maximum entropy के करीब है। हर bit information ले जा रहा है; eliminate करने के लिए कोई pattern नहीं बचा।

Run-Length Encoding: सबसे सरल रूप

भारी algorithms तक पहुंचने से पहले, run-length encoding (RLE) core idea को स्पष्ट रूप से illustrate करती है।

RLE repeated symbols की एक run को एक count और symbol से replace करता है:

Original:  AAABBBBBCCDDDDDD
RLE:       3A 5B 2C 6D

Original: 16 characters। Encoded: 8 characters। 50% कमी।

RLE fax transmission (CCITT Group 3/4), BMP files और more complex formats के अंदर sub-step के रूप में उपयोग किया जाता है। इसकी कमज़ोरी स्पष्ट है: long runs के बिना data पर यह poorly perform करता है। String ABABABAB में कोई run नहीं है, इसलिए RLE हर जगह 1 के counts prefix करके इसे बड़ा बना देता है।

यही कमज़ोरी अधिक sophisticated approaches को drive करती है।

Huffman Coding: सामान्य Symbols के लिए छोटे Codes

Standard ASCII में, हर character को चाहे कितनी भी बार appear करे, 8 bits मिलते हैं। Huffman coding उस assumption को तोड़ता है। Frequent symbols को shorter codes मिलते हैं; rare symbols को longer codes। Average code length गिरती है और file shrink होती है।

Huffman Tree बनाना

String AABBBCCCC (9 characters) लेते हैं। Frequencies गिनते हैं:

Step 1. हर symbol को उसकी frequency से weighted leaf node में रखें।

[A:2]  [B:3]  [C:4]

Step 2. बार-बार दो सबसे कम weight वाले nodes को एक parent node में merge करें जिसका weight उनका sum है, जब तक एक tree न बचे।

[A:2] और [B:3] merge करें → parent [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

[C:4] और [AB:5] merge करें → root [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Step 3. Tree traverse करके codes assign करें: left edge = 0, right edge = 1।

Bit Savings की गणना

Huffman codes के साथ, AABBBCCCC encode करने का cost:

A × 2 occurrences × 2 bits = 4 bits
B × 3 occurrences × 2 bits = 6 bits
C × 4 occurrences × 1 bit  = 4 bits
Total = 14 bits

Fixed 8-bit ASCII के साथ:

9 characters × 8 bits = 72 bits

14 bits बनाम 72 bits — इस toy example में 81% की कमी। Real-world gains छोटे हैं, लेकिन principle लागू रहता है।

Critical insight: Huffman codes prefix-free हैं। कोई code किसी अन्य का prefix नहीं है, जिसका मतलब decoder बिना किसी separators के original stream को unambiguously reconstruct कर सकता है। Tree structure ही compressed file header में store होती है ताकि decoder इसे rebuild कर सके।

LZ77 और LZ78: Repeated Sequences का उपयोग

Huffman coding individual symbol frequencies पर काम करती है। लेकिन यह redundancy की एक बड़ी class miss करती है: repeated sequences। Source code में function शब्द हर बार 8 bytes लेता है। अगर दूसरे और बाद के occurrences को पहले की तरफ pointer से replace किया जा सके, तो काफी बचत होगी।

यही Abraham Lempel और Jacob Ziv ने अपने 1977 और 1978 के papers में describe किया था, जिसने हमें LZ77 और LZ78 दिए।

LZ77: Sliding Window Compression

LZ77 एक sliding window maintain करता है — recently seen data का buffer। Encoder नए data process करते समय window के through पीछे देखता है ताकि अगले आने वाले data के लिए longest match ढूंढ सके। अगर मिले, तो literal bytes की बजाय back-reference (offset, length) emit करता है।

String encode करने पर विचार करें:

abcabc

abc process करना: कोई prior history नहीं, literals a, b, c emit करें।

दूसरे abc को process करना: encoder पीछे देखता है और 3 positions पहले से शुरू होने वाला abc length 3 के साथ पाता है। तीन literal bytes की बजाय back-reference (offset=3, length=3) emit करता है।

Decoder (3, 3) देखकर अपने output buffer में 3 positions पीछे जाता है और 3 bytes copy करता है — abc perfectly reconstruct करता है।

Real implementation में, match search window size से bounded होती है (gzip 32 KB window use करता है)। Longer window अधिक matches ढूंढती है लेकिन अधिक memory और search time लगती है।

Back-reference (offset, length) typically 2–3 bytes होती है। तो 10-byte repeated sequence को 2-byte reference से replace करने से 8 bytes बचते हैं। Match जितनी longer, ratio उतना better।

LZ78 और LZW

LZ78 sliding window use करने की बजाय encountered patterns का explicit dictionary बनाता है। LZW (Lempel-Ziv-Welch), एक derivative, GIF compression और Unix compress utility के algorithm के रूप में प्रसिद्ध हुआ। LZW patterns को single dictionary indices के रूप में encode करता है, encoding और decoding के दौरान dictionary को on-the-fly बढ़ाता है।

DEFLATE: LZ77 Plus Huffman Coding

DEFLATE, RFC 1951 में define, LZ77 और Huffman coding को sequence में combine करता है:

1. LZ77 pass: Repeated sequences को (offset, length) back-references से replace करें। Output literals और back-references का stream है।
2. Huffman pass: उस stream पर Huffman coding apply करें। Frequent literals को short codes मिलते हैं; rare back-reference values को longer ones।

दोनों techniques अलग-अलग types की redundancy पर attack करती हैं। LZ77 long-range repetition eliminate करता है। Huffman coding फिर बचे हुए में frequency-based redundancy eliminate करती है। साथ मिलकर वे compression ratios achieve करते हैं जो अकेले कोई भी नहीं कर सकता।

DEFLATE data blocks में organized होता है। हर block तीन modes में से एक use कर सकता है:

• No compression — ऐसे data के लिए जहां compression output expand करेगी (already-random data)
• Fixed Huffman codes — एक pre-agreed code table, custom tree store करने का overhead बचाती है
• Dynamic Huffman codes — इस specific block के लिए optimized custom tree, block header में store

Dynamic mode most compressible data के लिए use होता है। Encoder block analyze करता है, optimal Huffman tree build करता है, block की शुरुआत में store करता है, फिर उस tree using data encode करता है।

Real File Formats में DEFLATE कहां रहता है

ZIP

ZIP files हर entry को independently उसकी own DEFLATE-compressed stream के साथ store करते हैं। Per-entry compression का मतलब है आप पूरा archive decompress किए बिना ZIP से single file extract कर सकते हैं। ZIP format already compressed files के लिए "stored" mode (no compression) भी support करता है।

gzip

gzip single DEFLATE stream को एक header (magic number, OS, modification time) और CRC32 checksum के साथ wrap करता है। यह HTTP Content-Encoding: gzip और .tar.gz archives के लिए standard compression format है। .gz extension always एक single DEFLATE stream होता है।

PNG

PNG अपने pixel data compress करने के लिए DEFLATE (via zlib) use करता है। Compression से पहले, PNG एक filter step apply करता है: यह pixels की हर row को एक prediction से differences में transform करता है (delta coding)। यह dramatically उन runs और repetitions को बढ़ाता है जिन्हें LZ77 exploit कर सकता है, compression significantly improve होती है। Typical screenshots और diagrams के लिए, PNG raw pixel data size के 20–50% तक compress हो जाता है। Image compression tools जो PNG export करते हैं, इस pipeline पर rely करते हैं।

zlib

zlib DEFLATE के around एक wrapper format है — यह एक two-byte header और Adler-32 checksum add करता है। PDF streams embedded content compress करते समय zlib/DEFLATE use करते हैं (PDF compression इन streams को recompressing या removing करके file size reduce करता है)। HTTP, WebSockets, और many network protocols भी zlib use करते हैं।

JPEG: एक अलग Approach

यहां रुकना सार्थक है क्योंकि JPEG एक completely different compression strategy use करता है — जो जानबूझकर data खोती है।

JPEG 8×8 pixel blocks पर Discrete Cosine Transform (DCT) apply करता है। DCT pixel values को frequency components में convert करता है (Fourier transform के similar)। High-frequency components — fine detail — फिर aggressively quantized होते हैं (coarser values पर rounded या completely discarded)। Remaining coefficients Huffman coding के साथ encode होते हैं, लेकिन lossy quantization step ही photographs के लिए JPEG को PNG से बहुत छोटा बनाता है।

Trade-off: JPEG original pixels perfectly reconstruct नहीं कर सकता। PNG कर सकता है। यह lossy vs. lossless distinction है जिसे हमारे article में lossy vs. lossless file conversion में depth से explore किया गया है।

एक photograph के लिए, quality 80 पर JPEG lossless PNG की बजाय 10% bytes use कर सकता है। Flat colors और sharp edges वाले screenshot के लिए, PNG usually जीतता है क्योंकि DCT artifacts visible होते हैं और DEFLATE flat regions बेहतरीन compress करता है।

ZIP File को और compress क्यों नहीं कर सकते

यह confusion का एक common source है। अगर compression patterns ढूंढकर काम करता है, तो already-compressed file को compress करने से almost nothing क्यों आता है?

क्योंकि DEFLATE अपना काम सही तरह से कर रहा है। एक well-compressed DEFLATE stream statistically random दिखता है — by design। Back-references और Huffman codes predictable patterns eliminate करते हैं। जो बचता है वो data की entropy limit के करीब है।

उस पर second compressor run करें और उसे कोई runs (LZ77 को कोई long matches नहीं मिलते) और कोई frequency skew (Huffman near-uniform symbol distribution देखता है) नहीं मिलेगी। Entropy already 7.9+ bits per byte है। Exploit करने के लिए कुछ नहीं बचा।

यही कारण है कि आपको already-compressed media कभी compress नहीं करना चाहिए। JPEG को ZIP में wrap करने से ZIP overhead का cost आता है बिना किसी size benefit के। यही MP3, MP4, HEIC पर लागू होता है — सभी compressed formats जो already अपने entropy ceiling के पास हैं।

Algorithm Comparison

सब कुछ एक साथ जोड़ना

gzip-compressed file के लिए raw data से compressed bytes तक की chain:

1. Input: Raw byte stream (जैसे एक text file)
2. LZ77: 32 KB sliding window के साथ back-references के लिए scan, literals और (offset, length) pairs का stream produce करें
3. Huffman coding: दो trees build करें — literals/lengths के लिए एक, offsets के लिए एक — और LZ77 output encode करें
4. DEFLATE blocks: Huffman trees और encoded data को एक या अधिक blocks में package करें
5. gzip wrapper: gzip header prepend करें, CRC32 और original file size append करें
6. Output: .gz file, compressible input के लिए typically 30–70% छोटी

Decompression strictly reverse में चलता है: gzip header parse करें, block headers से Huffman trees read और reconstruct करें, Huffman stream को LZ77 tokens में decode करें, original byte stream reconstruct करने के लिए back-references apply करें। Decompression always compression से faster होता है क्योंकि hard work (optimal matches ढूंढना, optimal trees build करना) सिर्फ एक बार होता है।

मुख्य बातें

• Files compressible हैं क्योंकि वे redundancy contain करती हैं — repeated patterns और skewed symbol frequencies।
• Shannon entropy hard floor set करती है: truly random data compress नहीं हो सकता क्योंकि हर bit already information carry कर रहा है।
• RLE repetition को crudely handle करता है। Huffman coding frequency skew को elegantly handle करता है। LZ77 long-range sequence repetition handle करता है।
• DEFLATE LZ77 और Huffman को sequence में chain करता है, इसलिए यह either algorithm alone को beat करता है। यह ZIP, gzip, PNG, और zlib-compressed PDF streams का engine है।
• JPEG fundamentally different approach लेता है: lossy DCT quantization followed by lossless Huffman, pixel accuracy को dramatic size reduction के साथ trade करता है।
• Compressed file compress करने से कुछ नहीं होता क्योंकि good compression near-maximum-entropy output produce करता है।

ये algorithms समझना tab काम आता है जब आप format choose कर रहे हों, unexpectedly large files diagnose कर रहे हों, या compression pipeline debug कर रहे हों। अगली बार जब आप PDF compression use करें, ZIP file extract करें, या image compression के लिए PNG export करें, आप exactly जानेंगे software आपके bits के साथ क्या कर रहा है।