डेटा स्ट्रक्चर में हफमैन कोड और एन्ट्रॉपी

हफमैन कोड (Huffman Code)

हफमैन कोड को एक विशेष प्रकार के इष्टतम प्रीफिक्स कोड (Optimal Prefix Code) के रूप में परिभाषित किया जाता है जो आमतौर पर लॉसलेस डेटा संपीड़न (Lossless Data Compression) के लिए उपयोग किया जाता है।

ऐसे कोड को खोजने या लागू करने की प्रक्रिया हफमैन कोडिंग (Huffman Coding) नामक एक एल्गोरिदम द्वारा होती है, जिसे डेविड ए. हफमैन (David A. Huffman) द्वारा विकसित किया गया था जब वह MIT में Sc.D. छात्र थे, और 1952 के पेपर "A Method for the Construction of Minimum-Redundancy Codes" में प्रकाशित हुआ था।

हफमैन के एल्गोरिदम का आउटपुट एक स्रोत प्रतीक (Source Symbol) (जैसे फ़ाइल में एक वर्ण) को एन्कोड करने के लिए एक परिवर्तनीय-लंबाई कोड टेबल (Variable-length Code Table) के रूप में प्रदर्शित किया जा सकता है। एल्गोरिदम इस टेबल को स्रोत प्रतीक के प्रत्येक संभावित मान के लिए अनुमानित संभावना या घटना की आवृत्ति (वजन) से बनाता है। अन्य एन्ट्रॉपी एन्कोडिंग विधियों की तरह, अधिक सामान्य प्रतीकों को आमतौर पर कम सामान्य प्रतीकों की तुलना में कम बिट्स का उपयोग करके दर्शाया जाता है। हफमैन की विधि को कुशलतापूर्वक लागू किया जा सकता है, यदि ये वजन सॉर्ट किए गए हैं तो इनपुट वजन की संख्या के रैखिक समय में कोड ढूंढना।

एन्ट्रॉपी (Entropy)

सूचना सिद्धांत (Information Theory) में, शैनन का स्रोत कोडिंग प्रमेय (Shannon's Source Coding Theorem) (या नॉइज़लेस कोडिंग प्रमेय) डेटा संपीड़न की संभावित सीमाओं को स्थापित करने में सक्षम है, और शैनन एन्ट्रॉपी (Shannon Entropy) का परिचालन अर्थ।

स्रोत कोडिंग प्रमेय दर्शाता है कि (सीमा में, जैसे-जैसे स्वतंत्र और समान रूप से वितरित यादृच्छिक चर (i.i.d.) डेटा की एक स्ट्रीम की लंबाई अनंत की ओर प्रवृत्त होती है) डेटा को इस तरह संपीड़ित करना संभव नहीं है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) स्रोत की शैनन एन्ट्रॉपी से छोटी हो, बिना यह लगभग निश्चित हुए कि जानकारी खो जाएगी। हालांकि, कोड दर को नगण्य हानि संभावना के साथ शैनन एन्ट्रॉपी के मनमाने ढंग से करीब प्राप्त करना संभव है।

सूचना एन्ट्रॉपी को स्टोकेस्टिक डेटा स्रोत द्वारा जानकारी उत्पन्न की जाने वाली औसत दर के रूप में परिभाषित किया जाता है।

यादृच्छिक चर के लिए एन्ट्रॉपी की गणना (Calculate the Entropy for a Random Variable)

हम यह भी गणना कर सकते हैं कि एक यादृच्छिक चर में कितनी जानकारी है।

उदाहरण के लिए, यदि हम संभावना वितरण p के साथ यादृच्छिक चर X के लिए जानकारी की गणना करना चाहते हैं, तो इसे H() फंक्शन के रूप में लिखा जा सकता है; उदाहरण के लिए: H(X)

प्रभाव में, यादृच्छिक चर के लिए जानकारी की गणना यादृच्छिक चर के घटनाओं के संभावना वितरण के लिए जानकारी की गणना के समान है।

यादृच्छिक चर के लिए जानकारी की गणना को "सूचना एन्ट्रॉपी" (Information Entropy), "शैनन एन्ट्रॉपी" (Shannon Entropy), या बस "एन्ट्रॉपी" (Entropy) कहा जाता है।

यह भौतिकी से एन्ट्रॉपी के विचार से सादृश्य द्वारा संबंधित है, इसमें दोनों अनिश्चितता (Uncertainty) शब्द से संबंधित हैं।

एन्ट्रॉपी के लिए अंतर्ज्ञान यह है कि इसे यादृच्छिक चर के संभावना वितरण से निकाले गए घटना को प्रस्तुत या संचारित करने के लिए आवश्यक बिट्स की औसत संख्या के रूप में परिभाषित किया जाता है।

एक वितरण की शैनन एन्ट्रॉपी को उस वितरण से निकाले गए घटना में अपेक्षित जानकारी की मात्रा के रूप में परिभाषित किया जाता है।

यह वितरण P से निकाले गए प्रतीकों को एन्कोड करने के लिए औसतन आवश्यक बिट्स की संख्या पर निचली सीमा (Lower Bound) प्रदान करता है।

एन्ट्रॉपी की गणना K असतत अवस्थाओं (Discrete States) वाले यादृच्छिक चर X के लिए निम्नानुसार की जा सकती है:

H(X) = -∑ (प्रत्येक k ∈ K के लिए p(k) * log(p(k)))

इसका अर्थ है प्रत्येक घटना की संभावना का योग, जिसे उस घटना की संभावना के लॉग से गुणा किया गया है, का ऋणात्मक।

जानकारी की तरह, log() फंक्शन बेस-2 (Base-2) का उपयोग करता है और इकाइयां बिट्स (Bits) हैं। प्राकृतिक लघुगणक (Natural Logarithm) का भी उपयोग किया जा सकता है।

सबसे कम एन्ट्रॉपी एक यादृच्छिक चर के लिए गणना की जाती है जिसमें 1.0 की संभावना के साथ एकल घटना होती है, एक निश्चितता। यादृच्छिक चर के लिए सबसे बड़ी एन्ट्रॉपी संभव होगी यदि सभी घटनाएं समान रूप से संभावित हों।