असममित अंक प्रणाली

असममित अंक प्रणाली (एएनएस) जगियेलोनियन विश्वविद्यालय के जारोस्लाव डूडा द्वारा प्रारम्भ की गई एन्ट्रापी एन्कोडिंग विधियों का समूह होता है, जिसका उपयोग पिछले विधियों की तुलना में श्रेष्ट प्रदर्शन के कारण 2014 से डेटा संपीड़न में उपयोग किया जाता है। एएनएस हफ़मैन कोडिंग के समान प्रसंस्करण लागत के साथ अंकगणित कोडिंग (जो लगभग स्पष्ट संभाव्यता वितरण का उपयोग करता है) के संपीड़न अनुपात को जोड़ता है। सारणीबद्ध ANS (tANS) संस्करण में, इसे गुणन का उपयोग किए बिना बड़े वर्णमाला पर काम करने के लिए परिमित-अवस्था मशीन का निर्माण करके प्राप्त किया जाता है।

अन्य बातों के अतिरिक्त, ANS का उपयोग फेसबुक फेसबुक ज़ेडस्टैंडर्ड कंप्रेसर (उदाहरण के लिए लिनक्स कर्नेल, एंड्रॉइड ऑपरेटिंग सिस्टम में भी उपयोग किया जाता है जिसे एमआईएमई और एचटीटीपी के ​​लिए RFC 8478 के रूप में प्रकाशित किया गया था ), एप्पल इंक एलजेडएफएसई कंप्रेसर, गूगल ड्रेको 3डी कंप्रेसर (उदाहरण के लिए पिक्सर सार्वभौमिक दृश्य विवरण फॉर्मेट में उपयोग किया जाता है) और पीआईके छवि कंप्रेसर, सीआरएएम डीएनए कंप्रेसर सैमटूल्स उपयोगिताओं से, ड्रॉपबॉक् DivANS कंप्रेसर, माइक्रोसॉफ्ट डायरेक्टस्टोरेज बीसीपैक टेक्सचर कंप्रेसर, और जेपीईजी एक्सएल छवि कंप्रेसर इत्यादि में किया जाता है।

मूल विचार जानकारी को प्राकृतिक संख्या में एन्कोड करना है $x$. मानक बाइनरी संख्या प्रणाली में, हम थोड़ा सा जोड़ सकते हैं $s\in \{0,1\}$ को जानकारी का $x$ जोड़कर $s$ के अंत में $x$, जो हमें देता है $x'=2x+s$. एन्ट्रॉपी कोडर के लिए, यह इष्टतम है यदि $\Pr(0)=\Pr(1)=1/2$. ANS इस प्रक्रिया को प्रतीकों के मनमाने सेट के लिए सामान्यीकृत करता है $s\in S$ संभाव्यता वितरण के साथ $(p_{s})_{s\in S}$. ANS में, यदि से जानकारी $s$ से जोड़ा गया है $x$ इसके परिणाम में $x'$, तब $x'\approx x\cdot p_{s}^{-1}$. समान रूप से, $\log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})$, कहाँ $\log _{2}(x)$ संख्या में संग्रहीत जानकारी के बिट्स की संख्या है $x$, और $\log _{2}(1/p_{s})$ प्रतीक में निहित बिट्स की संख्या है $s$.

एन्कोडिंग नियम के लिए, प्राकृतिक संख्याओं के सेट को विभिन्न प्रतीकों के अनुरूप असंयुक्त उपसमूहों में विभाजित किया गया है – सम और विषम संख्याओं की तरह, लेकिन एन्कोड करने के लिए प्रतीकों की संभाव्यता वितरण के अनुरूप घनत्व के साथ। फिर सिंबल से जानकारी जोड़ना है $s$ वर्तमान संख्या में पहले से ही संग्रहीत जानकारी में $x$, हम नंबर पर जाते हैं $x'=C(x,s)\approx x/p$ की स्थिति होने के नाते $x$-वें से उपस्थिति $s$-वां उपसमुच्चय.

