एन्ट्रॉपी कोडिंग आरएएनएस या अपने स्वयं के अभिलेखागार को कैसे लिखना है

यह लेख उन लोगों के लिए रुचि का हो सकता है जो डेटा कम्प्रेशन में लगे हुए हैं या अपना स्वयं का संग्रह लिखना चाहते हैं।



लेख मुख्य रूप से ब्लॉग की सामग्रियों पर लिखा गया है , जिसे फाबियान गिसेन द्वारा बनाए रखा गया है।

परिचय

एन्ट्रापी कोडिंग विधि rANS ( r ange + ANS) FSE एल्गोरिथ्म का सहोदर है, जिसे मैंने पहले लिखा था । संक्षिप्त नाम ANS का अर्थ है असममित अंक प्रणाली , और नाम सीमा में शब्द अंतराल कोडिंग के साथ इस पद्धति की समानता पर संकेत देता है। RANS के लेखक यारेक डूडा हैं ।

आरएनएस विधि आपको बहुत अधिक गति से लगभग इष्टतम संपीड़न प्राप्त करने की अनुमति देती है। इस rANS में FSE से ज्यादा बुरा नहीं है, जो आश्चर्य की बात नहीं है: दोनों एल्गोरिदम एक सामान्य सैद्धांतिक आधार पर आधारित हैं। हालांकि, एफएसई की तुलना में लागू करने के लिए rANS एल्गोरिदम बहुत सरल है।

सबसे पहले, एक लंबा "सैद्धांतिक" हिस्सा होगा, और फिर हम एक साधारण संग्रह लिखने की कोशिश करेंगे।

विधि का वर्णन

एल्गोरिथ्म का संचालन निम्नलिखित सरल सूत्रों द्वारा निर्धारित किया जाता है:

एन्कोडिंग: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)
डिकोडिंग: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs

आइए उनका विस्तार से विश्लेषण करें।

एन्कोडिंग फ़ंक्शन C (s, x) वर्ण को एन्कोडेड होने देता है (इसे पूर्णांक होने दें) और एनकोडर x (एक पूर्णांक) की वर्तमान स्थिति।

एफ _एस - प्रतीक आवृत्ति एस । उपरोक्त एफएस द्वारा विभाजन पूर्णांक है।
M वर्णमाला के सभी प्रतीकों ( M = ) F _s ) की आवृत्तियों का योग है।
_{एस में} , एन्कोड किए गए वर्ण के अनुरूप अंतराल की शुरुआत (नीचे की आकृति में)।
x % F, F के द्वारा x को विभाजित करने का शेष भाग है।

ऑपरेशन का सिद्धांत अंकगणित कोडिंग में समान है: हम खंड [ 0, M) को लेते हैं और इसे भागों में विभाजित करते हैं ताकि प्रत्येक वर्ण एस वर्ण F की आवृत्ति के आकार के बराबर अंतराल के अनुरूप हो। किसी भी अंतराल में मूल्य x% M की घटना इसी प्रतीक के एन्कोडिंग को दर्शाती है।


एन्कोडिंग की शुरुआत में, एक्स को एक मनमाना उपयुक्त मान के साथ आरंभीकृत करें, और फिर अनुक्रम में सभी एन्कोड किए गए वर्णों के लिए फ़ंक्शन सी (एस, एक्स) की गणना करें।

