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

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

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

डेटा संपीड़न में, पूर्णांकों के लिए एक सार्वभौमिक कोड एक उपसर्ग कोड होता है जो सकारात्मक पूर्णांकों को बाइनरी कोडवर्ड पर मैप करता है, अतिरिक्त संपत्ति के साथ कि पूर्णांकों पर वास्तविक संभाव्यता वितरण जो भी हो, जब तक कि वितरण मोनोटोनिक है (यानी, पी) (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.