इसे व्यवहार में लागू करने के वैकल्पिक तरीके हैं – एन्कोडिंग और डिकोडिंग चरणों (यूएबीएस और आरएएनएस वेरिएंट) के लिए प्रत्यक्ष गणितीय सूत्र, या कोई संपूर्ण व्यवहार को तालिका (टीएएनएस वेरिएंट) में डाल सकता है। रोकने के लिए पुनर्सामान्यीकरण का उपयोग किया जाता है $x$ अनंत तक जा रहा हूँ – संचित बिट्स को बिटस्ट्रीम में या उससे स्थानांतरित करना।

एंट्रॉपी कोडिंग

मान लीजिए कि 1,000 शून्य और का अनुक्रम एन्कोड किया जाएगा, जिसे सीधे स्टोर करने में 1000 बिट्स लगेंगे। हालाँकि, अगर यह किसी तरह ज्ञात हो कि इसमें केवल 1 शून्य और 999 हैं, तो यह शून्य की स्थिति को एनकोड करने के लिए पर्याप्त होगा, जिसके लिए केवल $\lceil \log _{2}(1000)\rceil \approx 10$ मूल 1000 बिट्स के बजाय यहां बिट्स।

आम तौर पर, ऐसी लंबाई $n$ अनुक्रम युक्त $pn$ शून्य और $(1-p)n$ वाले, कुछ संभावना के लिए $p\in (0,1)$, संयोजन कहलाते हैं। स्टर्लिंग सन्निकटन का उपयोग करके हमें उनकी स्पर्शोन्मुख संख्या प्राप्त होती है

${n \choose pn}\approx 2^{nh(p)}{\text{ for large }}n{\text{ and }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),$

एन्ट्रॉपी (सूचना सिद्धांत) कहा जाता है।

इसलिए, ऐसे किसी क्रम को चुनने के लिए हमें लगभग की आवश्यकता होती है $nh(p)$ बिट्स यह अब भी है $n$ बिट्स अगर $p=1/2$हालाँकि, यह बहुत छोटा भी हो सकता है। उदाहरण के लिए, हमें केवल इसकी आवश्यकता है $\approx n/2$ के लिए बिट्स $p=0.11$.

एन्ट्रॉपी एन्कोडिंग प्रति प्रतीक लगभग शैनन एन्ट्रॉपी बिट्स का उपयोग करके प्रतीकों के अनुक्रम के एन्कोडिंग की अनुमति देता है। उदाहरण के लिए, ANS का उपयोग सीधे संयोजनों की गणना करने के लिए किया जा सकता है: लगभग इष्टतम तरीके से निश्चित अनुपात वाले प्रतीकों के प्रत्येक अनुक्रम के लिए अलग प्राकृतिक संख्या निर्दिष्ट करें।

एन्कोडिंग संयोजनों के विपरीत, यह संभाव्यता वितरण आमतौर पर डेटा कंप्रेसर में भिन्न होता है। इस प्रयोजन के लिए, शैनन एन्ट्रॉपी को भारित औसत के रूप में देखा जा सकता है: संभाव्यता का प्रतीक $p$ रोकना $\log _{2}(1/p)$ जानकारी के टुकड़े. तथा जानकारी को प्राकृतिक संख्या में एन्कोड करें $x$, युक्त के रूप में व्याख्या की गई $\log _{2}(x)$ जानकारी के टुकड़े. संभाव्यता के प्रतीक से जानकारी जोड़ना $p$ इस सूचनात्मक सामग्री को बढ़ाता है $\log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)$. इसलिए, नए नंबर में दोनों जानकारी होनी चाहिए $x'\approx x/p$.

प्रेरक उदाहरण

1/2, 1/4, 1/4 प्रायिकता के साथ 3 अक्षरों ए, बी, सी वाले स्रोत पर विचार करें। बाइनरी में इष्टतम उपसर्ग कोड बनाना सरल है: ए = 0, बी = 10, सी = 11। फिर, संदेश को एबीसी -> 01011 के रूप में एन्कोड किया गया है।

हम देखते हैं कि एन्कोडिंग करने के लिए समकक्ष विधि इस प्रकार है:

• संख्या 1 से प्रारंभ करें, और प्रत्येक इनपुट अक्षर के लिए संख्या पर ऑपरेशन करें।
• ए = 2 से गुणा करें; बी = 4 से गुणा करें, 2 जोड़ें; C = 4 से गुणा करें, 3 जोड़ें।
• संख्या को बाइनरी में व्यक्त करें, फिर पहला अंक 1 हटा दें।

