यूनिवर्सल कोड (डेटा कम्प्रेशन)

फाइबोनैचि, एलियास गामा, और एलियास डेल्टा बनाम बाइनरी कूटलेखन

k = 2, 3, 4, 5, 8, 16 बनाम बाइनरी वाला चावल

आंकड़ा संकुलन में, पूर्णांकों के लिए एक सार्वभौमिक कूट एक पूर्वलग्न कूट होता है जो सकारात्मक पूर्णांकों को बाइनरी(द्विआधारी) कूट शब्द पर मैप करता है, अतिरिक्त गुण के साथ कि पूर्णांकों पर वास्तविक संभाव्यता वितरण जो भी हो, जब तक कि वितरण मोनोटोनिक है (i.e., p(i) ≥ p(i + 1) सभी सकारात्मक i के लिए), कूट शब्द की अपेक्षित मान लंबाई अपेक्षित लंबाई के एक स्थिर कारक के भीतर है उस संभाव्यता वितरण के लिए इष्टतम कूट निर्दिष्ट किया गया होगा। एक सार्वभौमिक कूट असममित रूप से इष्टतम होता है यदि वास्तविक और इष्टतम अपेक्षित लंबाई के बीच का अनुपात कूट की सूचना एन्ट्रॉपी के एक फलन द्वारा घिरा होता है, जो बंधे होने के अतिरिक्त, 1 तक पहुंचता है क्योंकि एन्ट्रॉपी अनंत तक पहुंचती है।

सामान्यत:, पूर्णांकों के लिए अधिकांश पूर्वलग्न कूट बड़े पूर्णांकों के लिए लंबे कूट शब्द निर्दिष्ट करते हैं। इस तरह के कूट का उपयोग संभावित संदेशों के एक सेट से निकाले गए संदेश को कुशलतापूर्वक संप्रेषित करने के लिए किया जा सकता है, संभाव्यता को कम करके संदेशों के सेट को क्रमबद्ध करके और फिर इच्छित संदेश का सूचकांक भेजकर, यूनिवर्सल कूट सामान्यत: सटीक रूप से ज्ञात संभाव्यता वितरण के लिए उपयोग नहीं किए जाते हैं, और कोई भी यूनिवर्सल कूट प्रक्रिया में उपयोग किए जाने वाले किसी भी वितरण के लिए इष्टतम नहीं माना जाता है।

एक सार्वभौमिक कूट को सार्वभौमिक स्रोत कूटलेखन के साथ भ्रमित नहीं किया जाना चाहिए, जिसमें आंकड़ा संकुलन विधि को एक निश्चित पूर्वलग्न कूट की आवश्यकता नहीं होती है और वास्तविक और इष्टतम अपेक्षित लंबाई के बीच का अनुपात एक होना चाहिए। चूंकि, ध्यान दें कि सार्वभौमिक स्रोत कोडिंग की एक विधि के रूप में, तेजी से बड़े ब्लॉकों का उपयोग करके, एक असम्बद्ध रूप से इष्टतम सार्वभौमिक कोड का उपयोग स्वतंत्र रूप से समान रूप से वितरित स्रोतों पर किया जा सकता है।

सार्वभौमिक और गैर-सार्वभौमिक कूट

ये पूर्णांकों के लिए कुछ सार्वभौमिक कूट हैं; एक तारांकन चिह्न (*) एक कूट को इंगित करता है जिसे शब्दावली क्रम में तुच्छ रूप से दोहराया जा सकता है, जबकि एक डबल डैगर( दुमुठ कटार (चिह्न)) (‡) एक ऐसे कूट को इंगित करता है जो स्पर्शोन्मुख रूप से इष्टतम है:

• इलियास गामा कूटलेखन*
• इलियास डेल्टा कूटलेखन* ‡
• इलियास ओमेगा कूटलेखन* ‡
• एक्सपोनेंशियल-गोलोम्ब कूटलेखन (एक्सप-गोलोम्ब कूटलेखन) *, जिसमें एक विशेष स्थिति के रूप में एलियास गामा कूटलेखन है। (H.264/MPEG-4 AVC में प्रयुक्त)
• फाइबोनैचि कूटलेखन
• लेवेनशेटिन कूटलेखन* ‡, मूल सार्वभौमिक कूटलेखन तकनीक [1]
• बाइट कूटलेखन जहाँ कूट के अंत को चिह्नित करने के लिए एक विशेष बिट पैटर्न (कम से कम दो बिट्स के साथ) का उपयोग किया जाता है - उदाहरण के लिए, यदि पूर्णांक को अधिक प्राकृतिक आधार 16 के अतिरिक्त आधार 15 में अंकों का प्रतिनिधित्व करने वाले निबल्स के अनुक्रम के रूप में एन्कोड किया गया है, तो पूर्णांक के अंत को इंगित करने के लिए उच्चतम निबल मान (अर्थात, बाइनरी में चार लोगों का अनुक्रम) का उपयोग किया जा सकता है।
• चर-लंबाई मात्रा

ये गैर-सार्वभौमिक हैं:

• यूनरी(एकअंगी) कोडिंग, जिसका उपयोग एलियास कूट में किया जाता है
• गोलोम्ब कूटलेखन, जिसका उपयोग एफएलएसी ऑडियो कोडेक में किया जाता है और जिसमें एक विशेष स्थिति के रूप में यूनरी कूटलेखन होती है।
• गोलोम्ब कूटलेखन, जिसमें विशेष स्थितियोंं के रूप में राइस कूटलेखन और यूनरी कूटलेखन है।

उनकी गैर-सार्वभौमिकता को यह देखकर देखा जा सकता है कि, यदि इनमें से किसी का उपयोग गॉस-कुज़मिन वितरण या ज़ेटा वितरण को पैरामीटर s=2 के साथ कूट करने के लिए किया जाता है, तो अपेक्षित कूट शब्द लंबाई अनंत है। उदाहरण के लिए, ज़ेटा वितरण पर यूनरी कूटलेखन का उपयोग करने से अपेक्षित लंबाई प्राप्त होती है

$E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,$

दूसरी ओर, गॉस-कुज़मिन वितरण के लिए सार्वभौमिक एलियास गामा कूटलेखन का उपयोग करने से एन्ट्रापी (लगभग 3.43 बिट्स) के निकट अपेक्षित कूट शब्द लंबाई (लगभग 3.51 बिट्स) प्राप्त होती है।http://scholar.google.com/scholar?cluster=13442560459874106744 - Академия Google।

व्यावहारिक संपीड़न से संबंध

हफ़मैन कूटलेखन और अंकगणित कूटलेखन (जब उनका उपयोग किया जा सकता है) किसी भी सार्वभौमिक कूट की तुलना में कम से कम अच्छा, और अधिकांशत: बेहतर संपीड़न देते हैं।

चूंकि, यूनिवर्सल कूट तब उपयोगी होते हैं जब हफ़मैन कूटलेखन का उपयोग नहीं किया जा सकता है - उदाहरण के लिए, जब कोई प्रत्येक संदेश की सटीक संभावना नहीं जानता है, लेकिन केवल उनकी संभावनाओं की रैंकिंग जानता है।

हफ़मैन कूट असुविधाजनक होने पर यूनिवर्सल कूट भी उपयोगी होते हैं। उदाहरण के लिए, जब ट्रांसमीटर नहीं बल्कि रिसीवर संदेशों की संभावनाओं को जानता है, तो हफ़मैन कूटलेखन के लिए उन संभावनाओं को रिसीवर तक प्रसारित करने के लिए ओवरहेड की आवश्यकता होती है। यूनिवर्सल कूट का उपयोग करने पर वह ओवरहेड नहीं होता है।

प्रत्येक सार्वभौमिक कूट, एक दूसरे के स्व-परिसीमन (पूर्वलग्न) बाइनरी कूट की तरह, इसका अपना निहित संभाव्यता वितरण होता है P(i)=2^−l(i) जहाँ l(i) ith कूट शब्द की लंबाई है और P(i) संबंधित प्रतीक की संभावना है। यदि वास्तविक संदेश संभावनाएँ Q(i) और कुल्बैक-लीबलर विचलन हैं $D_{\text{KL}}(Q\|P)$ कूट द्वारा न्यूनतम किया गया है l(i), तो संदेशों के उस सेट के लिए इष्टतम हफ़मैन कूट उस कूट के बराबर होगा। इसी तरह, कोई कूट इष्टतम के कितना करीब है, इसे इस विचलन से मापा जा सकता है। चूँकि यूनिवर्सल कूट हफ़मैन कूट (जो बदले में, अंकगणितीय एन्कूटलेखन की तुलना में सरल और तेज़ है) की तुलना में एन्कोड(कोडन) और डीकोड(विकोडन) करने में सरल और तेज़ होते हैं, यूनिवर्सल कूट उन स्थितियोंं में बेहतर होगा जहाँ $D_{\text{KL}}(Q\|P)$ पर्याप्त रूप से छोटा है. दोषरहित आंकड़ा संकुलन प्रोग्राम: हाइब्रिड LZ77 RLE

किसी भी ज्यामितीय वितरण (पूर्णांकों पर एक घातीय वितरण) के लिए, एक गोलोम्ब कूट इष्टतम है। सार्वभौमिक कूट के साथ, अंतर्निहित वितरण लगभग एक पावर नियम है जैसे $1/n^{2}$ (अधिक सटीक रूप से, एक Zipf वितरण)।

फाइबोनैचि कूट के लिए, अंतर्निहित वितरण लगभग है $1/n^{q}$, साथ

$q=1/\log _{2}(\varphi )\simeq 1.44,$

जिहाँ $\varphi$ स्वर्णिम अनुपात है. टर्नरी अल्पविराम कूट के लिए (अर्थात, आधार 3 में एन्कूटलेखन, प्रति प्रतीक 2 बिट्स के साथ दर्शाया गया है), अंतर्निहित वितरण एक पावर नियम है $q=1+\log _{3}(4/3)\simeq 1.26$. इस प्रकार इन वितरणों में उनके संबंधित पावर नियमों के साथ लगभग-इष्टतम कूट होते हैं।

बाहरी संबंध

• Data Compression, by Debra A. Lelewer and Daniel S. Hirschberg (University of California, Irvine)
• Information Theory, Inference, and Learning Algorithms, by David MacKay, has a chapter on codes for integers, including an introduction to Elias codes.
• Кодирование целых чисел has mostly English-language papers on universal and other integer codes.