असममित अंक प्रणाली: Difference between revisions
No edit summary |
No edit summary |
||
Line 4: | Line 4: | ||
|url=https://encode.su/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations | |url=https://encode.su/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations | ||
|title=List of compressors using ANS, implementations and other materials | |title=List of compressors using ANS, implementations and other materials | ||
|last=Duda |first=Jarek |date=October 6, 2019 |access-date=October 6, 2019}}</ref><ref name="blANS">{{cite web |url=https://www.bleepingcomputer.com/news/google/google-accused-of-trying-to-patent-public-domain-technology/ |title=Google पर सार्वजनिक डोमेन प्रौद्योगिकी का पेटेंट कराने का प्रयास करने का आरोप|work=[[Bleeping Computer]] |date=September 11, 2017}}</ref> एएनएस [[हफ़मैन कोडिंग]] के समान प्रसंस्करण लागत के साथ अंकगणित कोडिंग (जो | |last=Duda |first=Jarek |date=October 6, 2019 |access-date=October 6, 2019}}</ref><ref name="blANS">{{cite web |url=https://www.bleepingcomputer.com/news/google/google-accused-of-trying-to-patent-public-domain-technology/ |title=Google पर सार्वजनिक डोमेन प्रौद्योगिकी का पेटेंट कराने का प्रयास करने का आरोप|work=[[Bleeping Computer]] |date=September 11, 2017}}</ref> एएनएस [[हफ़मैन कोडिंग]] के समान प्रसंस्करण लागत के साथ अंकगणित कोडिंग (जो न्यूनाधिक स्पष्ट संभाव्यता वितरण का उपयोग करता है) के संपीड़न अनुपात को जोड़ता है। सारणीबद्ध एएनएस (tएएनएस ) संस्करण में, इसे गुणन का उपयोग किए बिना बड़े वर्णमाला पर काम करने के लिए परिमित-अवस्था मशीन का निर्माण करके प्राप्त किया जाता है। | ||
अन्य बातों के अतिरिक्त, | अन्य बातों के अतिरिक्त, एएनएस का उपयोग [[Facebook|फेसबुक]] [[Zstandard|फेसबुक ज़ेडस्टैंडर्ड]] कंप्रेसर <ref name=ZSTD>[https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/ ''Smaller and faster data compression with Zstandard''], Facebook, August 2016.</ref><ref name=ZSTD1>[https://code.fb.com/core-data/zstandard/ ''5 ways Facebook improved compression at scale with Zstandard''], Facebook, December 2018.</ref> (उदाहरण के लिए [[लिनक्स]] कर्नेल, [[एंड्रॉइड (ऑपरेटिंग सिस्टम)|एंड्रॉइड ऑपरेटिंग सिस्टम]] में भी उपयोग किया जाता है जिसे<ref name=Linux>[https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.14-Zstd-Pull ''Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook''], Phoronix, September 2017.</ref> <ref>{{cite web |url=https://android.googlesource.com/kernel/common/+/refs/heads/android-4.14-p-release/fs/btrfs/zstd.c |title=Android P रिलीज़ में Zstd|access-date=2019-05-29 |archive-date=2020-08-26 |archive-url=https://web.archive.org/web/20200826023340/https://android.googlesource.com/kernel/common/+/refs/heads/android-4.14-p-release/fs/btrfs/zstd.c |url-status=dead }}</ref> [[MIME|एमआईएमई]] और [[HTTP|एचटीटीपी]] के लिए RFC 8478 के रूप में प्रकाशित किया गया था<ref name=MIME>[https://datatracker.ietf.org/doc/draft-kucherawy-dispatch-zstd/ ''Zstandard Compression and The application/zstd Media Type (email standard)''].</ref> <ref name="HTTP">[https://www.iana.org/assignments/http-parameters/http-parameters.xhtml ''Hypertext Transfer Protocol (HTTP) Parameters''], [[IANA]].</ref>), एप्पल इंक [[एलजेडएफएसई]] कंप्रेसर,<ref name="LZFSE">[https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource ''Apple Open-Sources its New Compression Algorithm LZFSE''], InfoQ, July 2016.</ref> [[गूगल]] ड्रेको 3डी कंप्रेसर<ref name="Draco">[https://github.com/google/draco ''Google Draco 3D compression library''].</ref> (उदाहरण के लिए [[पिक्सर]] [[ सार्वभौमिक दृश्य विवरण |सार्वभौमिक दृश्य विवरण]] फॉर्मेट में उपयोग किया जाता है<ref name="Pixar">[https://opensource.googleblog.com/2019/11/google-and-pixar-add-draco-compression.html ''Google and Pixar add Draco Compression to Universal Scene Description (USD) Format ''].</ref>) और पीआईके छवि कंप्रेसर,<ref name="PIK">[https://github.com/google/pik ''Google PIK: new lossy image format for the internet''].</ref> [[CRAM (फ़ाइल स्वरूप)|सीआरएएम]] डीएनए कंप्रेसर<ref name="CRAM">[https://samtools.github.io/hts-specs/CRAMv3.pdf ''CRAM format specification (version 3.0)''].</ref> [[SAMtools|सैमटूल्स]] उपयोगिताओं से,<ref name="pmid34590992">{{cite journal| author=Chen W, Elliott LT| title=परिमित-अवस्था एन्ट्रापी के माध्यम से जनसंख्या आनुवंशिक डेटा के लिए संपीड़न।| journal=J Bioinform Comput Biol | year= 2021 | volume= 19| issue= 5| pages= 2150026 | pmid=34590992 | doi=10.1142/S0219720021500268 | pmc= | doi-access=free }}</ref> [[ड्रॉपबॉक्स (सेवा)|ड्रॉपबॉक्]] Divएएनएस कंप्रेसर,<ref name="DivANS">[https://blogs.dropbox.com/tech/2018/06/building-better-compression-together-with-divans/ ''Building better compression together with DivANS''].</ref> [[माइक्रोसॉफ्ट]] [[डायरेक्टस्टोरेज]] बीसीपैक टेक्सचर कंप्रेसर,<ref name="BCPack">[https://docs.microsoft.com/en-us/gaming/gdk/_content/gc/system/overviews/directstorage/directstorage-overview ''Microsoft DirectStorage overview''].</ref> और [[जेपीईजी एक्सएल]]<ref name=jpegxl_committeedraft>{{cite arXiv |title=JPEG XL इमेज कोडिंग सिस्टम का समिति ड्राफ्ट|eprint = 1908.03565 |last1 = Rhatushnyak |first1 = Alexander |last2 = Wassenberg |first2 = Jan |last3 = Sneyers |first3 = Jon |last4 = Alakuijala |first4 = Jyrki |last5 = Vandevenne |first5 = Lode |last6 = Versari |first6 = Luca |last7 = Obryk |first7 = Robert |last8 = Szabadka |first8 = Zoltan |last9 = Kliuchnikov |first9 = Evgenii |last10 = Comsa |first10 = Iulia-Maria |last11 = Potempa |first11 = Krzysztof |last12 = Bruse |first12 = Martin |last13 = Firsching |first13 = Moritz |last14 = Khasanova |first14 = Renata |author15 = Ruud van Asseldonk |last16 = Boukortt |first16 = Sami |last17 = Gomez |first17 = Sebastian |last18 = Fischbacher |first18 = Thomas |class = eess.IV |year = 2019}}</ref> छवि कंप्रेसर इत्यादि में किया जाता है। | ||
मूल विचार सूचना को प्राकृतिक संख्या <math>x</math> में एन्कोड करना है। मानक बाइनरी संख्या प्रणाली में, हम थोड़ा सा <math>s \in \{0, 1\}</math> को सूचना को <math>x</math> में जोड़कर <math>x</math> के अंत में <math>s</math> संलग्न करते है, जिसके फलस्वरूप हमे <math>x' = 2x + s</math> प्राप्त होता। एन्ट्रॉपी कोडर के लिए, यह श्रेष्ट होता है यदि <math>\Pr(0) = \Pr(1) = 1/2</math> होता है। एएनएस इस प्रक्रिया <math>s \in S</math> को प्रतीकों के अनैतिक समुच्चय संभाव्यता वितरण के साथ <math>(p_s)_{s \in S}</math> के लिए सामान्यीकृत करता है। एएनएस में, यदि सूचना <math>s</math> से <math>x</math>में जोड़ा जाता है तो इसके परिणामस्वरूप <math>x'</math> प्राप्त होता है, तब <math>x' \approx x \cdot p_s^{-1}</math>होता है। समान रूप से, <math>\log_2(x') \approx \log_2(x) + \log_2(1/p_s)</math> होता है, जहाँ <math>\log_2(x)</math> संख्या में संग्रहीत सूचना के बिट्स की संख्या <math>x</math> होती है, और <math>\log_2(1/p_s)</math> प्रतीक <math>s</math> में निहित बिट्स की संख्या होती है। | |||
एन्कोडिंग नियम के लिए, प्राकृतिक संख्याओं के समुच्चय को विभिन्न प्रतीकों के अनुरूप असंयुक्त उपसमूहों में विभाजित किया जाता है{{snd}} जैसे सम और विषम संख्याओं के अनुसार, परन्तु एन्कोड करने के लिए प्रतीकों की संभाव्यता वितरण के अनुरूप घनत्व के साथ। फिर प्रतीक <math>s</math> से सूचना को वर्तमान संख्या में पहले से ही संग्रहीत सूचना <math>x</math> में जोड़ता है, इसके पश्चात् हम <math>x' = C(x, s) \approx x/p</math> नंबर पर जाते हैं <math>x</math>-वें से उपस्थिति की स्थिति होने के नाते <math>s</math>-वां उपसमुच्चय प्राप्त होता है। | |||
इसे व्यवहार में प्रयुक्त करने के वैकल्पिक विधियाँ होती हैं{{snd}}एन्कोडिंग और डिकोडिंग चरणों (यूएबीएस और आरएएनएस वेरिएंट) के लिए प्रत्यक्ष गणितीय सूत्र, या कोई संपूर्ण व्यवहार को तालिका (टीएएनएस वेरिएंट) में सम्मिलित कर सकता है। <math>x</math> को अनंत तक जाने से रोकने के लिए पुनर्सामान्यीकरण का उपयोग किया जाता है - संचित बिट्स को बिटस्ट्रीम से या उससे स्थानांतरित करना होता है। | |||
इसे व्यवहार में | |||
==एंट्रॉपी कोडिंग== | ==एंट्रॉपी कोडिंग== | ||
मान लीजिए कि 1,000 शून्य और | मान लीजिए कि 1,000 शून्य और एक अनुक्रम एन्कोड किया जाता है, जिसे प्रत्यक्ष स्टोर करने में 1000 बिट्स लगते है। यघपि, अगर यह किसी तरह ज्ञात हो कि इसमें मात्र 1 शून्य और 999 होता हैं, तो यह शून्य की स्थिति को एनकोड करने के लिए यह पर्याप्त होता है, जिसके लिए मात्र 1000 बिट्स के अतिरिक्त <math>\lceil \log_2(1000)\rceil \approx 10</math> बिट्स की आवश्कता होती है। | ||
सामान्यतः, ऐसी लंबाई <math>n</math> अनुक्रम युक्त <math>pn</math> शून्य और <math>(1-p)n</math> वाले, कुछ संभावना के लिए <math>p\in(0,1)</math>, संयोजन कहलाते हैं। स्टर्लिंग सन्निकटन का उपयोग करके हमें उनकी स्पर्शोन्मुख संख्या प्राप्त होती है | |||
: <math>{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), </math> | : <math>{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), </math> | ||
[[एन्ट्रॉपी (सूचना सिद्धांत)]] कहा जाता है। | जिसे [[एन्ट्रॉपी (सूचना सिद्धांत)]] कहा जाता है। | ||
इसलिए, ऐसे किसी क्रम को चुनने के लिए हमें | इसलिए, ऐसे किसी क्रम को चुनने के लिए हमें न्यूनाधिक <math>n h(p)</math> बिट्स की आवश्यकता होती है। यह अब भी <math>n</math> बिट्स होता है अगर <math>p=1/2</math> होता है यघपि, यह बहुत छोटा भी हो सकता है। उदाहरण के लिए, हमें मात्र <math>\approx n/2</math> के लिए बिट्स <math>p = 0.11</math>की आवश्यकता होती है। | ||
एन्ट्रॉपी एन्कोडिंग प्रति प्रतीक | एन्ट्रॉपी एन्कोडिंग प्रति प्रतीक न्यूनाधिक शैनन एन्ट्रॉपी बिट्स का उपयोग करके प्रतीकों के अनुक्रम के एन्कोडिंग की अनुमति देता है। उदाहरण के लिए, एएनएस का उपयोग प्रत्यक्ष संयोजनों की गणना करने के लिए किया जा सकता है: न्यूनाधिक सर्वश्रेष्ठ विधियों से निश्चित अनुपात वाले प्रतीकों के प्रत्येक अनुक्रम के लिए अलग प्राकृतिक संख्या निर्दिष्ट करता है। | ||
एन्कोडिंग संयोजनों के विपरीत, यह संभाव्यता वितरण | एन्कोडिंग संयोजनों के विपरीत, यह संभाव्यता वितरण सामान्यतः डेटा कंप्रेसर में भिन्न होता है। इस प्रयोजन के लिए, शैनन एन्ट्रॉपी को भारित औसत के रूप में देखा जा सकता है: संभाव्यता का प्रतीक <math>p</math> को <math>\log_2(1/p)</math> सूचना के बिट्स से संलग्न किया जाता है। एएनएस जानकारी को एक प्राकृतिक संख्या <math>x</math> में एन्कोड करता है, जिसकी व्याख्या सूचना के <math>\log_2(x)</math> के रूप में दी जाती है। संभाव्यता के प्रतीक <math>p</math> से सूचना जोड़ने से यह सूचनात्मक सामग्री<math>\log_2(x)+\log_2(1/p)=\log_2(x/p)</math> तक बढ़ जाती है। इसलिए, नए नंबर <math>x'\approx x/p </math> में दोनों सूचना होनी चाहिए। | ||
=== प्रेरक उदाहरण === | === प्रेरक उदाहरण === | ||
1/2, 1/4, 1/4 प्रायिकता के साथ 3 अक्षरों | 1/2, 1/4, 1/4 प्रायिकता के साथ 3 अक्षरों A, B, C वाले स्रोत पर विचार करें। बाइनरी में सर्वश्रेष्ठ उपसर्ग कोड A = 0, B = 10, C = 11 बनाना सरल होता है। फिर संदेश को ABC -> 01011 के रूप में एन्कोड किया जाता है। | ||
हम देखते हैं कि एन्कोडिंग करने के लिए समकक्ष विधि इस प्रकार है: | हम देखते हैं कि एन्कोडिंग करने के लिए समकक्ष विधि इस प्रकार है: | ||
* संख्या 1 से प्रारंभ करें, और प्रत्येक इनपुट अक्षर के लिए संख्या पर | * संख्या 1 से प्रारंभ करें, और प्रत्येक इनपुट अक्षर के लिए संख्या पर संचालन करें। | ||
* | * A = 2 से गुणा करें; B= 4 से गुणा करें, 2 जोड़ें; C = 4 से गुणा करें, 3 जोड़ें। | ||
* संख्या को बाइनरी में व्यक्त करें, फिर | * संख्या को बाइनरी में व्यक्त करें, फिर प्रथम अंक 1 हटा दें। | ||
तर्कसंगत संभावनाओं | तर्कसंगत संभावनाओं <math>n_1/N, ..., n_k/N</math> के साथ k अक्षरों वाले अधिक सामान्य स्रोत पर विचार करेंI फिर स्रोत पर अंकगणितीय कोडिंग करने के लिए मात्र पूर्णांकों के साथ स्पष्ट अंकगणित की आवश्यकता होती है। | ||
सामान्यतः, एएनएस अंकगणितीय कोडिंग का प्राक्कलन होता है जो वास्तविक संभावनाओं <math>r_1, ..., r_k</math> तर्कसंगत <math>n_1/N, ..., n_k/N</math> संख्याओं द्वारा छोटे हर के साथ <math>N</math>का प्राक्कलन लगाता है। | |||
== | == एएनएस की मूल अवधारणाएँ == | ||
[[Image:ANS_general_picture.png|thumb|640px|right|अंकगणितीय कोडिंग (बाएं) और एएनएस (दाएं) की अवधारणा की तुलना। दोनों को मानक अंक प्रणालियों के सामान्यीकरण के रूप में देखा जा सकता है, जो अंकों के समान संभाव्यता वितरण के लिए | [[Image:ANS_general_picture.png|thumb|640px|right|अंकगणितीय कोडिंग (बाएं) और एएनएस (दाएं) की अवधारणा की तुलना। दोनों को मानक अंक प्रणालियों के सामान्यीकरण के रूप में देखा जा सकता है, जो अंकों के समान संभाव्यता वितरण के लिए सर्वश्रेष्ठ है, कुछ चुने हुए संभाव्यता वितरण के लिए अनुकूलित है। अंकगणित या रेंज कोडिंग सबसे महत्वपूर्ण स्थिति में नई सूचना जोड़ने से मेल खाती है, जबकि एएनएस कम से कम महत्वपूर्ण स्थिति में सूचना जोड़ने का सामान्यीकरण करता है। इसका कोडिंग नियम यह है कि x वर्तमान में एन्कोड किए गए प्रतीक के अनुरूप प्राकृतिक संख्याओं के सबसमुच्चय की x-वें उपस्थिति पर जाता है। प्रस्तुत उदाहरण में, अनुक्रम (01111) को प्राकृतिक संख्या 18 में एन्कोड किया गया है, जो एनकोड करने के लिए अनुक्रम की आवृत्तियों के साथ बेहतर समझौते के कारण मानक बाइनरी सिस्टम का उपयोग करके प्राप्त 47 से छोटा है। एएनएस का लाभ सीमा को परिभाषित करने वाले दो के विपरीत, ही प्राकृतिक संख्या में सूचना संग्रहीत करना है।]]कल्पना कीजिए कि कुछ सूचना प्राकृतिक संख्या <math>x</math> में संग्रहीत होता है, उदाहरण के लिए इसके बाइनरी विस्तार के बिट अनुक्रम के रूप में होता है। बाइनरी वेरिएबल <math>s</math> से सूचना जोड़ने के लिए, हम कोडिंग फलन का उपयोग कर सकते हैं <math>x'=C(x,s) = 2x + s </math>, जो सभी बिट्स को स्थान ऊपर स्थानांतरित करता है, और नए बिट को कम से कम महत्वपूर्ण स्थान पर रखता है। अब डिकोडिंग फलन <math>D(x')=(\lfloor x'/2 \rfloor, \mathrm{mod}(x',2))</math> किसी को पिछले को पुनः प्राप्त करने की अनुमति देता है <math>x</math> और इसमें थोड़ा सा संलग्न किया गया: <math>D(C(x,s))=(x,s),\ C(D(x'))=x'</math>होता है। हम <math>x=1</math> प्रारंभिक अवस्था से प्रारम्भ कर सकते हैं, फिर उपयोग कर सकते है <math>C</math>अंतिम प्राप्त करने के लिए परिमित बिट अनुक्रम के क्रमिक बिट्स पर कार्य करता है <math>x</math> इस पूरे अनुक्रम को संग्रहीत करने वाली संख्या होती है। फिर <math>D</math> का उपयोग तब तक कार्य के लिए किया जाता है जब तक <math>x=1</math> किसी को बिट अनुक्रम को व्युत्क्रम क्रम में पुनः प्राप्त करने की अनुमति देता है। | ||
उपरोक्त प्रक्रिया प्रतीकों | उपरोक्त प्रक्रिया प्रतीकों <math>\Pr(0)=\Pr(1)=1/2</math> के समान (सममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ होता है। एएनएस इसे प्रतीकों <math>\Pr(s)=p_s</math> के किसी भी चयन किये हुए (असममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ बनाने के लिए सामान्यीकृत करता है। जबकि <math>s</math> उपरोक्त उदाहरण में सम और विषम <math>C(x,s)</math> के मध्य चयन करना था, एएनएस में प्राकृतिक संख्याओं के इस सम/विषम विभाजन को कल्पित संभाव्यता वितरण के अनुरूप घनत्व वाले उपसमूहों में विभाजन के साथ प्रतिस्थापित किया जाता है। <math>\{p_s\}_s</math>: पद <math>x</math> तक, न्यूनाधिक हैं <math>x p_s</math> प्रतीक की घटनाएँ <math>s</math>. | ||
कोडिंगफलन <math> C(x,s)</math> को लौटाता है <math>x</math>प्रतीक के अनुरूप ऐसे उपसमुच्चय से -वाँ स्वरूप <math> s</math>. घनत्व धारणा स्थिति के बराबर है <math> x'=C(x,s) \approx x / p_s </math>. यह मानते हुए कि यह प्राकृतिक संख्या है <math> x </math> रोकना <math> \log_2(x) </math> सूचना के टुकड़े, <math> \log_2(C(x,s)) \approx \log_2(x) + \log_2(1/ p_s) </math>. अतः संभाव्यता का प्रतीक है <math> p_s </math> युक्त के रूप में एन्कोड किया गया है <math> \approx\log_2(1/ p_s) </math> एन्ट्रॉपी एन्कोडिंग से आवश्यक सूचना के टुकड़े। | |||
== यूनिफ़ॉर्म बाइनरी वेरिएंट (यूएबीएस) == | == यूनिफ़ॉर्म बाइनरी वेरिएंट (यूएबीएस) == | ||
आइए द्विआधारी वर्णमाला और संभाव्यता वितरण से शुरुआत करें <math> \Pr(1) = p</math>, <math>\Pr(0)=1-p </math>. पद तक <math> x </math> हम | आइए द्विआधारी वर्णमाला और संभाव्यता वितरण से शुरुआत करें <math> \Pr(1) = p</math>, <math>\Pr(0)=1-p </math>. पद तक <math> x </math> हम न्यूनाधिक चाहते हैं <math> p\cdot x </math> विषम संख्याओं के अनुरूप (के लिए) <math>s = 1</math>). हम दिखावे की इस संख्या को इस प्रकार चुन सकते हैं <math>\lceil x\cdot p \rceil</math>, उपार्जन <math>s = \lceil (x+1)\cdot p \rceil - \lceil x\cdot p \rceil </math>. इस संस्करण को यूएबीएस कहा जाता है और यह निम्नलिखित डिकोडिंग और एन्कोडिंग कार्यों की ओर ले जाता है:<ref name=uABS>[http://mattmahoney.net/dc/dce.html#Section_33 Data Compression Explained], Matt Mahoney</ref> | ||
डिकोडिंग: | डिकोडिंग: | ||
<syntaxhighlight lang="csharp"> | <syntaxhighlight lang="csharp"> | ||
Line 62: | Line 59: | ||
if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x | 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 </syntaxhighlight> | if s = 1 then new_x = floor(x/p) // C(x,1) = new_x </syntaxhighlight> | ||
के लिए <math>p=1/2</math> यह अलग के लिए मानक बाइनरी सिस्टम (0 और 1 उलटा के साथ) के बराबर है <math>p</math> यह इस दिए गए संभाव्यता वितरण के लिए | के लिए <math>p=1/2</math> यह अलग के लिए मानक बाइनरी सिस्टम (0 और 1 उलटा के साथ) के बराबर है <math>p</math> यह इस दिए गए संभाव्यता वितरण के लिए सर्वश्रेष्ठ बन जाता है। उदाहरण के लिए, के लिए <math>p=0.3</math> ये सूत्र छोटे मानों के लिए तालिका की ओर ले जाते हैं <math>x</math>: | ||
{| class="wikitable" align="center" | {| class="wikitable" align="center" | ||
Line 135: | Line 132: | ||
|align="right"|6 | |align="right"|6 | ||
|} | |} | ||
प्रतीक <math>s=1</math> घनत्व के साथ प्राकृतिक संख्याओं के | प्रतीक <math>s=1</math> घनत्व के साथ प्राकृतिक संख्याओं के सबसमुच्चय से मेल खाता है <math>p=0.3</math>, जो इस मामले में पद हैं <math>\{0,3,6,10,13,16,20,23,26,\ldots\}</math>. जैसा <math>1/4< 0.3 < 1/3</math>, इन पदों में 3 या 4 की वृद्धि होती है। क्योंकि <math>p=3/10</math> यहां, प्रतीकों का पैटर्न हर 10 स्थिति में दोहराया जाता है। | ||
कोडिंग <math>C(x,s)</math> किसी दिए गए प्रतीक के अनुरूप पंक्ति लेकर पाया जा सकता है <math>s</math>, और दिए गए को चुनना <math>x</math> इस पंक्ति में. फिर शीर्ष पंक्ति प्रदान करती है <math>C(x,s)</math>. उदाहरण के लिए, <math>C(7,0)=11 </math> मध्य से शीर्ष पंक्ति तक. | कोडिंग <math>C(x,s)</math> किसी दिए गए प्रतीक के अनुरूप पंक्ति लेकर पाया जा सकता है <math>s</math>, और दिए गए को चुनना <math>x</math> इस पंक्ति में. फिर शीर्ष पंक्ति प्रदान करती है <math>C(x,s)</math>. उदाहरण के लिए, <math>C(7,0)=11 </math> मध्य से शीर्ष पंक्ति तक. | ||
कल्पना कीजिए कि हम '0100' से प्रारम्भ होने वाले अनुक्रम को एन्कोड करना चाहेंगे <math>x=1</math>. पहला <math>s=0</math> हमें ले जाता है <math>x=2</math>, तब <math>s=1</math> को <math>x=6</math>, तब <math>s=0</math> को <math>x=9</math>, तब <math>s=0</math> को <math>x=14</math>. | कल्पना कीजिए कि हम '0100' से प्रारम्भ होने वाले अनुक्रम को एन्कोड करना चाहेंगे <math>x=1</math>. पहला <math>s=0</math> हमें ले जाता है <math>x=2</math>, तब <math>s=1</math> को <math>x=6</math>, तब <math>s=0</math> को <math>x=9</math>, तब <math>s=0</math> को <math>x=14</math>. डिकोडिंगफलन का उपयोग करके <math>D(x')</math> इस फाइनल पर <math>x</math>, हम प्रतीक अनुक्रम पुनः प्राप्त कर सकते हैं। इस प्रयोजन के लिए तालिका का उपयोग करते हुए, <math>x</math> पहली पंक्ति में कॉलम निर्धारित होता है, फिर गैर-रिक्त पंक्ति और लिखित मान संबंधित निर्धारित करते हैं <math>s</math> और <math>x</math>. | ||
== रेंज वेरिएंट (आरएएनएस) और स्ट्रीमिंग == | == रेंज वेरिएंट (आरएएनएस) और स्ट्रीमिंग == | ||
श्रेणी संस्करण अंकगणितीय सूत्रों का भी उपयोग करता है, | श्रेणी संस्करण अंकगणितीय सूत्रों का भी उपयोग करता है, परन्तु बड़े वर्णमाला पर संचालन की अनुमति देता है। सहज रूप से, यह प्राकृतिक संख्याओं के समुच्चय को आकार में विभाजित करता है <math>2^n</math> श्रेणियाँ, और उनमें से प्रत्येक को कल्पित संभाव्यता वितरण द्वारा दिए गए अनुपातों की उपश्रेणियों में समान विधियाँ से विभाजित करें। | ||
हम संभाव्यता वितरण के परिमाणीकरण से शुरुआत करते हैं <math>2^n</math> हर, कहाँ {{mvar|n}} चुना गया है ( | हम संभाव्यता वितरण के परिमाणीकरण से शुरुआत करते हैं <math>2^n</math> हर, कहाँ {{mvar|n}} चुना गया है (सामान्यतः 8-12 बिट्स): <math>p_s \approx f[s]/2^n</math> कुछ प्राकृतिक के लिए <math>f[s]</math> संख्याएँ (उपश्रेणियों के आकार)। | ||
निरूपित <math>\text{mask} = 2^n-1</math>, और संचयी | निरूपित <math>\text{mask} = 2^n-1</math>, और संचयी वितरणफलन : | ||
: <math>\operatorname{CDF}[s] = \sum_{i<s} f[i] =f[0]+ \cdots +f[s-1].</math> | : <math>\operatorname{CDF}[s] = \sum_{i<s} f[i] =f[0]+ \cdots +f[s-1].</math> | ||
यहां ध्यान दें कि | यहां ध्यान दें कि | ||
<syntaxhighlight lang="c" inline>CDF[s]</syntaxhighlight> | <syntaxhighlight lang="c" inline>CDF[s]</syntaxhighlight>फलन सच्चा संचयी वितरणफलन नहीं है#परिभाषा यह है कि वर्तमान प्रतीक की संभावना अभिव्यक्ति के मूल्य में शामिल नहीं है। इसके बजाय, <syntaxhighlight lang="c" inline>CDF[s]</syntaxhighlight> पिछले सभी प्रतीकों की कुल संभावना का प्रतिनिधित्व करता है। उदाहरण: की सामान्य परिभाषा के बजाय <syntaxhighlight lang="c" inline>CDF[0] = f[0]</syntaxhighlight>, इसका मूल्यांकन इस प्रकार किया जाता है <syntaxhighlight lang="c" inline>CDF[0] = 0</syntaxhighlight>, क्योंकि कोई पिछला प्रतीक नहीं है। | ||
के लिए <math>y\in[0,2^n-1]</math> | के लिए <math>y\in[0,2^n-1]</math>फलन को निरूपित करें (सामान्यतः तालिकाबद्ध) | ||
<syntaxhighlight lang="c">symbol(y) = s such that CDF[s] <= y < CDF[s+1] </syntaxhighlight> | <syntaxhighlight lang="c">symbol(y) = s such that CDF[s] <= y < CDF[s+1] </syntaxhighlight> | ||
अब | अब कोडिंगफलन है: | ||
<syntaxhighlight lang="c">C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s] </syntaxhighlight> | <syntaxhighlight lang="c">C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s] </syntaxhighlight> | ||
Line 161: | Line 158: | ||
<syntaxhighlight lang="c">D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s) </syntaxhighlight> | <syntaxhighlight lang="c">D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s) </syntaxhighlight> | ||
इस तरह हम प्रतीकों के अनुक्रम को बड़ी प्राकृतिक संख्या में कूटबद्ध कर सकते हैं {{mvar|x}}. बड़ी संख्या के अंकगणित के उपयोग से बचने के लिए, व्यवहार में स्ट्रीम वेरिएंट का उपयोग किया जाता है: जो | इस तरह हम प्रतीकों के अनुक्रम को बड़ी प्राकृतिक संख्या में कूटबद्ध कर सकते हैं {{mvar|x}}. बड़ी संख्या के अंकगणित के उपयोग से बचने के लिए, व्यवहार में स्ट्रीम वेरिएंट का उपयोग किया जाता है: जो प्रयुक्त करता है <math> x\in [L, b \cdot L-1] </math> पुनर्सामान्यीकरण द्वारा: कम से कम महत्वपूर्ण बिट्स भेजना {{mvar|x}} बिटस्ट्रीम से या उससे (सामान्यतः {{mvar|L}} और {{mvar|b}} 2) की शक्तियां हैं। | ||
rएएनएस संस्करण में {{mvar|x}} उदाहरण के लिए 32 बिट है। 16 बिट पुनर्सामान्यीकरण के लिए, <math> x\in [2^{16},2^{32}-1]</math>, डिकोडर जरूरत पड़ने पर बिटस्ट्रीम से कम से कम महत्वपूर्ण बिट्स को फिर से भरता है: | |||
<syntaxhighlight lang="c">if(x < (1 << 16)) x = (x << 16) + read16bits() </syntaxhighlight> | <syntaxhighlight lang="c">if(x < (1 << 16)) x = (x << 16) + read16bits() </syntaxhighlight> | ||
== सारणीबद्ध संस्करण ( | == सारणीबद्ध संस्करण (tएएनएस ) == | ||
[[Image:Simple example of ANS automaton.png |thumb|480px|right|पीआर(ए)=3/4, पीआर(बी)=1/4 संभाव्यता वितरण के लिए 4 राज्य एएनएस ऑटोमेटन का सरल उदाहरण। प्रतीक b में −lg(1/4)=2 बिट | [[Image:Simple example of ANS automaton.png |thumb|480px|right|पीआर(ए)=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 आकार की वर्णमाला के लिए (बाइट्स को प्रत्यक्ष एनकोड करने के लिए)।]]टीएएनएस संस्करण संपूर्ण व्यवहार (पुनर्सामान्यीकरण सहित) को रखता है <math>x\in[L,2L-1]</math> तालिका में जो गुणन की आवश्यकता से बचते हुए परिमित-राज्य मशीन उत्पन्न करती है। | ||
अंत में, डिकोडिंग लूप के चरण को इस प्रकार लिखा जा सकता है: | अंत में, डिकोडिंग लूप के चरण को इस प्रकार लिखा जा सकता है: | ||
Line 180: | Line 177: | ||
writeBits(x, nbBits); // send the least significant bits to bitstream | writeBits(x, nbBits); // send the least significant bits to bitstream | ||
x = encodingTable[start[s] + (x >> nbBits)]; </syntaxhighlight> | x = encodingTable[start[s] + (x >> nbBits)]; </syntaxhighlight> | ||
प्रत्येक को प्रतीक निर्दिष्ट करके विशिष्ट टीएएनएस कोडिंग निर्धारित की जाती है <math>[L,2L-1]</math> स्थिति, उनकी उपस्थिति की संख्या कल्पित संभावनाओं के समानुपाती होनी चाहिए। उदाहरण के लिए, कोई Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 संभाव्यता वितरण के लिए abdacdac असाइनमेंट चुन सकता है। यदि प्रतीकों को 2 की घात वाली लंबाई की श्रेणियों में निर्दिष्ट किया गया है, तो हमें हफ़मैन कोडिंग मिलेगी। उदाहरण के लिए, aaabcdd प्रतीक असाइनमेंट के साथ | प्रत्येक को प्रतीक निर्दिष्ट करके विशिष्ट टीएएनएस कोडिंग निर्धारित की जाती है <math>[L,2L-1]</math> स्थिति, उनकी उपस्थिति की संख्या कल्पित संभावनाओं के समानुपाती होनी चाहिए। उदाहरण के लिए, कोई Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 संभाव्यता वितरण के लिए abdacdac असाइनमेंट चुन सकता है। यदि प्रतीकों को 2 की घात वाली लंबाई की श्रेणियों में निर्दिष्ट किया गया है, तो हमें हफ़मैन कोडिंग मिलेगी। उदाहरण के लिए, aaabcdd प्रतीक असाइनमेंट के साथ tएएनएस के लिए a->0, b->100, c->101, d->11 उपसर्ग कोड प्राप्त किया जाएगा। | ||
[[Image:TANSex.png|thumb|640px|center|एम = 3 आकार वर्णमाला और एल = 16 राज्यों के लिए टीएएनएस तालिकाओं के निर्माण का उदाहरण, फिर उन्हें स्ट्रीम डिकोडिंग के लिए | [[Image:TANSex.png|thumb|640px|center|एम = 3 आकार वर्णमाला और एल = 16 राज्यों के लिए टीएएनएस तालिकाओं के निर्माण का उदाहरण, फिर उन्हें स्ट्रीम डिकोडिंग के लिए प्रयुक्त करना। सबसे पहले हम भिन्न का उपयोग करके संभावनाओं का प्राक्कलन लगाते हैं जिसमें हर राज्यों की संख्या है। फिर हम इन प्रतीकों को न्यूनाधिक समान विधियाँ से फैलाते हैं, वैकल्पिक रूप से विवरण साथ एन्क्रिप्शन के लिए क्रिप्टोग्राफ़िक कुंजी पर निर्भर हो सकते हैं। फिर हम किसी दिए गए प्रतीक के लिए उनकी राशि के मूल्य से प्रारम्भ होने वाली उपस्थिति की गणना करते हैं। फिर हम x (पुनर्सामान्यीकरण) के लिए प्राक्कलनित सीमा पर लौटने के लिए स्ट्रीम से सबसे कम उम्र के बिट्स को फिर से भरते हैं।]] | ||
== टिप्पणियाँ == | == टिप्पणियाँ == | ||
हफ़मैन कोडिंग के लिए, | हफ़मैन कोडिंग के लिए, tएएनएस की संभाव्यता वितरण को संशोधित करना अपेक्षाकृत महंगा है, इसलिए इसका उपयोग मुख्य रूप से स्थैतिक स्थितियों में किया जाता है, सामान्यतः कुछ LZ77 और LZ78|लेम्पेल-ज़िव योजना (जैसे ZSTD, LZFSE) के साथ। इस मामले में, फ़ाइल को ब्लॉकों में विभाजित किया गया है - उनमें से प्रत्येक के लिए प्रतीक आवृत्तियों को स्वतंत्र रूप से गिना जाता है, फिर प्राक्कलन (परिमाणीकरण) के बाद ब्लॉक हेडर में लिखा जाता है और tएएनएस के लिए स्थिर संभाव्यता वितरण के रूप में उपयोग किया जाता है। | ||
इसके विपरीत, | इसके विपरीत, rएएनएस का उपयोग सामान्यतः [[रेंज एन्कोडिंग]] के लिए तेज़ प्रतिस्थापन के रूप में किया जाता है (उदाहरण के लिए CRAM (फ़ाइल प्रारूप), LZNA, ड्रेको,<ref name=Draco />). इसमें गुणन की आवश्यकता होती है, परन्तु यह अधिक मेमोरी कुशल है और संभाव्यता वितरण को गतिशील रूप से अनुकूलित करने के लिए उपयुक्त है। | ||
एएनएस की एन्कोडिंग और डिकोडिंग विपरीत दिशाओं में की जाती है, जिससे यह प्रतीकों के लिए [[स्टैक (सार डेटा प्रकार)]] बन जाता है। इस असुविधा को सामान्यतः पीछे की दिशा में एन्कोडिंग द्वारा हल किया जाता है, जिसके बाद डिकोडिंग को आगे की ओर किया जा सकता है। संदर्भ-निर्भरता के लिए, [[मार्कोव मॉडल]] की तरह, एनकोडर को बाद के डिकोडिंग के परिप्रेक्ष्य से संदर्भ का उपयोग करने की आवश्यकता होती है। अनुकूलता के लिए, एनकोडर को पहले उन संभावनाओं को खोजने के लिए आगे बढ़ना चाहिए जिनका डिकोडर द्वारा उपयोग (प्राक्कलनित) किया जाएगा और उन्हें बफर में संग्रहीत किया जाएगा, फिर बफर की गई संभावनाओं का उपयोग करके पीछे की दिशा में एनकोड किया जाएगा। | |||
डिकोडिंग प्रारम्भ करने के लिए एन्कोडिंग की अंतिम स्थिति की आवश्यकता होती है, इसलिए इसे संपीड़ित फ़ाइल में संग्रहीत करने की आवश्यकता होती है। एनकोडर की प्रारंभिक स्थिति में कुछ | डिकोडिंग प्रारम्भ करने के लिए एन्कोडिंग की अंतिम स्थिति की आवश्यकता होती है, इसलिए इसे संपीड़ित फ़ाइल में संग्रहीत करने की आवश्यकता होती है। एनकोडर की प्रारंभिक स्थिति में कुछ सूचना संग्रहीत करके इस लागत की भरपाई की जा सकती है। उदाहरण के लिए, 10000 स्थिति से प्रारम्भ करने के बजाय, 1**** स्थिति से प्रारम्भ करें, जहां * कुछ अतिरिक्त संग्रहीत बिट्स हैं, जिन्हें डिकोडिंग के अंत में पुनर्प्राप्त किया जा सकता है। वैकल्पिक रूप से, इस स्थिति को निश्चित स्थिति के साथ एन्कोडिंग प्रारम्भ करके चेकसम के रूप में इस्तेमाल किया जा सकता है, और परीक्षण किया जा सकता है कि डिकोडिंग की अंतिम स्थिति अपेक्षित है या नहीं। | ||
== पेटेंट विवाद == | == पेटेंट विवाद == | ||
उपन्यास | उपन्यास एएनएस एल्गोरिदम और इसके वेरिएंट tएएनएस और rएएनएस के लेखक ने विशेष रूप से परोपकारी कारणों से अपने काम को सार्वजनिक डोमेन में स्वतंत्र रूप से उपलब्ध कराने का इरादा किया था। उन्होंने उनसे लाभ कमाने की कोशिश नहीं की है और यह सुनिश्चित करने के लिए कदम उठाए हैं कि वे कानूनी खदान न बनें, या दूसरों द्वारा प्रतिबंधित न हों, या उनसे लाभ न कमाएं। 2015 में, Google ने मिश्रित बूलियन-टोकन और गुणांक कोडिंग के लिए यूएस और फिर विश्वव्यापी पेटेंट प्रकाशित किया।<ref>{{cite web |title=मिश्रित बूलियन-टोकन और गुणांक कोडिंग|url=https://patents.google.com/patent/US20170164007 |access-date=14 June 2021}}</ref> उस समय, प्रोफेसर डूडा को Google द्वारा वीडियो संपीड़न में मदद करने के लिए कहा गया था, इसलिए वे इस डोमेन के बारे में गहराई से जानते थे, मूल लेखक उनकी सहायता कर रहे थे। | ||
डूडा (संयोग से) Google के पेटेंट इरादों की खोज से खुश नहीं था, क्योंकि वह स्पष्ट था कि वह इसे सार्वजनिक डोमेन के रूप में चाहता था, और उसने विशेष रूप से उस आधार पर Google की सहायता की थी। डूडा ने बाद में तृतीय-पक्ष आवेदन दायर किया<ref>{{cite web |title=गूगल का विरोध|url=http://th.if.uj.edu.pl/~dudaj/protestGoogle.pdf |website=Institute of Theoretical Physics. Jagiellonian University in Krakow Poland |publisher=Professor Jarosław Duda}}</ref> अमेरिकी पेटेंट कार्यालय में अस्वीकृति की मांग करते हुए। यूएसपीटीओ ने 2018 में इसके आवेदन को खारिज कर दिया और बाद में Google ने पेटेंट को छोड़ दिया।<ref>{{cite web |title=पेटेंट कार्यालय की अस्वीकृति के बाद, Google के लिए सार्वजनिक डोमेन एल्गोरिदम के पेटेंट उपयोग के अपने प्रयास को छोड़ने का समय आ गया है|url=https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public |publisher=EFF}}</ref> | डूडा (संयोग से) Google के पेटेंट इरादों की खोज से खुश नहीं था, क्योंकि वह स्पष्ट था कि वह इसे सार्वजनिक डोमेन के रूप में चाहता था, और उसने विशेष रूप से उस आधार पर Google की सहायता की थी। डूडा ने बाद में तृतीय-पक्ष आवेदन दायर किया<ref>{{cite web |title=गूगल का विरोध|url=http://th.if.uj.edu.pl/~dudaj/protestGoogle.pdf |website=Institute of Theoretical Physics. Jagiellonian University in Krakow Poland |publisher=Professor Jarosław Duda}}</ref> अमेरिकी पेटेंट कार्यालय में अस्वीकृति की मांग करते हुए। यूएसपीटीओ ने 2018 में इसके आवेदन को खारिज कर दिया और बाद में Google ने पेटेंट को छोड़ दिया।<ref>{{cite web |title=पेटेंट कार्यालय की अस्वीकृति के बाद, Google के लिए सार्वजनिक डोमेन एल्गोरिदम के पेटेंट उपयोग के अपने प्रयास को छोड़ने का समय आ गया है|url=https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public |publisher=EFF}}</ref> | ||
Line 213: | Line 210: | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
* [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7306068 High throughput hardware architectures for asymmetric numeral systems entropy coding] S. M. Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015 | * [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7306068 High throughput hardware architectures for asymmetric numeral systems entropy coding] S. M. Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015 | ||
* [https://github.com/Cyan4973/FiniteStateEntropy New Generation Entropy coders] Finite state entropy (FSE) implementation of | * [https://github.com/Cyan4973/FiniteStateEntropy New Generation Entropy coders] Finite state entropy (FSE) implementation of tएएनएस by Yann Collet | ||
* [https://github.com/rygorous/ryg_rans rygorous/ | * [https://github.com/rygorous/ryg_rans rygorous/ryg_rएएनएस] Implementation of rएएनएस by Fabian Giesen | ||
* [https://github.com/jkbonfield/rans_static jkbonfield/ | * [https://github.com/jkbonfield/rans_static jkbonfield/rएएनएस _static] Fast implementation of rएएनएस and aritmetic coding by James K. Bonfield | ||
* [https://github.com/facebook/zstd/ facebook/zstd] [[Facebook]] [[Zstandard]] compressor by Yann Collet (author of [[LZ4 (compression algorithm)|LZ4]]) | * [https://github.com/facebook/zstd/ facebook/zstd] [[Facebook]] [[Zstandard]] compressor by Yann Collet (author of [[LZ4 (compression algorithm)|LZ4]]) | ||
* [https://github.com/lzfse/lzfse LZFSE] [[LZFSE]] compressor (LZ+FSE) of [[Apple Inc.]] | * [https://github.com/lzfse/lzfse LZFSE] [[LZFSE]] compressor (LZ+FSE) of [[Apple Inc.]] | ||
* [http://www.ebi.ac.uk/ena/software/cram-toolkit CRAM 3.0 DNA compressor (order 1 | * [http://www.ebi.ac.uk/ena/software/cram-toolkit CRAM 3.0 DNA compressor (order 1 rएएनएस )] (part of [[SAMtools]]) by [[European Bioinformatics Institute]] | ||
* [https://chromium-review.googlesource.com/#/c/318743 ] implementation for Google [[VP10]] | * [https://chromium-review.googlesource.com/#/c/318743 ] implementation for Google [[VP10]] | ||
* [https://chromium-review.googlesource.com/#/c/338781/ ] implementation for Google [[WebP]] | * [https://chromium-review.googlesource.com/#/c/338781/ ] implementation for Google [[WebP]] |
Revision as of 22:56, 16 July 2023
Part of a series on |
Numeral systems |
---|
List of numeral systems |
असममित अंक प्रणाली (एएनएस)[1][2] जगियेलोनियन विश्वविद्यालय के जारोस्लाव डूडा द्वारा प्रारम्भ की गई एन्ट्रापी एन्कोडिंग विधियों का समूह होता है, [3]जिसका उपयोग पिछले विधियों की तुलना में श्रेष्ट प्रदर्शन के कारण 2014 से डेटा संपीड़न में उपयोग किया जाता है।[4][5] एएनएस हफ़मैन कोडिंग के समान प्रसंस्करण लागत के साथ अंकगणित कोडिंग (जो न्यूनाधिक स्पष्ट संभाव्यता वितरण का उपयोग करता है) के संपीड़न अनुपात को जोड़ता है। सारणीबद्ध एएनएस (tएएनएस ) संस्करण में, इसे गुणन का उपयोग किए बिना बड़े वर्णमाला पर काम करने के लिए परिमित-अवस्था मशीन का निर्माण करके प्राप्त किया जाता है।
अन्य बातों के अतिरिक्त, एएनएस का उपयोग फेसबुक फेसबुक ज़ेडस्टैंडर्ड कंप्रेसर [6][7] (उदाहरण के लिए लिनक्स कर्नेल, एंड्रॉइड ऑपरेटिंग सिस्टम में भी उपयोग किया जाता है जिसे[8] [9] एमआईएमई और एचटीटीपी के लिए RFC 8478 के रूप में प्रकाशित किया गया था[10] [11]), एप्पल इंक एलजेडएफएसई कंप्रेसर,[12] गूगल ड्रेको 3डी कंप्रेसर[13] (उदाहरण के लिए पिक्सर सार्वभौमिक दृश्य विवरण फॉर्मेट में उपयोग किया जाता है[14]) और पीआईके छवि कंप्रेसर,[15] सीआरएएम डीएनए कंप्रेसर[16] सैमटूल्स उपयोगिताओं से,[17] ड्रॉपबॉक् Divएएनएस कंप्रेसर,[18] माइक्रोसॉफ्ट डायरेक्टस्टोरेज बीसीपैक टेक्सचर कंप्रेसर,[19] और जेपीईजी एक्सएल[20] छवि कंप्रेसर इत्यादि में किया जाता है।
मूल विचार सूचना को प्राकृतिक संख्या में एन्कोड करना है। मानक बाइनरी संख्या प्रणाली में, हम थोड़ा सा को सूचना को में जोड़कर के अंत में संलग्न करते है, जिसके फलस्वरूप हमे प्राप्त होता। एन्ट्रॉपी कोडर के लिए, यह श्रेष्ट होता है यदि होता है। एएनएस इस प्रक्रिया को प्रतीकों के अनैतिक समुच्चय संभाव्यता वितरण के साथ के लिए सामान्यीकृत करता है। एएनएस में, यदि सूचना से में जोड़ा जाता है तो इसके परिणामस्वरूप प्राप्त होता है, तब होता है। समान रूप से, होता है, जहाँ संख्या में संग्रहीत सूचना के बिट्स की संख्या होती है, और प्रतीक में निहित बिट्स की संख्या होती है।
एन्कोडिंग नियम के लिए, प्राकृतिक संख्याओं के समुच्चय को विभिन्न प्रतीकों के अनुरूप असंयुक्त उपसमूहों में विभाजित किया जाता है – जैसे सम और विषम संख्याओं के अनुसार, परन्तु एन्कोड करने के लिए प्रतीकों की संभाव्यता वितरण के अनुरूप घनत्व के साथ। फिर प्रतीक से सूचना को वर्तमान संख्या में पहले से ही संग्रहीत सूचना में जोड़ता है, इसके पश्चात् हम नंबर पर जाते हैं -वें से उपस्थिति की स्थिति होने के नाते -वां उपसमुच्चय प्राप्त होता है।
इसे व्यवहार में प्रयुक्त करने के वैकल्पिक विधियाँ होती हैं – एन्कोडिंग और डिकोडिंग चरणों (यूएबीएस और आरएएनएस वेरिएंट) के लिए प्रत्यक्ष गणितीय सूत्र, या कोई संपूर्ण व्यवहार को तालिका (टीएएनएस वेरिएंट) में सम्मिलित कर सकता है। को अनंत तक जाने से रोकने के लिए पुनर्सामान्यीकरण का उपयोग किया जाता है - संचित बिट्स को बिटस्ट्रीम से या उससे स्थानांतरित करना होता है।
एंट्रॉपी कोडिंग
मान लीजिए कि 1,000 शून्य और एक अनुक्रम एन्कोड किया जाता है, जिसे प्रत्यक्ष स्टोर करने में 1000 बिट्स लगते है। यघपि, अगर यह किसी तरह ज्ञात हो कि इसमें मात्र 1 शून्य और 999 होता हैं, तो यह शून्य की स्थिति को एनकोड करने के लिए यह पर्याप्त होता है, जिसके लिए मात्र 1000 बिट्स के अतिरिक्त बिट्स की आवश्कता होती है।
सामान्यतः, ऐसी लंबाई अनुक्रम युक्त शून्य और वाले, कुछ संभावना के लिए , संयोजन कहलाते हैं। स्टर्लिंग सन्निकटन का उपयोग करके हमें उनकी स्पर्शोन्मुख संख्या प्राप्त होती है
जिसे एन्ट्रॉपी (सूचना सिद्धांत) कहा जाता है।
इसलिए, ऐसे किसी क्रम को चुनने के लिए हमें न्यूनाधिक बिट्स की आवश्यकता होती है। यह अब भी बिट्स होता है अगर होता है यघपि, यह बहुत छोटा भी हो सकता है। उदाहरण के लिए, हमें मात्र के लिए बिट्स की आवश्यकता होती है।
एन्ट्रॉपी एन्कोडिंग प्रति प्रतीक न्यूनाधिक शैनन एन्ट्रॉपी बिट्स का उपयोग करके प्रतीकों के अनुक्रम के एन्कोडिंग की अनुमति देता है। उदाहरण के लिए, एएनएस का उपयोग प्रत्यक्ष संयोजनों की गणना करने के लिए किया जा सकता है: न्यूनाधिक सर्वश्रेष्ठ विधियों से निश्चित अनुपात वाले प्रतीकों के प्रत्येक अनुक्रम के लिए अलग प्राकृतिक संख्या निर्दिष्ट करता है।
एन्कोडिंग संयोजनों के विपरीत, यह संभाव्यता वितरण सामान्यतः डेटा कंप्रेसर में भिन्न होता है। इस प्रयोजन के लिए, शैनन एन्ट्रॉपी को भारित औसत के रूप में देखा जा सकता है: संभाव्यता का प्रतीक को सूचना के बिट्स से संलग्न किया जाता है। एएनएस जानकारी को एक प्राकृतिक संख्या में एन्कोड करता है, जिसकी व्याख्या सूचना के के रूप में दी जाती है। संभाव्यता के प्रतीक से सूचना जोड़ने से यह सूचनात्मक सामग्री तक बढ़ जाती है। इसलिए, नए नंबर में दोनों सूचना होनी चाहिए।
प्रेरक उदाहरण
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 हटा दें।
तर्कसंगत संभावनाओं के साथ k अक्षरों वाले अधिक सामान्य स्रोत पर विचार करेंI फिर स्रोत पर अंकगणितीय कोडिंग करने के लिए मात्र पूर्णांकों के साथ स्पष्ट अंकगणित की आवश्यकता होती है।
सामान्यतः, एएनएस अंकगणितीय कोडिंग का प्राक्कलन होता है जो वास्तविक संभावनाओं तर्कसंगत संख्याओं द्वारा छोटे हर के साथ का प्राक्कलन लगाता है।
एएनएस की मूल अवधारणाएँ
कल्पना कीजिए कि कुछ सूचना प्राकृतिक संख्या में संग्रहीत होता है, उदाहरण के लिए इसके बाइनरी विस्तार के बिट अनुक्रम के रूप में होता है। बाइनरी वेरिएबल से सूचना जोड़ने के लिए, हम कोडिंग फलन का उपयोग कर सकते हैं , जो सभी बिट्स को स्थान ऊपर स्थानांतरित करता है, और नए बिट को कम से कम महत्वपूर्ण स्थान पर रखता है। अब डिकोडिंग फलन किसी को पिछले को पुनः प्राप्त करने की अनुमति देता है और इसमें थोड़ा सा संलग्न किया गया: होता है। हम प्रारंभिक अवस्था से प्रारम्भ कर सकते हैं, फिर उपयोग कर सकते है अंतिम प्राप्त करने के लिए परिमित बिट अनुक्रम के क्रमिक बिट्स पर कार्य करता है इस पूरे अनुक्रम को संग्रहीत करने वाली संख्या होती है। फिर का उपयोग तब तक कार्य के लिए किया जाता है जब तक किसी को बिट अनुक्रम को व्युत्क्रम क्रम में पुनः प्राप्त करने की अनुमति देता है।
उपरोक्त प्रक्रिया प्रतीकों के समान (सममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ होता है। एएनएस इसे प्रतीकों के किसी भी चयन किये हुए (असममित) संभाव्यता वितरण के लिए सर्वश्रेष्ठ बनाने के लिए सामान्यीकृत करता है। जबकि उपरोक्त उदाहरण में सम और विषम के मध्य चयन करना था, एएनएस में प्राकृतिक संख्याओं के इस सम/विषम विभाजन को कल्पित संभाव्यता वितरण के अनुरूप घनत्व वाले उपसमूहों में विभाजन के साथ प्रतिस्थापित किया जाता है। : पद तक, न्यूनाधिक हैं प्रतीक की घटनाएँ .
कोडिंगफलन को लौटाता है प्रतीक के अनुरूप ऐसे उपसमुच्चय से -वाँ स्वरूप . घनत्व धारणा स्थिति के बराबर है . यह मानते हुए कि यह प्राकृतिक संख्या है रोकना सूचना के टुकड़े, . अतः संभाव्यता का प्रतीक है युक्त के रूप में एन्कोड किया गया है एन्ट्रॉपी एन्कोडिंग से आवश्यक सूचना के टुकड़े।
यूनिफ़ॉर्म बाइनरी वेरिएंट (यूएबीएस)
आइए द्विआधारी वर्णमाला और संभाव्यता वितरण से शुरुआत करें , . पद तक हम न्यूनाधिक चाहते हैं विषम संख्याओं के अनुरूप (के लिए) ). हम दिखावे की इस संख्या को इस प्रकार चुन सकते हैं , उपार्जन . इस संस्करण को यूएबीएस कहा जाता है और यह निम्नलिखित डिकोडिंग और एन्कोडिंग कार्यों की ओर ले जाता है:[21] डिकोडिंग:
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
के लिए यह अलग के लिए मानक बाइनरी सिस्टम (0 और 1 उलटा के साथ) के बराबर है यह इस दिए गए संभाव्यता वितरण के लिए सर्वश्रेष्ठ बन जाता है। उदाहरण के लिए, के लिए ये सूत्र छोटे मानों के लिए तालिका की ओर ले जाते हैं :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 |
प्रतीक घनत्व के साथ प्राकृतिक संख्याओं के सबसमुच्चय से मेल खाता है , जो इस मामले में पद हैं . जैसा , इन पदों में 3 या 4 की वृद्धि होती है। क्योंकि यहां, प्रतीकों का पैटर्न हर 10 स्थिति में दोहराया जाता है।
कोडिंग किसी दिए गए प्रतीक के अनुरूप पंक्ति लेकर पाया जा सकता है , और दिए गए को चुनना इस पंक्ति में. फिर शीर्ष पंक्ति प्रदान करती है . उदाहरण के लिए, मध्य से शीर्ष पंक्ति तक.
कल्पना कीजिए कि हम '0100' से प्रारम्भ होने वाले अनुक्रम को एन्कोड करना चाहेंगे . पहला हमें ले जाता है , तब को , तब को , तब को . डिकोडिंगफलन का उपयोग करके इस फाइनल पर , हम प्रतीक अनुक्रम पुनः प्राप्त कर सकते हैं। इस प्रयोजन के लिए तालिका का उपयोग करते हुए, पहली पंक्ति में कॉलम निर्धारित होता है, फिर गैर-रिक्त पंक्ति और लिखित मान संबंधित निर्धारित करते हैं और .
रेंज वेरिएंट (आरएएनएस) और स्ट्रीमिंग
श्रेणी संस्करण अंकगणितीय सूत्रों का भी उपयोग करता है, परन्तु बड़े वर्णमाला पर संचालन की अनुमति देता है। सहज रूप से, यह प्राकृतिक संख्याओं के समुच्चय को आकार में विभाजित करता है श्रेणियाँ, और उनमें से प्रत्येक को कल्पित संभाव्यता वितरण द्वारा दिए गए अनुपातों की उपश्रेणियों में समान विधियाँ से विभाजित करें।
हम संभाव्यता वितरण के परिमाणीकरण से शुरुआत करते हैं हर, कहाँ n चुना गया है (सामान्यतः 8-12 बिट्स): कुछ प्राकृतिक के लिए संख्याएँ (उपश्रेणियों के आकार)।
निरूपित , और संचयी वितरणफलन :
यहां ध्यान दें कि
CDF[s]
फलन सच्चा संचयी वितरणफलन नहीं है#परिभाषा यह है कि वर्तमान प्रतीक की संभावना अभिव्यक्ति के मूल्य में शामिल नहीं है। इसके बजाय,CDF[s]
पिछले सभी प्रतीकों की कुल संभावना का प्रतिनिधित्व करता है। उदाहरण: की सामान्य परिभाषा के बजायCDF[0] = f[0]
, इसका मूल्यांकन इस प्रकार किया जाता हैCDF[0] = 0
, क्योंकि कोई पिछला प्रतीक नहीं है।
के लिए फलन को निरूपित करें (सामान्यतः तालिकाबद्ध)
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 बिटस्ट्रीम से या उससे (सामान्यतः L और b 2) की शक्तियां हैं।
rएएनएस संस्करण में x उदाहरण के लिए 32 बिट है। 16 बिट पुनर्सामान्यीकरण के लिए, , डिकोडर जरूरत पड़ने पर बिटस्ट्रीम से कम से कम महत्वपूर्ण बिट्स को फिर से भरता है:
if(x < (1 << 16)) x = (x << 16) + read16bits()
सारणीबद्ध संस्करण (tएएनएस )
टीएएनएस संस्करण संपूर्ण व्यवहार (पुनर्सामान्यीकरण सहित) को रखता है तालिका में जो गुणन की आवश्यकता से बचते हुए परिमित-राज्य मशीन उत्पन्न करती है।
अंत में, डिकोडिंग लूप के चरण को इस प्रकार लिखा जा सकता है:
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)];
प्रत्येक को प्रतीक निर्दिष्ट करके विशिष्ट टीएएनएस कोडिंग निर्धारित की जाती है स्थिति, उनकी उपस्थिति की संख्या कल्पित संभावनाओं के समानुपाती होनी चाहिए। उदाहरण के लिए, कोई Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 संभाव्यता वितरण के लिए abdacdac असाइनमेंट चुन सकता है। यदि प्रतीकों को 2 की घात वाली लंबाई की श्रेणियों में निर्दिष्ट किया गया है, तो हमें हफ़मैन कोडिंग मिलेगी। उदाहरण के लिए, aaabcdd प्रतीक असाइनमेंट के साथ tएएनएस के लिए a->0, b->100, c->101, d->11 उपसर्ग कोड प्राप्त किया जाएगा।
टिप्पणियाँ
हफ़मैन कोडिंग के लिए, tएएनएस की संभाव्यता वितरण को संशोधित करना अपेक्षाकृत महंगा है, इसलिए इसका उपयोग मुख्य रूप से स्थैतिक स्थितियों में किया जाता है, सामान्यतः कुछ LZ77 और LZ78|लेम्पेल-ज़िव योजना (जैसे ZSTD, LZFSE) के साथ। इस मामले में, फ़ाइल को ब्लॉकों में विभाजित किया गया है - उनमें से प्रत्येक के लिए प्रतीक आवृत्तियों को स्वतंत्र रूप से गिना जाता है, फिर प्राक्कलन (परिमाणीकरण) के बाद ब्लॉक हेडर में लिखा जाता है और tएएनएस के लिए स्थिर संभाव्यता वितरण के रूप में उपयोग किया जाता है।
इसके विपरीत, rएएनएस का उपयोग सामान्यतः रेंज एन्कोडिंग के लिए तेज़ प्रतिस्थापन के रूप में किया जाता है (उदाहरण के लिए CRAM (फ़ाइल प्रारूप), LZNA, ड्रेको,[13]). इसमें गुणन की आवश्यकता होती है, परन्तु यह अधिक मेमोरी कुशल है और संभाव्यता वितरण को गतिशील रूप से अनुकूलित करने के लिए उपयुक्त है।
एएनएस की एन्कोडिंग और डिकोडिंग विपरीत दिशाओं में की जाती है, जिससे यह प्रतीकों के लिए स्टैक (सार डेटा प्रकार) बन जाता है। इस असुविधा को सामान्यतः पीछे की दिशा में एन्कोडिंग द्वारा हल किया जाता है, जिसके बाद डिकोडिंग को आगे की ओर किया जा सकता है। संदर्भ-निर्भरता के लिए, मार्कोव मॉडल की तरह, एनकोडर को बाद के डिकोडिंग के परिप्रेक्ष्य से संदर्भ का उपयोग करने की आवश्यकता होती है। अनुकूलता के लिए, एनकोडर को पहले उन संभावनाओं को खोजने के लिए आगे बढ़ना चाहिए जिनका डिकोडर द्वारा उपयोग (प्राक्कलनित) किया जाएगा और उन्हें बफर में संग्रहीत किया जाएगा, फिर बफर की गई संभावनाओं का उपयोग करके पीछे की दिशा में एनकोड किया जाएगा।
डिकोडिंग प्रारम्भ करने के लिए एन्कोडिंग की अंतिम स्थिति की आवश्यकता होती है, इसलिए इसे संपीड़ित फ़ाइल में संग्रहीत करने की आवश्यकता होती है। एनकोडर की प्रारंभिक स्थिति में कुछ सूचना संग्रहीत करके इस लागत की भरपाई की जा सकती है। उदाहरण के लिए, 10000 स्थिति से प्रारम्भ करने के बजाय, 1**** स्थिति से प्रारम्भ करें, जहां * कुछ अतिरिक्त संग्रहीत बिट्स हैं, जिन्हें डिकोडिंग के अंत में पुनर्प्राप्त किया जा सकता है। वैकल्पिक रूप से, इस स्थिति को निश्चित स्थिति के साथ एन्कोडिंग प्रारम्भ करके चेकसम के रूप में इस्तेमाल किया जा सकता है, और परीक्षण किया जा सकता है कि डिकोडिंग की अंतिम स्थिति अपेक्षित है या नहीं।
पेटेंट विवाद
उपन्यास एएनएस एल्गोरिदम और इसके वेरिएंट tएएनएस और rएएनएस के लेखक ने विशेष रूप से परोपकारी कारणों से अपने काम को सार्वजनिक डोमेन में स्वतंत्र रूप से उपलब्ध कराने का इरादा किया था। उन्होंने उनसे लाभ कमाने की कोशिश नहीं की है और यह सुनिश्चित करने के लिए कदम उठाए हैं कि वे कानूनी खदान न बनें, या दूसरों द्वारा प्रतिबंधित न हों, या उनसे लाभ न कमाएं। 2015 में, Google ने मिश्रित बूलियन-टोकन और गुणांक कोडिंग के लिए यूएस और फिर विश्वव्यापी पेटेंट प्रकाशित किया।[22] उस समय, प्रोफेसर डूडा को Google द्वारा वीडियो संपीड़न में मदद करने के लिए कहा गया था, इसलिए वे इस डोमेन के बारे में गहराई से जानते थे, मूल लेखक उनकी सहायता कर रहे थे।
डूडा (संयोग से) Google के पेटेंट इरादों की खोज से खुश नहीं था, क्योंकि वह स्पष्ट था कि वह इसे सार्वजनिक डोमेन के रूप में चाहता था, और उसने विशेष रूप से उस आधार पर Google की सहायता की थी। डूडा ने बाद में तृतीय-पक्ष आवेदन दायर किया[23] अमेरिकी पेटेंट कार्यालय में अस्वीकृति की मांग करते हुए। यूएसपीटीओ ने 2018 में इसके आवेदन को खारिज कर दिया और बाद में Google ने पेटेंट को छोड़ दिया।[24] जून 2019 में Microsoft ने रेंज असममित संख्या प्रणाली एन्कोडिंग और डिकोडिंग की विशेषताएं नामक पेटेंट आवेदन दर्ज किया।[25] यूएसपीटीओ ने 27 अक्टूबर, 2020 को आवेदन की अंतिम अस्वीकृति जारी की। फिर भी 2 मार्च, 2021 को, माइक्रोसॉफ्ट ने यूएसपीटीओ व्याख्यात्मक फाइलिंग दी जिसमें कहा गया कि आवेदक सम्मानपूर्वक अस्वीकृति से असहमत है। ,[26] आफ्टर फाइनल कंसीडरेशन पायलट 2.0 कार्यक्रम के तहत अंतिम अस्वीकृति को पलटने की मांग की जा रही है।[27] पुनर्विचार के बाद, यूएसपीटीओ ने 25 जनवरी, 2022 को आवेदन स्वीकार कर लिया।[28]
यह भी देखें
- एन्ट्रापी एन्कोडिंग
- हफ़मैन कोडिंग
- अंकगणित कोडिंग
- रेंज एन्कोडिंग
- ज़स्टैंडर्ड फेसबुक कंप्रेसर
- LZFSE एप्पल कंप्रेसर
संदर्भ
- ↑ J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, The use of asymmetric numeral systems as an accurate replacement for Huffman coding, Picture Coding Symposium, 2015.
- ↑ J. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540, 2013.
- ↑ "Dr Jarosław Duda (Jarek Duda)". Institute of Theoretical Physics. Jagiellonian University in Krakow. Retrieved 2021-08-02.
- ↑ Duda, Jarek (October 6, 2019). "List of compressors using ANS, implementations and other materials". Retrieved October 6, 2019.
- ↑ "Google पर सार्वजनिक डोमेन प्रौद्योगिकी का पेटेंट कराने का प्रयास करने का आरोप". Bleeping Computer. September 11, 2017.
- ↑ Smaller and faster data compression with Zstandard, Facebook, August 2016.
- ↑ 5 ways Facebook improved compression at scale with Zstandard, Facebook, December 2018.
- ↑ Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook, Phoronix, September 2017.
- ↑ "Android P रिलीज़ में Zstd". Archived from the original on 2020-08-26. Retrieved 2019-05-29.
- ↑ Zstandard Compression and The application/zstd Media Type (email standard).
- ↑ Hypertext Transfer Protocol (HTTP) Parameters, IANA.
- ↑ Apple Open-Sources its New Compression Algorithm LZFSE, InfoQ, July 2016.
- ↑ 13.0 13.1 Google Draco 3D compression library.
- ↑ Google and Pixar add Draco Compression to Universal Scene Description (USD) Format .
- ↑ Google PIK: new lossy image format for the internet.
- ↑ CRAM format specification (version 3.0).
- ↑ Chen W, Elliott LT (2021). "परिमित-अवस्था एन्ट्रापी के माध्यम से जनसंख्या आनुवंशिक डेटा के लिए संपीड़न।". J Bioinform Comput Biol. 19 (5): 2150026. doi:10.1142/S0219720021500268. PMID 34590992.
- ↑ Building better compression together with DivANS.
- ↑ Microsoft DirectStorage overview.
- ↑ Rhatushnyak, Alexander; Wassenberg, Jan; Sneyers, Jon; Alakuijala, Jyrki; Vandevenne, Lode; Versari, Luca; Obryk, Robert; Szabadka, Zoltan; Kliuchnikov, Evgenii; Comsa, Iulia-Maria; Potempa, Krzysztof; Bruse, Martin; Firsching, Moritz; Khasanova, Renata; Ruud van Asseldonk; Boukortt, Sami; Gomez, Sebastian; Fischbacher, Thomas (2019). "JPEG XL इमेज कोडिंग सिस्टम का समिति ड्राफ्ट". arXiv:1908.03565 [eess.IV].
- ↑ Data Compression Explained, Matt Mahoney
- ↑ "मिश्रित बूलियन-टोकन और गुणांक कोडिंग". Retrieved 14 June 2021.
- ↑ "गूगल का विरोध" (PDF). Institute of Theoretical Physics. Jagiellonian University in Krakow Poland. Professor Jarosław Duda.
- ↑ "पेटेंट कार्यालय की अस्वीकृति के बाद, Google के लिए सार्वजनिक डोमेन एल्गोरिदम के पेटेंट उपयोग के अपने प्रयास को छोड़ने का समय आ गया है". EFF.
- ↑ "रेंज असममित संख्या प्रणाली एन्कोडिंग और डिकोडिंग की विशेषताएं". Retrieved 14 June 2021.
- ↑ "Third time's a harm? Microsoft tries to get twice-rejected compression patent past skeptical examiners". The Register. Retrieved 14 June 2021.
- ↑ "After Final Consideration Pilot 2.0". United States Patent and Trademark Office. United States Patent and Trademark Office. Retrieved 14 June 2021.
- ↑ "रेंज असममित संख्या प्रणाली एन्कोडिंग और डिकोडिंग की विशेषताएं". Retrieved 16 February 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