तर्कसंगत संभावनाओं के साथ k अक्षरों वाले अधिक सामान्य स्रोत पर विचार करें $n_{1}/N,...,n_{k}/N$. फिर स्रोत पर अंकगणितीय कोडिंग करने के लिए केवल पूर्णांकों के साथ स्पष्ट अंकगणित की आवश्यकता होती है।

सामान्य तौर पर, ANS अंकगणितीय कोडिंग का अनुमान है जो वास्तविक संभावनाओं का अनुमान लगाता है $r_{1},...,r_{k}$ तर्कसंगत संख्याओं द्वारा $n_{1}/N,...,n_{k}/N$ छोटे हर के साथ $N$.

ANS की मूल अवधारणाएँ

अंकगणितीय कोडिंग (बाएं) और एएनएस (दाएं) की अवधारणा की तुलना। दोनों को मानक अंक प्रणालियों के सामान्यीकरण के रूप में देखा जा सकता है, जो अंकों के समान संभाव्यता वितरण के लिए इष्टतम है, कुछ चुने हुए संभाव्यता वितरण के लिए अनुकूलित है। अंकगणित या रेंज कोडिंग सबसे महत्वपूर्ण स्थिति में नई जानकारी जोड़ने से मेल खाती है, जबकि एएनएस कम से कम महत्वपूर्ण स्थिति में जानकारी जोड़ने का सामान्यीकरण करता है। इसका कोडिंग नियम यह है कि x वर्तमान में एन्कोड किए गए प्रतीक के अनुरूप प्राकृतिक संख्याओं के सबसेट की x-वें उपस्थिति पर जाता है। प्रस्तुत उदाहरण में, अनुक्रम (01111) को प्राकृतिक संख्या 18 में एन्कोड किया गया है, जो एनकोड करने के लिए अनुक्रम की आवृत्तियों के साथ बेहतर समझौते के कारण मानक बाइनरी सिस्टम का उपयोग करके प्राप्त 47 से छोटा है। ANS का लाभ सीमा को परिभाषित करने वाले दो के विपरीत, ही प्राकृतिक संख्या में जानकारी संग्रहीत करना है।

कल्पना कीजिए कि कुछ जानकारी प्राकृतिक संख्या में संग्रहीत है $x$, उदाहरण के लिए इसके बाइनरी विस्तार के बिट अनुक्रम के रूप में। बाइनरी वेरिएबल से जानकारी जोड़ने के लिए $s$, हम कोडिंग फ़ंक्शन का उपयोग कर सकते हैं $x'=C(x,s)=2x+s$, जो सभी बिट्स को स्थान ऊपर स्थानांतरित करता है, और नए बिट को कम से कम महत्वपूर्ण स्थान पर रखता है। अब डिकोडिंग फ़ंक्शन $D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))$ किसी को पिछले को पुनः प्राप्त करने की अनुमति देता है $x$ और इसमें थोड़ा सा जोड़ा गया: $D(C(x,s))=(x,s),\ C(D(x'))=x'$. हम शुरुआत कर सकते हैं $x=1$ प्रारंभिक अवस्था, फिर उपयोग करें $C$ अंतिम प्राप्त करने के लिए परिमित बिट अनुक्रम के क्रमिक बिट्स पर कार्य करें $x$ इस पूरे अनुक्रम को संग्रहीत करने वाली संख्या। फिर उपयोग करना $D$ तक कई बार कार्य करें $x=1$ किसी को बिट अनुक्रम को उल्टे क्रम में पुनः प्राप्त करने की अनुमति देता है।

उपरोक्त प्रक्रिया प्रतीकों के समान (सममित) संभाव्यता वितरण के लिए इष्टतम है $\Pr(0)=\Pr(1)=1/2$. ANS इसे प्रतीकों के किसी भी चुने हुए (असममित) संभाव्यता वितरण के लिए इष्टतम बनाने के लिए सामान्यीकृत करता है: $\Pr(s)=p_{s}$. जबकि $s$ उपरोक्त उदाहरण में सम और विषम के बीच चयन करना था $C(x,s)$, ANS में प्राकृतिक संख्याओं के इस सम/विषम विभाजन को कल्पित संभाव्यता वितरण के अनुरूप घनत्व वाले उपसमूहों में विभाजन के साथ प्रतिस्थापित किया जाता है। $\{p_{s}\}_{s}$: पद तक $x$, लगभग हैं $xp_{s}$ प्रतीक की घटनाएँ $s$.

