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

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

राइस 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.