हफमैन कोड
एक हफ़मैन कोड को एक विशेष प्रकार के इष्टतम उपसर्ग कोड के रूप में परिभाषित किया जाता है जो आमतौर पर दोषरहित डेटा संपीड़न के लिए उपयोग किया जाता है।
इस तरह के कोड को खोजने या लागू करने की प्रक्रिया हफ़मैन कोडिंग के माध्यम से आगे बढ़ती है, एक एल्गोरिथम जिसे डेविड ए। हफ़मैन द्वारा विकसित किया गया था, जब वह एक Sc.D था। एमआईटी में छात्र, और 1952 के पेपर "न्यूनतम-रिडंडेंसी कोड के निर्माण के लिए एक विधि" में प्रकाशित हुआ।
हफ़मैन के एल्गोरिथम से आउटपुट को स्रोत प्रतीक (जैसे फ़ाइल में एक वर्ण) को एन्कोड करने के लिए एक चर-लंबाई कोड तालिका के रूप में प्रदर्शित किया जा सकता है। एल्गोरिदम इस तालिका को स्रोत प्रतीक के प्रत्येक संभावित मूल्य के लिए अनुमानित संभावना या घटना की आवृत्ति (वजन) से बनाता है। अन्य एन्ट्रापी एन्कोडिंग विधियों की तरह, अधिक सामान्य प्रतीकों को आम तौर पर कम सामान्य प्रतीकों की तुलना में कम बिट्स को लागू करने का प्रतिनिधित्व किया जाता है। हफ़मैन की विधि को कुशलता से लागू किया जा सकता है, यदि इन वज़न को क्रमबद्ध किया जाता है, तो इनपुट वज़न की संख्या के लिए रैखिक समय में एक कोड ढूँढना।
एंट्रॉपी
सूचना सिद्धांत में, शैनन का स्रोत कोडिंग प्रमेय (या नीरव कोडिंग प्रमेय) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रापी के संचालनात्मक अर्थ को स्थापित करने में सक्षम है।
स्रोत कोडिंग प्रमेय प्रदर्शित करता है कि (सीमा में, स्वतंत्र और समान रूप से वितरित यादृच्छिक चर (i.i.d.) डेटा की एक धारा की लंबाई अनंत तक जाती है) डेटा को इस तरह संपीड़ित करना संभव नहीं है कि कोड दर (औसत संख्या) बिट्स प्रति प्रतीक) स्रोत के शैनन एन्ट्रापी से छोटा है, बिना यह सुनिश्चित किए कि जानकारी खो जाएगी। हालांकि, नुकसान की नगण्य संभावना के साथ, मनमाने ढंग से शैनन एन्ट्रापी के करीब कोड दर प्राप्त करना संभव है।
सूचना एन्ट्रापी को उस औसत दर के रूप में परिभाषित किया जाता है जिस पर डेटा के एक स्टोकेस्टिक स्रोत द्वारा सूचना का उत्पादन किया जाता है।
यादृच्छिक चर के लिए एन्ट्रॉपी की गणना करें
हम यह भी गणना कर सकते हैं कि यादृच्छिक चर में कितनी जानकारी है।
उदाहरण के लिए, यदि हम संभाव्यता वितरण p के साथ एक यादृच्छिक चर X के लिए जानकारी की गणना करना चाहते हैं, तो इसे एक फ़ंक्शन H () के रूप में लिखा जा सकता है; उदाहरण के लिए:एच(एक्स)
वास्तव में, एक यादृच्छिक चर के लिए जानकारी की गणना करना यादृच्छिक चर के लिए घटनाओं के संभाव्यता वितरण के लिए जानकारी की गणना करने के समान है।
एक यादृच्छिक चर के लिए जानकारी की गणना करना "सूचना एन्ट्रॉपी," "शैनन एन्ट्रॉपी," या बस "एन्ट्रॉपी" के रूप में दर्शाया गया है।
यह सादृश्य द्वारा भौतिकी से एन्ट्रापी के विचार से संबंधित है, जिसमें दोनों अनिश्चितता शब्द से संबंधित हैं।
एन्ट्रापी के लिए अंतर्ज्ञान यह है कि इसे यादृच्छिक चर के लिए संभाव्यता वितरण से खींची गई घटना का प्रतिनिधित्व करने या प्रसारित करने के लिए आवश्यक बिट्स की औसत संख्या के रूप में परिभाषित किया गया है।
किसी वितरण की शैनन एन्ट्रॉपी को उस वितरण से ली गई घटना में अपेक्षित जानकारी की मात्रा के रूप में परिभाषित किया जाता है।
यह वितरण पी से खींचे गए प्रतीकों को सांकेतिक शब्दों में बदलने के लिए औसतन आवश्यक बिट्स की संख्या पर एक निचली सीमा प्रदान करता है।
K असतत अवस्थाओं में k के साथ एक यादृच्छिक चर X के लिए एन्ट्रॉपी की गणना निम्नानुसार की जा सकती है
H(X) = -sum(each k in K p(k) * log(p(k)))
इसका मतलब है कि प्रत्येक घटना की संभावना के योग को प्रत्येक घटना की संभावना के लॉग से गुणा किया जाता है।
जानकारी की तरह, लॉग () फ़ंक्शन बेस -2 को लागू करता है और इकाइयाँ बिट्स होती हैं। इसके बजाय एक प्राकृतिक लघुगणक लागू किया जा सकता है।
सबसे कम एन्ट्रापी की गणना एक यादृच्छिक चर के लिए की जाती है जिसमें 1.0 की संभावना के साथ एक एकल घटना होती है, एक निश्चितता। एक यादृच्छिक चर के लिए सबसे बड़ी एन्ट्रॉपी संभव होगी यदि सभी घटनाओं को समान रूप से समान रूप से किया जाता है।