गोलोम्ब कोडिंग

गोलोम्ब कोडिंग 1960 के दशक में सोलोमन डब्ल्यू. गोलोम्ब द्वारा आविष्कृत डेटा संपीड़न कोड के परिवार का उपयोग करके दोषरहित डेटा संपीड़न विधि है। ज्यामितीय वितरण का अनुसरण करने वाले अक्षरों में इष्टतम उपसर्ग कोड के रूप में गोलोम्ब कोड होगा, गोलोम्ब कोडिंग को उन स्थितियों के लिए अत्यधिक उपयुक्त बनाना जहां इनपुट स्ट्रीम में छोटे मानों की घटना बड़े मानों की तुलना में काफी अधिक होने की संभावना है।

चावल कोडिंग

राइस कोडिंग (रॉबर्ट एफ. राइस द्वारा आविष्कार) सरल (लेकिन संभवतः उप-इष्टतम) उपसर्ग कोड का उत्पादन करने के लिए गोलोम्ब कोड के परिवार के सबसेट का उपयोग करने को दर्शाता है। राइस ने कोड के इस सेट का उपयोग अनुकूली कोडिंग योजना में किया; राइस कोडिंग या तो उस अनुकूली योजना को संदर्भित कर सकती है या गोलोम्ब कोड के उस सबसेट का उपयोग कर सकती है। जबकि गोलोम्ब कोड में ट्यून करने योग्य पैरामीटर होता है जो कोई भी सकारात्मक पूर्णांक मान हो सकता है, राइस कोड वे होते हैं जिनमें ट्यून करने योग्य पैरामीटर दो की शक्ति है। यह राइस कोड को कंप्यूटर पर उपयोग के लिए सुविधाजनक बनाता है क्योंकि 2 से गुणा और भाग को बाइनरी अंकगणित में अधिक कुशलता से लागू किया जा सकता है।

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

राइस कोडिंग का उपयोग कई दोषरहित छवि संपीड़न और ऑडियो डेटा संपीड़न विधियों में एन्ट्रापी एन्कोडिंग चरण के रूप में किया जाता है।

सिंहावलोकन

पैरामीटर के साथ, ज्यामितीय वितरण के साथ स्रोत x के लिए गोलोम्ब कोडिंग उदाहरण p(0) = 0.2, गोलोम्ब कोड का उपयोग करते हुए M = 3. 2-बिट कोड 00 का उपयोग 20% समय किया जाता है; 3-बिट कोड 010, 011, और 100 का उपयोग 38% से अधिक समय में किया जाता है; बहुत कम मामलों में 4 बिट या अधिक की आवश्यकता होती है। इस स्रोत के लिए, एन्ट्रापी = 3.610 बिट्स; इस स्रोत के साथ इस कोड के लिए, दर = 3.639 बिट्स; इसलिए अतिरेक = 0.030 बिट्स, या दक्षता = 0.992 बिट्स प्रति बिट।

कोडों का निर्माण

गोलोम्ब कोडिंग ट्यून करने योग्य पैरामीटर का उपयोग करती है M किसी इनपुट मान को विभाजित करने के लिए xदो भागों में: q, द्वारा विभाजन का परिणाम M, और r, शेष। भागफल को यूनरी कोडिंग में भेजा जाता है, इसके बाद शेष को काटे संक्षिप्त बाइनरी एन्कोडिंग में भेजा जाता है। कब $M=1$, गोलोम्ब कोडिंग यूनरी कोडिंग के बराबर है।

गोलोम्ब-चावल कोड को ऐसे कोड के रूप में माना जा सकता है जो बिन की स्थिति के आधार पर संख्या दर्शाते हैं (q), और बिन के भीतर ऑफसेट (r). उदाहरण चित्र स्थिति दर्शाता है q और ऑफसेट r पूर्णांक की एन्कोडिंग के लिए x गोलोम्ब-राइस पैरामीटर का उपयोग करना M = 3, ज्यामितीय वितरण के बाद स्रोत संभावनाओं के साथ p(0) = 0.2.

औपचारिक रूप से, दोनों भाग निम्नलिखित अभिव्यक्ति द्वारा दिए गए हैं, जहाँ x क्या गैर-ऋणात्मक पूर्णांक को एन्कोड किया जा रहा है:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

और

$r=x-qM$.

यह छवि, गोलोम्ब कोड की, बिट्स में, अतिरेक को दर्शाती है Mके लिए इष्टतम रूप से चुना गया है 1 − p(0) ≥ 0.45