फ़ंक्शन C (s, x) की प्रत्येक गणना x का मान बढ़ाती है। जब यह बहुत बड़ा हो जाता है, तो आपको आउटपुट में डेटा डंप करना चाहिए:

 while (x >= x_max) {   writeToStream(x % b); //     x /= b; //  x } 

इस कदम को रेनोवेशन कहा जाता है। इसके बाद, आप कोडिंग जारी रख सकते हैं।

कोड में ऊपर, नए स्थिरांक दिखाई दिए: x_max और b । सिद्धांत रूप में, संख्या एम , बी, और x_max कुछ संबंधों से संबंधित हैं, लेकिन व्यवहार में यह निम्नलिखित मूल्यों का उपयोग करने के लिए सबसे प्रभावी है यदि राज्य uint32 राज्य x लिए उपयोग किया जाता है:

एम = 2 ^ के , जहां के <= 16
b = 2 ^ 16 (uint32 का आधा आकार)

M = 2 ^ k का विकल्प इस तथ्य के कारण है कि डिकोडिंग फ़ंक्शन में M द्वारा विभाजन है, इसलिए शेष के साथ विभाजन को बिटवाइज़ ऑपरेशन के साथ बदला जा सकता है।

K का मान निम्नलिखित विचारों से चुना जाता है: यह जितना बड़ा होगा, F _s की सटीकता उतनी ही अधिक होगी और संपीड़न जितना अधिक कुशल होगा। इस मामले में, आवृत्ति तालिका को संग्रहीत करने के लिए कुछ ओवरहेड को ध्यान में रखा जाना चाहिए, इसलिए यह हमेशा कश्मीर के अधिकतम मूल्यों का उपयोग करने के लायक नहीं है।

X_max का मान ऐसा होना चाहिए कि कोई अतिप्रवाह न हो। एन्कोडिंग फ़ंक्शन के आधार पर, हमें वह x < uint32_max * Fs / M या थोड़ा अलग तरीका मिलता है: x_max <= ( b * L ) * Fs / M , जहां L <= uint32_max / b । वास्तविक कोड में, स्थिति गणना में ओवरफ्लो से बचने के लिए फॉर्म x / b> = L / M * Fs लेती है।

मान b = 2 ^ 16 (uint32 का आधा आकार) इस तरह से चुना जाता है कि यदि x x_max से अधिक हो जाता है , तो b द्वारा एक विभाजन काम जारी रखने के लिए पर्याप्त है। नतीजतन, while पहले पुनरावृत्ति के बाद समाप्त हो जाएगा, जिसका अर्थ है कि यदि यह एक सरल के साथ बदला जा सकता है।

परिणामस्वरूप, एन्कोडिंग फ़ंक्शन निम्न रूप लेता है:

 typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10; //   constexpr uint32_t RANS_M = 1u << k; // M = 2^k //   s void RansEnc(RansState& x, uint32_t s, RansOutBuf& out) {   assert(x >= RANS_L); //        uint32 Fs = freq[s]; //   s   uint32 Bs = range_start[s]; //   s   assert(Fs > 0 && Fs <= RANS_M);     // renormalize   if ((x >> 16) >= (RANS_L >> k) * Fs) { // x / b >=  L / M * Fs       out.put( x & 0xffff );       x >>= 16;   }   x = ((x / Fs) << k) + Bs + (x % Fs); // C(s,x)     assert(x >= RANS_L); //      } 

एन्कोडिंग के अंत में, आपको x का मान बचाना होगा, क्योंकि डिकोडिंग इससे शुरू होगी। और हां, हम अंत से शुरुआत तक, यानी आखिरी एन्कोडेड कैरेक्टर से पहले तक डिकोड करेंगे। ( एफएसई के बारे में एक लेख में , इस बिंदु को पर्याप्त रूप से समझाया गया है।)

मैं थोड़ी और जानकारी देना चाहता हूं कि एन्कोडिंग फॉर्मूला कैसे काम करता है।

 x := (x / Fs) * M + Bs + (x % Fs) 

कंप्यूटिंग ( x / Fs) * M , चर x में कम से कम महत्वपूर्ण बिट्स होते हैं (याद रखें कि M = 2 ^ k )। + Bs + (x % Fs) जोड़ना अनिवार्य रूप से इन बिट्स को वर्ण s के अंतराल से एक निश्चित मान लिखता है, क्योंकि Bs अंतराल की शुरुआत है, और (x% Fs) इस अंतराल के भीतर की संख्या है (अंतराल का आकार Fs है)। इस प्रकार, डिकोडिंग के समय, हम एन्कोडेड वर्ण को उस अंतराल से निर्धारित कर सकते हैं जिसमें यह गिरता है (x% M)।

डिकोडिंग

चलो डिकोडिंग फ़ंक्शन पर चलते हैं।

 D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs 

जैसा कि हम पहले ही ऊपर समझ चुके हैं, वांछित वर्ण s , विभाजन x % M के शेष भाग से निर्धारित होता है । किस अंतराल में मान (x% M) गिर गया, ऐसा चरित्र एनकोडेड था।

इससे पहले, हमने डिकोडिंग फ़ंक्शन को सरल बनाने के लिए विशेष रूप से M = 2 ^ k को परिभाषित किया। यह इस तरह समाप्त हुआ:

 uint32_t RansDecode(RansState& x, RansInBuf& in) {   assert(x >= RANS_L); //       uint32_t x_mod = x & (RANS_M - 1); // = x % M   //  ,    x_mod,     assert(x_mod < dct.size());   uint32_t s = dct[x_mod]; //     uint32 Fs = freq[s]; //   s   uint32 Bs = range_start[s]; //    s   x = (x >> k) * Fs + x_mod - Bs;     // renormalize   if (x < RANS_L) {       x = (x << 16) | in.read16(); //  16    }     assert(x >= RANS_L); //     return s; } 

डिकोडिंग उसी एक्स से शुरू होती है जो एन्कोडिंग के अंत में प्राप्त की गई थी। ऐसा करने के लिए, इसे एन्कोडेड डेटा के साथ सहेजा जाना चाहिए।

डिकोडिंग के अंत में, डिकोडर x की स्थिति एन्कोडिंग के समान होनी चाहिए। सामान्य तौर पर, प्रत्येक चरण में x का संगत कोडिंग चरण के समान होना चाहिए। डिबगिंग के समय यह तथ्य बहुत मदद करता है।

जैसा कि आप देख सकते हैं, डिकोडिंग एन्कोडिंग की तुलना में तेजी से काम करता है, क्योंकि कोई विभाजन ऑपरेशन नहीं है।

डिकोडिंग फ़ंक्शन में सबसे कठिन क्षण यह निर्धारित करने की विधि है जिसमें मान गिर गया (x% M)।

सबसे आसान और सबसे तेज़ तरीका सिंबल [] टेबल का उपयोग करना है, आकार एम। इस मामले में, हमें FSE एल्गोरिथ्म में उसी आकार की एक तालिका मिलती है, जिसमें अंतर यह है कि rANS में तालिका "मिश्रित" नहीं है, वर्ण क्रम में हैं, और ऐसी तालिका का निर्माण करना बहुत आसान है।

इस दृष्टिकोण का मुख्य दोष सिंबल टेबल का आकार है, जो बढ़ते कश्मीर के साथ तेजी से बढ़ता है।

उपनाम विधि

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


एक लंबी और लंबी व्याख्या यहां पाई जा सकती है: डार्ट्स, डाइस और सिक्के । मैं संक्षेप में विधि के सार का वर्णन करूंगा: हम सबसे लंबे अंतराल का एक टुकड़ा लेते हैं और इसे सबसे कम अंतराल से जोड़ते हैं ताकि कुल आकार एम / एन (जहां एन वर्णमाला में वर्णों की संख्या हो)। यह पता चला है कि यदि आप क्रमिक रूप से ऐसा करते हैं, तो आप हमेशा एन जोड़े के आकार एम / एन के साथ समाप्त होंगे ।

स्वाभाविक रूप से, M को N से विभाज्य होना चाहिए । और अगर हमें याद है कि हमारे पास M = 2 ^ k है , तो वर्णमाला का आकार भी दो की शक्ति है। यह एक समस्या नहीं है, क्योंकि आप हमेशा शून्य आकार के साथ अप्रयुक्त वर्णों के साथ वांछित आकार में वर्णमाला को पूरक कर सकते हैं।

तथ्य यह है कि चरित्र अंतराल को कई भागों में विभाजित किया गया है, कोडिंग प्रक्रिया को थोड़ा जटिल करता है, लेकिन बहुत अधिक नहीं। यदि आप एफएसई को याद करते हैं, तो वहां अंतराल आम तौर पर पूरी रेंज में फैले हुए थे, जैसे कि एक पागल मिक्सर ने उन पर काम किया था, और कुछ भी काम नहीं किया =)

वांछित अंतराल का निर्धारण करना मुश्किल नहीं है: एक्स को एन से विभाजित करें, और जोड़े में से एक में गिरें। अगला, हम एक जोड़ी में खंडों के बीच की सीमा के साथ x% N के शेष भाग की तुलना करते हैं और एक अंतराल या दूसरे में गिरते हैं।

हम अभ्यास में प्रयास करते हैं

हम समाप्त उदाहरण के कोड का उपयोग करेंगे।

हम फ़ाइल से संपीड़न के लिए डेटा लेते हैं:

 size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size); 

