> shannon | fano | entropy <
// Shannon-Fano – डेटा कंप्रेशन के लिए टॉप‑डाउन एंट्रॉपी एन्कोडिंग
एंट्रॉपी‑आधारित
सूचना सिद्धांत का उपयोग करके कुशल वैरिएबल‑लेंथ कोड बनाता है।
टॉप‑डाउन अप्रोच
प्रतीकों को समान प्रायिकता वाले समूहों में रिकर्सिव तरीके से बाँटता है।
ऐतिहासिक एल्गोरिथ्म
एक अग्रणी विधि जिसने आधुनिक कंप्रेशन तकनीकों को प्रभावित किया।
>> तकनीकी जानकारी
Shannon-Fano कैसे काम करता है?:
Shannon-Fano एन्कोडिंग में प्रतीकों को आवृत्ति के अनुसार क्रमबद्ध किया जाता है और फिर उन्हें दो समूहों में बाँटा जाता है जिनकी कुल प्रायिकता लगभग बराबर हो। हर विभाजन कोड में एक बिट जोड़ता है (बाएँ के लिए 0, दाएँ के लिए 1)। परिणामस्वरूप वैरिएबल‑लेंथ प्रीफिक्स कोड मिलते हैं।
एन्कोडिंग प्रक्रिया:
टेक्स्ट: "AAABBCD" फ़्रीक्वेंसी: A:3, B:2, C:1, D:1 स्प्लिट: [A] | [B,C,D] कोड: A: 0 B: 10 C: 110 D: 111 एन्कोडेड आउटपुट: 0 0 0 10 10 110 111
Shannon-Fano क्यों इस्तेमाल करें?:
- >इम्प्लीमेंट करना आसान
- >अच्छा कंप्रेशन रेश्यो
- >महत्त्वपूर्ण ऐतिहासिक भूमिका
- >सीखने‑सिखाने के लिए उपयोगी
- >प्रीफिक्स कोड उत्पन्न करता है
>> अक्सर पूछे जाने वाले प्रश्न
Shannon-Fano एन्कोडिंग क्या है?
Shannon-Fano एन्कोडिंग एक एंट्रॉपी‑आधारित कोडिंग तकनीक है जिसे 1940 के दशक में Claude Shannon और Robert Fano ने विकसित किया था। यह उन शुरुआती एल्गोरिथ्मों में से एक है जो प्रतीकों की प्रायिकता के आधार पर वैरिएबल‑लेंथ कोड का उपयोग करते हैं।
Shannon-Fano बनाम Huffman?
दोनों वैरिएबल‑लेंथ कोड बनाते हैं, लेकिन Huffman एल्गोरिथ्म इष्टतम है और औसत कोड लंबाई को न्यूनतम करता है। Shannon-Fano सरल है, पर थोड़ा लंबा कोड दे सकता है। Huffman ट्री को नीचे से ऊपर बनाता है, जबकि Shannon-Fano ऊपर से नीचे।
स्प्लिटिंग कैसे काम करती है?
प्रतीकों को फ़्रीक्वेंसी के अनुसार क्रमबद्ध किया जाता है और फिर दो समूहों में बाँटा जाता है जिनकी कुल प्रायिकता जितनी हो सके उतनी समान हो। यह प्रक्रिया रिकर्सिव रूप से दोहराई जाती है जब तक कि हर समूह में केवल एक प्रतीक न रह जाए।
क्या Shannon-Fano आज भी इस्तेमाल होता है?
आज Shannon-Fano मुख्यतः ऐतिहासिक और शैक्षणिक उदाहरण के रूप में प्रयोग होता है। व्यावहारिक प्रणालियों में इसे अधिकतर Huffman कोडिंग ने प्रतिस्थापित कर दिया है, जो इष्टतम कोड की गारंटी देता है। फिर भी कंप्रेशन की बुनियादी अवधारणाएँ समझने के लिए यह बहुत उपयोगी है।
// हल किया गया उदाहरण
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// कोड उदाहरण
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> और प्रश्न
प्र: Shannon-Fano हफ़मैन से कैसे अलग है?
उ: Shannon-Fano क्रमबद्ध सूची को ऊपर से नीचे ऐसे दो भागों में बाँटता है जिनकी आवृत्ति-योग लगभग बराबर हों; हफ़मैन सबसे दुर्लभ प्रतीकों को मिलाकर नीचे से ऊपर ट्री बनाता है। हफ़मैन का इष्टतम होना सिद्ध है, Shannon-Fano का हमेशा नहीं।
प्र: क्या Shannon-Fano हमेशा इष्टतम है?
उ: नहीं। उदाहरण में इसे 89 बिट लगते हैं जबकि हफ़मैन को 87। दोनों प्रीफ़िक्स-मुक्त कोड देते हैं, पर Shannon-Fano का विभाजन-नियम प्रतिकूल विभाजन चुन सकता है।
प्र: Shannon-Fano कहाँ उपयोग होता है?
उ: मुख्यतः ऐतिहासिक और शैक्षिक विधि के रूप में (Claude Shannon और Robert Fano, 1948/49)। ZIP के IMPLODE एल्गोरिदम में इसका एक रूप है; आधुनिक कंप्रेसर हफ़मैन या अंकगणितीय कोडिंग उपयोग करते हैं।