दोनों q और r बिट्स की परिवर्तनीय संख्याओं का उपयोग करके एन्कोड किया जाएगा: q यूनरी कोड द्वारा, और r द्वारा b राइस कोड के लिए बिट्स, या इनमें से कोई विकल्प b और b+1 गोलोम्ब कोड के लिए बिट्स (अर्थात्। M 2) की घात नहीं है $b=\lfloor \log _{2}(M)\rfloor$. अगर $r<2^{b+1}-M$, फिर उपयोग करें b एन्कोड करने के लिए बिट्स r; अन्यथा, उपयोग करें b+1 बिट एन्कोड करने के लिए r. स्पष्ट रूप से, $b=\log _{2}(M)$ अगर M 2 की घात है और हम इसके सभी मानों को एन्कोड कर सकते हैं r साथ b बिट्स.

पूर्णांक x गोलोम्ब द्वारा उपचारित बर्नौली प्रक्रिया की रन लंबाई थी, जिसका ज्यामितीय वितरण 0 से शुरू होता है। पैरामीटर का सबसे अच्छा विकल्प M संगत बर्नौली प्रक्रिया का फ़ंक्शन है, जिसे पैरामीटराइज़ किया गया है $p=P(x=0)$ किसी दिए गए बर्नौली परीक्षण में सफलता की संभावना। M या तो वितरण का माध्यिका है या माध्यिका ±1। इसे इन असमानताओं द्वारा निर्धारित किया जा सकता है:

$(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$

जिनका समाधान किया जाता है

$M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil$.

उदाहरण के लिए p(0) = 0.2:

$M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3$.

इस वितरण के लिए गोलोम्ब कोड समान संभावनाओं के लिए हफ़मैन कोड के बराबर है, यदि स्रोत मानों के अनंत सेट के लिए हफ़मैन कोड की गणना करना संभव हो।

हस्ताक्षरित पूर्णांकों के साथ प्रयोग करें

गोलोम्ब की योजना गैर-नकारात्मक संख्याओं के अनुक्रमों को एन्कोड करने के लिए डिज़ाइन की गई थी। हालाँकि, इसे ओवरलैप और इंटरलीव योजना का उपयोग करके नकारात्मक संख्याओं वाले अनुक्रमों को स्वीकार करने के लिए आसानी से बढ़ाया जाता है, जिसमें सभी मानों को अद्वितीय और प्रतिवर्ती तरीके से कुछ सकारात्मक संख्या में पुन: असाइन किया जाता है। अनुक्रम शुरू होता है: 0, −1, 1, −2, 2, −3, 3, −4, 4... n-वां नकारात्मक मान (यानी, $-n$) को n पर मैप किया गया है^वेंविषम संख्या ($2n-1$), और उन्हें^वेंधनात्मक मान को एम-वें सम संख्या में मैप किया जाता है ($2m$). इसे गणितीय रूप से इस प्रकार व्यक्त किया जा सकता है: सकारात्मक मान x को मैप किया गया है ($x'=2|x|=2x,\ x\geq 0$), और नकारात्मक मान y को मैप किया गया है ($y'=2|y|-1=-2y-1,\ y<0$). इस तरह के कोड का उपयोग सरलता के लिए किया जा सकता है, भले ही यह उप-इष्टतम हो। वास्तव में दो-तरफा ज्यामितीय वितरण के लिए इष्टतम कोड में इस सहित वितरण मापदंडों के आधार पर गोलोम्ब कोड के कई प्रकार शामिल हैं।

सरल एल्गोरिथ्म

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

1. पैरामीटर M को पूर्णांक मान पर ठीक करें।
2. N के लिए, एन्कोड किया जाने वाला नंबर ढूंढें
   1. भागफल = q = मंजिल(एन/एम)
   2. शेष = आर = एन मोडुलो एम
3. कोडवर्ड जेनरेट करें
   1. कोड प्रारूप: <कोटिएंट कोड><शेष कोड>, कहां
   2. कोटिएंट कोड (यूनरी कोडिंग में)
      1. 1 बिट्स की क्यू-लंबाई स्ट्रिंग लिखें (वैकल्पिक रूप से, 0 बिट्स की)
      2. 0 बिट लिखें (क्रमशः, 1 बिट)
   3. शेष कोड (काटे गए बाइनरी एन्कोडिंग में)
      1. होने देना $b=\lfloor \log _{2}(M)\rfloor$
         1. अगर $r<2^{b+1}-M$ बी बिट्स का उपयोग करके बाइनरी प्रतिनिधित्व में कोड आर।
         2. अगर $r\geq 2^{b+1}-M$ नंबर कोड करें $r+2^{b+1}-M$ बी + 1 बिट्स का उपयोग करके बाइनरी प्रतिनिधित्व में।

डिकोडिंग:

1. q के एकल प्रतिनिधित्व को डिकोड करें (कोड की शुरुआत में 1 की संख्या गिनें)
2. 0 सीमांकक छोड़ें
3. होने देना $b=\lfloor \log _{2}(M)\rfloor$
   1. अगले बी बिट्स को बाइनरी नंबर आर' के रूप में समझें। अगर $r'<2^{b+1}-M$ रखता है, फिर अनुस्मारक $r=r'$
   2. अन्यथा b + 1 बिट्स को बाइनरी नंबर r' के रूप में समझें, अनुस्मारक द्वारा दिया गया है $r=r'-2^{b+1}+M$
4. गणना करें $N=q*M+r$

उदाहरण

तय करना M = 10. इस प्रकार $b=\lfloor \log _{2}(10)\rfloor =3$. कटऑफ है $2^{b+1}-M=16-10=6$.

Encoding of quotient part q output bits 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 $\vdots$ $\vdots$ N $\underbrace {111\cdots 111} _{N}0$

Encoding of remainder part r offset binary output bits 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

उदाहरण के लिए, पैरामीटर का उपयोग करके राइस-गोलोम्ब एन्कोडिंग के साथ M = 10, दशमलव संख्या 42 को पहले विभाजित किया जाएगा q=4 और r = 2, और qcode के रूप में एन्कोड किया जाएगा(q),आरकोड(r) = qcode(4),rcode(2) = 11110,010 (आपको आउटपुट स्ट्रीम में अलग करने वाले अल्पविराम को एनकोड करने की आवश्यकता नहीं है, क्योंकि के अंत में 0 है q कोड कब कहने के लिए पर्याप्त है q समाप्त होता है और r शुरू करना ; क्यूकोड और आरकोड दोनों स्व-सीमांकित हैं)।

रन-लेंथ एन्कोडिंग के लिए उपयोग करें

ध्यान दें कि p और 1 – p पिछले अनुभागों में उपयोग की तुलना में इस अनुभाग में उलट दिया गया है।

दो प्रतीकों की वर्णमाला, या दो घटनाओं, पी और क्यू का सेट, संभावनाओं के साथ पी और (1 − p) क्रमशः, कहाँ p ≥ 1/2, गोलोम्ब कोडिंग का उपयोग एकल Q′s द्वारा अलग किए गए शून्य या अधिक P′s के रन को एन्कोड करने के लिए किया जा सकता है। इस एप्लिकेशन में, पैरामीटर एम की सबसे अच्छी सेटिंग निकटतम पूर्णांक है $-{\frac {1}{\log _{2}p}}$. जब पी = 1/2, एम = 1, और गोलोम्ब कोड यूनरी से मेल खाता है (n ≥ 0 P′s के बाद Q आता है, इसे n के रूप में एन्कोड किया जाता है जिसके बाद शून्य आता है)। यदि सरल कोड वांछित है, तो कोई गोलोम्ब-राइस पैरामीटर निर्दिष्ट कर सकता है b (यानी, गोलोम्ब पैरामीटर $M=2^{b}$) के निकटतम पूर्णांक तक $-\log _{2}(-\log _{2}p)$; हालाँकि यह हमेशा सबसे अच्छा पैरामीटर नहीं होता है, यह आमतौर पर सबसे अच्छा राइस पैरामीटर होता है और इसका संपीड़न प्रदर्शन इष्टतम गोलोम्ब कोड के काफी करीब होता है। (राइस ने स्वयं ही डेटा के लिए विभिन्न कोड का उपयोग करने का प्रस्ताव दिया ताकि यह पता लगाया जा सके कि कौन सा सबसे अच्छा था। बाद में जेट प्रोपल्शन प्रयोगशाला के शोधकर्ता ने कोड पैरामीटर को अनुकूलित करने या अनुमान लगाने के विभिन्न तरीकों का प्रस्ताव दिया।)

बाइनरी भाग वाले राइस कोड का उपयोग करने पर विचार करें b बिट्स रन-लेंथ एन्कोड अनुक्रमों के लिए जहां पी की संभावना है p. अगर $\mathbb {P} [{\text{bit is part of }}k{\text{-run}}]$ संभावना है कि बिट का हिस्सा होगा k-बिट रन ($k-1$ पीएस और क्यू) और $({\text{compression ratio of }}k{\text{-run}})$ उस रन का संपीड़न अनुपात है, तो अपेक्षित संपीड़न अनुपात है

${\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}$

संपीड़न को अक्सर के रूप में व्यक्त किया जाता है $1-\mathbb {E} [{\text{compression ratio}}]$, अनुपात संकुचित। के लिए $p\approx 1$, रन-लेंथ कोडिंग दृष्टिकोण के परिणामस्वरूप एन्ट्रॉपी (सूचना सिद्धांत) के करीब संपीड़न अनुपात होता है। उदाहरण के लिए, राइस कोड का उपयोग करना $b=6$ के लिए $p=0.99$ पैदावार 91.89% संपीड़न, जबकि एन्ट्रापी सीमा है 91.92%.

अनुकूली रन-लंबाई गोलोम्ब-राइस एन्कोडिंग

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

पूर्णांक डेटा को कुशलतापूर्वक एनकोड करने के लिए वैकल्पिक तरीका जिसका पीडीएफ ज्ञात नहीं है, या भिन्न हो रहा है, बैकवर्ड-अनुकूली एनकोडर का उपयोग करना है। run-length Golomb-Rice (RLGR) कोड बहुत ही सरल एल्गोरिदम का उपयोग करके इसे प्राप्त करता है जो Golomb-Rice पैरामीटर को ऊपर या नीचे समायोजित करता है, जो निर्भर करता है अंतिम एन्कोडेड प्रतीक. डिकोडर एन्कोडिंग मापदंडों की भिन्नता को ट्रैक करने के लिए उसी नियम का पालन कर सकता है, इसलिए किसी भी अतिरिक्त जानकारी को प्रसारित करने की आवश्यकता नहीं है, केवल एन्कोडेड डेटा। सामान्यीकृत गॉसियन पीडीएफ को मानते हुए, जो डेटा में देखे गए आंकड़ों की विस्तृत श्रृंखला को कवर करता है जैसे कि भविष्यवाणी त्रुटियां या मल्टीमीडिया कोडेक्स में गुणांक बदलना, आरएलजीआर एन्कोडिंग एल्गोरिदम ऐसे अनुप्रयोगों में बहुत अच्छा प्रदर्शन कर सकता है।

अनुप्रयोग

गोलोम्ब-कोडित चावल एल्गोरिदम प्रयोग संपीड़न अनुपात

कई सिग्नल कोडेक्स भविष्यवाणी अवशेषों के लिए राइस कोड का उपयोग करते हैं।

भविष्य कहनेवाला एल्गोरिदम में, ऐसे अवशेष दो-तरफा ज्यामितीय वितरण में आते हैं, जिसमें छोटे अवशेष बड़े अवशेषों की तुलना में अधिक बार होते हैं, और राइस कोड हफ़मैन तालिका को प्रसारित करने के ओवरहेड के बिना इस तरह के वितरण के लिए हफ़मैन कोड का बारीकी से अनुमान लगाता है। . एक संकेत जो ज्यामितीय वितरण से मेल नहीं खाता है वह साइन तरंग है, क्योंकि विभेदक अवशेष साइनसॉइडल सिग्नल बनाते हैं जिनके मान ज्यामितीय वितरण नहीं बना रहे हैं (उच्चतम और निम्नतम अवशेष मूल्यों में घटनाओं की समान उच्च आवृत्ति होती है, केवल औसत सकारात्मक और नकारात्मक होता है) अवशेष कम बार मिलते हैं)।