1. सबसे पहले आपको डेटा संरचना पर निर्णय लेने की आवश्यकता है।

हम सबसे सरल विकल्प का उपयोग करते हैं: हम वर्णमाला का उपयोग करके एक बाइट को कूटबद्ध करेंगे [0 ... 255]।

2. अगला कदम वर्णमाला वर्णों की आवृत्ति निर्धारित करना है:

(फंक्शन stats.count_freqs )

 for (size_t i = 0; i < in_size; i++) {   freqs[in_bytes[i]]++; } 

3. इसलिए, हमारे पास प्रतीक आवृत्तियां हैं, लेकिन अब हमें उन्हें सामान्य करने की आवश्यकता है, यानी आनुपातिक रूप से कम (या वृद्धि) ताकि कुल मिलाकर हमें M = 2 ^ k मिले। यह इतना आसान काम नहीं है जितना कि यह प्रतीत हो सकता है, इसलिए हम एक तैयार किए गए फ़ंक्शन का उपयोग करते हैं:

 stats.normalize_freqs(...); 

वैसे, आपको k का मान निर्धारित करने की आवश्यकता है। चूँकि हमारी वर्णमाला में 256 अक्षर होते हैं, इसलिए k को 8 से कम नहीं लिया जाना चाहिए। सबसे पहले, अधिकतम - 16 लें, और बाद में अन्य मान आज़माएँ।