कोडिंग फ़ंक्शन $C(x,s)$ को लौटाता है $x$प्रतीक के अनुरूप ऐसे उपसमुच्चय से -वाँ स्वरूप $s$. घनत्व धारणा स्थिति के बराबर है $x'=C(x,s)\approx x/p_{s}$. यह मानते हुए कि यह प्राकृतिक संख्या है $x$ रोकना $\log _{2}(x)$ जानकारी के टुकड़े, $\log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})$. अतः संभाव्यता का प्रतीक है $p_{s}$ युक्त के रूप में एन्कोड किया गया है $\approx \log _{2}(1/p_{s})$ एन्ट्रॉपी एन्कोडिंग से आवश्यक जानकारी के टुकड़े।

यूनिफ़ॉर्म बाइनरी वेरिएंट (यूएबीएस)

आइए द्विआधारी वर्णमाला और संभाव्यता वितरण से शुरुआत करें $\Pr(1)=p$, $\Pr(0)=1-p$. पद तक $x$ हम लगभग चाहते हैं $p\cdot x$ विषम संख्याओं के अनुरूप (के लिए) $s=1$). हम दिखावे की इस संख्या को इस प्रकार चुन सकते हैं $\lceil x\cdot p\rceil$, उपार्जन $s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil$. इस संस्करण को यूएबीएस कहा जाता है और यह निम्नलिखित डिकोडिंग और एन्कोडिंग कार्यों की ओर ले जाता है: डिकोडिंग:

s = ceil((x+1)*p) - ceil(x*p)  // 0 if fract(x*p) < 1-p, else 1
if s = 0 then new_x = x - ceil(x*p)   // D(x) = (new_x, 0), this is the same as new_x = floor(x*(1-p))
if s = 1 then new_x = ceil(x*p)  // D(x) = (new_x, 1)

एन्कोडिंग:

if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x
if s = 1 then new_x = floor(x/p)  // C(x,1) = new_x

के लिए $p=1/2$ यह अलग के लिए मानक बाइनरी सिस्टम (0 और 1 उलटा के साथ) के बराबर है $p$ यह इस दिए गए संभाव्यता वितरण के लिए इष्टतम बन जाता है। उदाहरण के लिए, के लिए $p=0.3$ ये सूत्र छोटे मानों के लिए तालिका की ओर ले जाते हैं $x$:

$C(x,s)$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$s=0$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
$s=1$	0			1			2				3			4			5				6

प्रतीक $s=1$ घनत्व के साथ प्राकृतिक संख्याओं के सबसेट से मेल खाता है $p=0.3$, जो इस मामले में पद हैं $\{0,3,6,10,13,16,20,23,26,\ldots \}$. जैसा $1/4<0.3<1/3$, इन पदों में 3 या 4 की वृद्धि होती है। क्योंकि $p=3/10$ यहां, प्रतीकों का पैटर्न हर 10 स्थिति में दोहराया जाता है।

कोडिंग $C(x,s)$ किसी दिए गए प्रतीक के अनुरूप पंक्ति लेकर पाया जा सकता है $s$, और दिए गए को चुनना $x$ इस पंक्ति में. फिर शीर्ष पंक्ति प्रदान करती है $C(x,s)$. उदाहरण के लिए, $C(7,0)=11$ मध्य से शीर्ष पंक्ति तक.