कई दोषरहित ऑडियो डेटा संपीड़न, जैसे शॉर्टन (फ़ाइल प्रारूप), एफएलएसी, Apple लॉसलेस, और MPEG-4 ALS, रैखिक भविष्य कहनेवाला कोडिंग (Apple लॉसलेस में एडाप्टिव FIR फ़िल्टर कहा जाता है) के बाद राइस कोड का उपयोग करते हैं। राइस कोडिंग का उपयोग FELICS दोषरहित छवि कोडेक में भी किया जाता है।

गोलोम्ब-राइस कोडर का उपयोग चावल एल्गोरिथ्म आधारित दोषरहित छवि कोडेक्स के एन्ट्रापी कोडिंग चरण में किया जाता है। ऐसा ही प्रयोग दिखाया गया संपीड़न अनुपात ग्राफ़ उत्पन्न करता है।

दोषरहित JPEG#JPEG-LS|JPEG-LS योजना पूर्वानुमान अवशेषों को एनकोड करने के लिए राइस-गोलोम्ब का उपयोग करती है।

run-length Golomb–Rice (RLGR) Golomb-Rice कोडिंग का ऊपर उल्लिखित अनुकूली संस्करण, वर्चुअल मशीनों में स्क्रीन सामग्री को एन्कोड करने के लिए उपयोग किया जाता है। माइक्रोसॉफ्ट रिमोट डेस्कटॉप प्रोटोकॉल का रिमोटएफएक्स घटक।

यह भी देखें

• इलियास डेल्टा कोडिंग

अग्रिम पठन

• Golomb, Solomon W. (1966). Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data". IEEE Transactions on Communications. 16 (9): 889–897. doi:10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979), , "Some Practical Universal Noiseless Coding Techniques", Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, March 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
• David Salomon. "Data Compression",ISBN 0-387-95045-1.
• H. S. Malvar, Adaptive run-length/Golomb–Rice encoding of quantized generalized Gaussian sources with unknown statistics, Proc. Data Compression Conference, 2006.
• RLGR Entropy Encoding, Microsoft MS-RDPRFX Open Specification, RemoteFX codec for Remote Desktop Protocol.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines Archived 2020-10-05 at the Wayback Machine. MIT Press, Cambridge MA, 2010.