4. निर्माण अन्य तालिका :

 stats.make_alias_table(); 

5. हम अंत से एनकोड करते हैं , फिर सामान्य क्रम में डिकोड करते हैं।

 RansState rans; //  rANS,    x RansEncInit(&rans); //    uint8_t* ptr = out_buf + out_max_size; // *end* of output buffer for (size_t i = in_size; i > 0; i--) { // NB: working in reverse!   int s = in_bytes[i - 1];   RansEncPutAlias(&rans, &ptr, &stats, s, prob_bits); } //   .     . RansEncFlush(&rans, &ptr); 

इसके अलावा, संदर्भ द्वारा उदाहरण तैयार आंकड़ों का उपयोग करके डेटा को संपीड़ित करता है। वास्तविक जीवन में, डिकोडिंग के लिए, आपको संपीड़ित डेटा के साथ आवृत्तियों (आँकड़े) की एक तालिका को सहेजने की आवश्यकता होती है। सरलतम मामले में, आपको इस पर N * k बिट्स खर्च करना होगा।

जैसा कि ऊपर वादा किया गया है, आइए k के विभिन्न मूल्यों के लिए संपीड़न परिणामों को देखें (कोड में यह prob_bits ), आवृत्ति तालिका की रिकॉर्डिंग के कारण आकार में वृद्धि को ध्यान में रखते हुए:

( मूल किताब 1 फ़ाइल का आकार : 768771)
k = 16: 435059 + 512 = 435571 बाइट्स
k = 15 : 435078 + 480 = 435558 बाइट्स
k = 14: 435113 + 448 = 435561 बाइट्स
k = 13: 435239 + 416 = 435655 बाइट्स
k = 12: 435603 + 384 = 435987 बाइट्स
k = 11: 436530 + 352 = 436882 बाइट्स
k = 10: 440895 + 320 = 441215 बाइट्स
k = 9: 453418 + 288 = 453706 बाइट्स
k = 8: 473126 + 256 = 473382 बाइट्स

आप देख सकते हैं कि उच्च k, बेहतर संपीड़न। लेकिन एक निश्चित बिंदु पर (k = 16 पर), आवृत्ति तालिका का ओवरहेड बढ़ती सटीकता के लाभों से आगे बढ़ना शुरू कर देता है। यदि आप एक छोटी फ़ाइल को संपीड़ित करते हैं, तो यह प्रभाव छोटे k पर दिखाई देगा।

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

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

अंतभाषण

जब कई समय-परीक्षण किए गए उपयोगिताओं हैं तो अपने स्वयं के अभिलेखागार को क्यों लिखें? इसका उत्तर काफी सरल है: विशिष्ट प्रारूप के अनुरूप आर्काइव बेहतर तरीके से संपीड़ित होते हैं।

Playrix में गेम विकसित करते समय, हम अक्सर बिल्ड आकार को कम करने की आवश्यकता पर भरोसा करते हैं। खेल लगातार विकसित हो रहे हैं, सामग्री की मात्रा बढ़ रही है, और स्थान सीमित है।

एक बार फिर , संसाधनों को लंबे समय तक देखते हुए, हमने महसूस किया कि कुछ फाइलों को उनकी संरचना को देखते हुए, ज़िप की तुलना में बहुत बेहतर तरीके से संकुचित किया जा सकता है। प्रयोगों के दौरान, हम अपने स्वयं के एनीमेशन प्रारूप के आकार को काफी कम करने में कामयाब रहे, ग्राफिक्स फ़ाइलों के संपीड़न में कुछ बदलाव भी हैं।

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

मुझे उम्मीद है कि यह लेख आपको rANS को जानने और अपनी परियोजनाओं में इसका उपयोग शुरू करने में मदद करेगा।

संदर्भ

यहां आप rANS कार्यान्वयन के कार्य उदाहरण देख सकते हैं (विभिन्न अनुकूलन विकल्पों के साथ):

फैबियन गिसेन: github.com/rygorous/ryg_rans

आप फैबियन के ब्लॉग (अंग्रेजी में) पर दिलचस्प विवरण और विवरण पढ़ सकते हैं:

→ rANS नोट
→ स्थिर संभावना वितरण के साथ rANS
→ व्यवहार में rANS