कल्पना कीजिए कि हम '0100' से प्रारम्भ होने वाले अनुक्रम को एन्कोड करना चाहेंगे $x=1$. पहला $s=0$ हमें ले जाता है $x=2$, तब $s=1$ को $x=6$, तब $s=0$ को $x=9$, तब $s=0$ को $x=14$. डिकोडिंग फ़ंक्शन का उपयोग करके $D(x')$ इस फाइनल पर $x$, हम प्रतीक अनुक्रम पुनः प्राप्त कर सकते हैं। इस प्रयोजन के लिए तालिका का उपयोग करते हुए, $x$ पहली पंक्ति में कॉलम निर्धारित होता है, फिर गैर-रिक्त पंक्ति और लिखित मान संबंधित निर्धारित करते हैं $s$ और $x$.

रेंज वेरिएंट (आरएएनएस) और स्ट्रीमिंग

श्रेणी संस्करण अंकगणितीय सूत्रों का भी उपयोग करता है, लेकिन बड़े वर्णमाला पर संचालन की अनुमति देता है। सहज रूप से, यह प्राकृतिक संख्याओं के सेट को आकार में विभाजित करता है $2^{n}$ श्रेणियाँ, और उनमें से प्रत्येक को कल्पित संभाव्यता वितरण द्वारा दिए गए अनुपातों की उपश्रेणियों में समान तरीके से विभाजित करें।

हम संभाव्यता वितरण के परिमाणीकरण से शुरुआत करते हैं $2^{n}$ हर, कहाँ n चुना गया है (आमतौर पर 8-12 बिट्स): $p_{s}\approx f[s]/2^{n}$ कुछ प्राकृतिक के लिए $f[s]$ संख्याएँ (उपश्रेणियों के आकार)।

निरूपित ${\text{mask}}=2^{n}-1$, और संचयी वितरण फ़ंक्शन:

$\operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].$

यहां ध्यान दें कि

CDF[s] फ़ंक्शन सच्चा संचयी वितरण फ़ंक्शन नहीं है#परिभाषा यह है कि वर्तमान प्रतीक की संभावना अभिव्यक्ति के मूल्य में शामिल नहीं है। इसके बजाय, CDF[s] पिछले सभी प्रतीकों की कुल संभावना का प्रतिनिधित्व करता है। उदाहरण: की सामान्य परिभाषा के बजाय CDF[0] = f[0], इसका मूल्यांकन इस प्रकार किया जाता है CDF[0] = 0, क्योंकि कोई पिछला प्रतीक नहीं है।

के लिए $y\in [0,2^{n}-1]$ फ़ंक्शन को निरूपित करें (आमतौर पर तालिकाबद्ध)

symbol(y) = s  such that  CDF[s] <= y < CDF[s+1]

अब कोडिंग फ़ंक्शन है:

C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]

डिकोडिंग: s = symbol(x & mask)

D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s)

इस तरह हम प्रतीकों के अनुक्रम को बड़ी प्राकृतिक संख्या में कूटबद्ध कर सकते हैं x. बड़ी संख्या के अंकगणित के उपयोग से बचने के लिए, व्यवहार में स्ट्रीम वेरिएंट का उपयोग किया जाता है: जो लागू करता है $x\in [L,b\cdot L-1]$ पुनर्सामान्यीकरण द्वारा: कम से कम महत्वपूर्ण बिट्स भेजना x बिटस्ट्रीम से या उससे (आमतौर पर L और b 2) की शक्तियां हैं।

rANS संस्करण में x उदाहरण के लिए 32 बिट है। 16 बिट पुनर्सामान्यीकरण के लिए, $x\in [2^{16},2^{32}-1]$, डिकोडर जरूरत पड़ने पर बिटस्ट्रीम से कम से कम महत्वपूर्ण बिट्स को फिर से भरता है:

if(x < (1 << 16)) x = (x << 16) + read16bits()

सारणीबद्ध संस्करण (tANS)

पीआर(ए)=3/4, पीआर(बी)=1/4 संभाव्यता वितरण के लिए 4 राज्य एएनएस ऑटोमेटन का सरल उदाहरण। प्रतीक b में −lg(1/4)=2 बिट जानकारी होती है और इसलिए यह हमेशा दो बिट उत्पन्न करता है। इसके विपरीत, प्रतीक a में −lg(3/4) ~ 0.415 बिट जानकारी होती है, इसलिए कभी-कभी यह बिट (स्थिति 6 और 7 से), कभी-कभी 0 बिट (स्थिति 4 और 5 से) उत्पन्न करता है, केवल स्थिति को बढ़ाता है, जो बिट्स की भिन्नात्मक संख्या वाले बफर के रूप में कार्य करता है: lg(x)। व्यवहार में राज्यों की संख्या उदाहरण के लिए 2048 है, 256 आकार की वर्णमाला के लिए (बाइट्स को सीधे एनकोड करने के लिए)।

