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

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

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

मूल विचार सूचना को प्राकृतिक संख्या $x$ में एन्कोड करना है। मानक बाइनरी संख्या प्रणाली में, हम थोड़ा सा $s\in \{0,1\}$ को सूचना को $x$ में जोड़कर $x$ के अंत में $s$ संलग्न करते है, जिसके फलस्वरूप हमे $x'=2x+s$ प्राप्त होता। एन्ट्रॉपी कोडर के लिए, यह श्रेष्ट होता है यदि $\Pr(0)=\Pr(1)=1/2$ होता है। एएनएस इस प्रक्रिया $s\in S$ को प्रतीकों के अनैतिक समुच्चय संभाव्यता वितरण के साथ $(p_{s})_{s\in S}$ के लिए सामान्यीकृत करता है। एएनएस में, यदि सूचना $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 होता हैं, तो यह शून्य की स्थिति को एनकोड करने के लिए यह पर्याप्त होता है, जिसके लिए मात्र 1000 बिट्स के अतिरिक्त $\lceil \log _{2}(1000)\rceil \approx 10$ बिट्स की आवश्कता होती है।

सामान्यतः, ऐसी लंबाई $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$की आवश्यकता होती है।

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

एन्कोडिंग संयोजनों के विपरीत, यह संभाव्यता वितरण सामान्यतः डेटा संपीडक में भिन्न होता है। इस प्रयोजन के लिए, शैनन एन्ट्रॉपी को भारित औसत के रूप में देखा जा सकता है: संभाव्यता का प्रतीक $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 अक्षरों A, B, C वाले स्रोत पर विचार करें। बाइनरी में सर्वश्रेष्ठ उपसर्ग कोड A = 0, B = 10, C = 11 बनाना सरल होता है। फिर संदेश को ABC -> 01011 के रूप में एन्कोड किया जाता है।

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

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

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

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

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

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

कल्पना कीजिए कि कुछ सूचना प्राकृतिक संख्या $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$ के समान (सममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ होता है। एएनएस इसे प्रतीकों $\Pr(s)=p_{s}$ के किसी भी चयन किये हुए (असममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ बनाने के लिए सामान्यीकृत करता है। जबकि $s$ उपरोक्त उदाहरण में सम और विषम $C(x,s)$ के मध्य चयन करना था, एएनएस में प्राकृतिक संख्याओं के इस सम/विषम विभाजन को कल्पित संभाव्यता वितरण के अनुरूप घनत्व वाले उपसमूहों में विभाजन के साथ प्रतिस्थापित किया जाता है। $\{p_{s}\}_{s}$: पद $x$ तक, $xp_{s}$ प्रतीक की $s$ न्यूनाधिक घटनाएँ होती है।

कोडिंगफलन प्रतीक $C(x,s)$ के अनुरूप ऐसे उपसमुच्चय $s$ से $x$-वाँ स्वरूप लौटाता है। घनत्व धारणा स्थिति $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$ प्रारम्भ करें। विषम संख्याओं के अनुरूप $s=1$ के लिए) $x$ पद तक हम न्यूनाधिक $p\cdot x$ चाहते हैं। हम उपस्थिति इस संख्या को इस प्रकार $\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$ के लिए यह भिन्न $p$ के लिए मानक बाइनरी प्रणाली (0 और 1 उलटा के साथ) के समान्तर होता है इस प्रकार यह इस दिए गए संभाव्यता वितरण के लिए सर्वश्रेष्ठ बन जाता है। उदाहरण के लिए, के लिए $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$ मध्य से शीर्ष पंक्ति तक होता है।

कल्पना कीजिए कि हम $x=1$ से '0100' तक प्रारम्भ होने वाले अनुक्रम को एन्कोड करा जाता है। सर्वप्रथम $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 नहीं होताहै क्योंकिवर्तमान प्रतीक की संभावना अभिव्यक्ति के मूल्य में सम्मिलित नहीं होताहै। इसके अतिरिक्त, 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) की शक्तियां होती हैं।

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

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

सारणीबद्ध संस्करण (टीएएनएस )

Pr(a) = 3/4, Pr(b) = 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 प्रतीक असाइनमेंट के साथ टीएएनएस के लिए a->0, b->100, c->101, d->11 उपसर्ग कोड प्राप्त किया जाएगा।

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

टिप्पणियाँ

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

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

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

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

पेटेंट विवाद

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

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

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

यह भी देखें

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

बाहरी संबंध

• 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 tएएनएस by Yann Collet
• rygorous/ryg_rएएनएस Implementation of rएएनएस by Fabian Giesen
• jkbonfield/rएएनएस _static Fast implementation of rएएनएस 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 rएएनएस ) (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