टीएएनएस संस्करण संपूर्ण व्यवहार (पुनर्सामान्यीकरण सहित) को रखता है $x\in [L,2L-1]$ तालिका में जो गुणन की आवश्यकता से बचते हुए परिमित-राज्य मशीन उत्पन्न करती है।

अंत में, डिकोडिंग लूप के चरण को इस प्रकार लिखा जा सकता है:

t = decodingTable(x);  
x = t.newX + readBits(t.nbBits); //state transition
writeSymbol(t.symbol); //decoded symbol

एन्कोडिंग लूप का चरण:

s = ReadSymbol();
nbBits = (x + ns[s]) >> r;  // # of bits for renormalization
writeBits(x, nbBits);  // send the least significant bits to bitstream
x = encodingTable[start[s] + (x >> nbBits)];

प्रत्येक को प्रतीक निर्दिष्ट करके विशिष्ट टीएएनएस कोडिंग निर्धारित की जाती है $[L,2L-1]$ स्थिति, उनकी उपस्थिति की संख्या कल्पित संभावनाओं के समानुपाती होनी चाहिए। उदाहरण के लिए, कोई Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 संभाव्यता वितरण के लिए abdacdac असाइनमेंट चुन सकता है। यदि प्रतीकों को 2 की घात वाली लंबाई की श्रेणियों में निर्दिष्ट किया गया है, तो हमें हफ़मैन कोडिंग मिलेगी। उदाहरण के लिए, aaabcdd प्रतीक असाइनमेंट के साथ tANS के लिए a->0, b->100, c->101, d->11 उपसर्ग कोड प्राप्त किया जाएगा।

एम = 3 आकार वर्णमाला और एल = 16 राज्यों के लिए टीएएनएस तालिकाओं के निर्माण का उदाहरण, फिर उन्हें स्ट्रीम डिकोडिंग के लिए लागू करना। सबसे पहले हम भिन्न का उपयोग करके संभावनाओं का अनुमान लगाते हैं जिसमें हर राज्यों की संख्या है। फिर हम इन प्रतीकों को लगभग समान तरीके से फैलाते हैं, वैकल्पिक रूप से विवरण साथ एन्क्रिप्शन के लिए क्रिप्टोग्राफ़िक कुंजी पर निर्भर हो सकते हैं। फिर हम किसी दिए गए प्रतीक के लिए उनकी राशि के मूल्य से प्रारम्भ होने वाली उपस्थिति की गणना करते हैं। फिर हम x (पुनर्सामान्यीकरण) के लिए अनुमानित सीमा पर लौटने के लिए स्ट्रीम से सबसे कम उम्र के बिट्स को फिर से भरते हैं।

टिप्पणियाँ

हफ़मैन कोडिंग के लिए, tANS की संभाव्यता वितरण को संशोधित करना अपेक्षाकृत महंगा है, इसलिए इसका उपयोग मुख्य रूप से स्थैतिक स्थितियों में किया जाता है, आमतौर पर कुछ LZ77 और LZ78|लेम्पेल-ज़िव योजना (जैसे ZSTD, LZFSE) के साथ। इस मामले में, फ़ाइल को ब्लॉकों में विभाजित किया गया है - उनमें से प्रत्येक के लिए प्रतीक आवृत्तियों को स्वतंत्र रूप से गिना जाता है, फिर अनुमान (परिमाणीकरण) के बाद ब्लॉक हेडर में लिखा जाता है और tANS के लिए स्थिर संभाव्यता वितरण के रूप में उपयोग किया जाता है।

इसके विपरीत, rANS का उपयोग आमतौर पर रेंज एन्कोडिंग के लिए तेज़ प्रतिस्थापन के रूप में किया जाता है (उदाहरण के लिए CRAM (फ़ाइल प्रारूप), LZNA, ड्रेको,). इसमें गुणन की आवश्यकता होती है, लेकिन यह अधिक मेमोरी कुशल है और संभाव्यता वितरण को गतिशील रूप से अनुकूलित करने के लिए उपयुक्त है।

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

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

पेटेंट विवाद

उपन्यास ANS एल्गोरिदम और इसके वेरिएंट tANS और rANS के लेखक ने विशेष रूप से परोपकारी कारणों से अपने काम को सार्वजनिक डोमेन में स्वतंत्र रूप से उपलब्ध कराने का इरादा किया था। उन्होंने उनसे लाभ कमाने की कोशिश नहीं की है और यह सुनिश्चित करने के लिए कदम उठाए हैं कि वे कानूनी खदान न बनें, या दूसरों द्वारा प्रतिबंधित न हों, या उनसे लाभ न कमाएं। 2015 में, Google ने मिश्रित बूलियन-टोकन और गुणांक कोडिंग के लिए यूएस और फिर विश्वव्यापी पेटेंट प्रकाशित किया। उस समय, प्रोफेसर डूडा को Google द्वारा वीडियो संपीड़न में मदद करने के लिए कहा गया था, इसलिए वे इस डोमेन के बारे में गहराई से जानते थे, मूल लेखक उनकी सहायता कर रहे थे।

डूडा (संयोग से) Google के पेटेंट इरादों की खोज से खुश नहीं था, क्योंकि वह स्पष्ट था कि वह इसे सार्वजनिक डोमेन के रूप में चाहता था, और उसने विशेष रूप से उस आधार पर Google की सहायता की थी। डूडा ने बाद में तृतीय-पक्ष आवेदन दायर किया अमेरिकी पेटेंट कार्यालय में अस्वीकृति की मांग करते हुए। यूएसपीटीओ ने 2018 में इसके आवेदन को खारिज कर दिया और बाद में Google ने पेटेंट को छोड़ दिया। जून 2019 में Microsoft ने रेंज असममित संख्या प्रणाली एन्कोडिंग और डिकोडिंग की विशेषताएं नामक पेटेंट आवेदन दर्ज किया। यूएसपीटीओ ने 27 अक्टूबर, 2020 को आवेदन की अंतिम अस्वीकृति जारी की। फिर भी 2 मार्च, 2021 को, माइक्रोसॉफ्ट ने यूएसपीटीओ व्याख्यात्मक फाइलिंग दी जिसमें कहा गया कि आवेदक सम्मानपूर्वक अस्वीकृति से असहमत है। , आफ्टर फाइनल कंसीडरेशन पायलट 2.0 कार्यक्रम के तहत अंतिम अस्वीकृति को पलटने की मांग की जा रही है। पुनर्विचार के बाद, यूएसपीटीओ ने 25 जनवरी, 2022 को आवेदन स्वीकार कर लिया।

यह भी देखें

• एन्ट्रापी एन्कोडिंग
• हफ़मैन कोडिंग
• अंकगणित कोडिंग
• रेंज एन्कोडिंग
• ज़स्टैंडर्ड फेसबुक कंप्रेसर
• LZFSE एप्पल कंप्रेसर

बाहरी संबंध

• High throughput hardware architectures for asymmetric numeral systems entropy coding S. M. Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
• New Generation Entropy coders Finite state entropy (FSE) implementation of tANS by Yann Collet
• rygorous/ryg_rans Implementation of rANS by Fabian Giesen
• jkbonfield/rans_static Fast implementation of rANS and aritmetic coding by James K. Bonfield
• facebook/zstd Facebook Zstandard compressor by Yann Collet (author of LZ4)
• LZFSE LZFSE compressor (LZ+FSE) of Apple Inc.
• CRAM 3.0 DNA compressor (order 1 rANS) (part of SAMtools) by European Bioinformatics Institute
• [1] implementation for Google VP10
• [2] implementation for Google WebP
• [3] Google Draco 3D compression library
• aom_dsp - aom - Git at Google implementation of Alliance for Open Media
• Data Compression Using Asymmetric Numeral Systems - Wolfram Demonstrations Project Wolfram Demonstrations Project
• GST: GPU-decodable Supercompressed Textures GST: GPU-decodable Supercompressed Textures
• Understanding compression book by A. Haecky, C. McAnlis