डेटा संपीड़न: अंकगणितीय कोडिंग अस्पष्ट

Question

क्या कोई भी कार्यान्वयन विवरण के साथ डेटा संपीड़न के लिए अंकगणितीय एन्कोडिंग समझा सकता है? मैंने इंटरनेट के माध्यम से सर्फ किया है और मार्क नेल्सन की पोस्ट पाई है लेकिन कई घंटों की कोशिश करने के बाद कार्यान्वयन की तकनीक वास्तव में मुझे अस्पष्ट नहीं है। अंकगणित पर

मार्क नेल्सन के विवरण कोडन मुझे गणित संपीड़न की अवधारणा को शुरू करने के लिए

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

अंकगणितीय संपीड़न के साथ मुख्य विचार यह संभाव्यता को आवश्यक डेटा लंबाई की सटीक मात्रा का उपयोग करके कोड करने की क्षमता है।

डेटा की इस राशि में जाना जाता है, शैनन द्वारा सिद्ध, और निम्न सूत्र का उपयोग करके बस गणना की जा सकती: -log2 (पी)

उदाहरण के लिए, पी = 50% है, तो आप 1 बिट की जरूरत है। और यदि पी = 25%, तो आपको 2 बिट्स की आवश्यकता है।

यह संभावनाओं के लिए काफी आसान है जो 2 की शक्ति हैं (और इस विशेष मामले में, हफमैन कोडिंग पर्याप्त हो सकती है)। लेकिन क्या होगा यदि संभावना 63% है? फिर आपको -log2 (0.63) = 0.67 बिट्स की आवश्यकता है। मुश्किल लगता है ...

यह संपत्ति विशेष रूप से महत्वपूर्ण है यदि आपकी संभावना अधिक है। यदि आप 95% सटीकता के साथ कुछ भविष्यवाणी कर सकते हैं, तो आपको अच्छे अनुमान का प्रतिनिधित्व करने के लिए केवल 0.074 बिट्स की आवश्यकता है। जिसका मतलब है कि आप बहुत कम करने जा रहे हैं।

अब, यह कैसे करें?

अच्छा, यह लगता है की तुलना में यह आसान है। आप संभावनाओं के आधार पर अपनी सीमा विभाजित करेंगे। उदाहरण के लिए, यदि आपके पास 100, 2 संभावित घटनाएं हैं, और पहली बार 95% की संभावना है, तो पहले 95 मान "इवेंट 1" कहेंगे, और अंतिम 5 शेष मान "इवेंट 2" कहेंगे ।

ठीक है, लेकिन कंप्यूटर पर, हम 2 शक्तियों का उपयोग करने के आदी हैं। उदाहरण के लिए, 16 बिट्स के साथ, आपके पास 65536 संभावित मानों की एक श्रृंखला है। बस वही करें: "इवेंट 1" कहने के लिए श्रेणी का पहला 95% (जो 62259 है) ले लो, और शेष "इवेंट 2" कहें। आपको स्पष्ट रूप से "गोल करने" (परिशुद्धता) की समस्या है, लेकिन जब तक आपके पास वितरित करने के लिए पर्याप्त मूल्य हैं, इससे कोई फर्क नहीं पड़ता। इसके अलावा, आप 2 घटनाओं तक सीमित नहीं हैं, आप कई घटनाओं को प्राप्त कर सकते हैं। यह सब मायने रखता है कि प्रत्येक घटना की संभावनाओं के आधार पर मूल्य आवंटित किए जाते हैं।

ठीक है, लेकिन अब मेरे पास "ईवेंट 1" और 3277 "इवेंट 2" कहने के लिए 62259 संभावित मान हैं। मुझे किसे चुनना चाहिए ? ठीक है, उनमें से कोई भी करेगा। गीलेर यह 1, 30, 5500 या 62256 है, इसका अभी भी "इवेंट 1" का अर्थ है।

वास्तव में, यह तय करना कि कौन सा मूल्य चुनना है, वर्तमान अनुमान पर निर्भर नहीं होगा, लेकिन अगले पर।

मान लीजिए कि मेरे पास "ईवेंट 1" है। तो अब मुझे 0 और 62256 के बीच कोई मूल्य चुनना है। अगले अनुमान पर, मेरे पास एक ही वितरण है (95% इवेंट 1, 5% इवेंट 2)। मैं बस इन संभावनाओं के साथ वितरण मानचित्र आवंटित करूंगा। इसके अलावा, इस बार, यह 62256 मूल्यों पर वितरित किया जाता है। और हम इस तरह जारी रखते हैं, प्रत्येक अनुमान के साथ मूल्यों की सीमा को कम करते हैं।

तो वास्तव में, हम "श्रेणियां" परिभाषित कर रहे हैं, जो प्रत्येक अनुमान के साथ संकीर्ण हैं। हालांकि, कुछ बिंदु पर, सटीकता की एक समस्या है, क्योंकि बहुत कम मूल्य रहते हैं।

विचार, बस फिर से श्रेणी को "फुलाएं" है। उदाहरण के लिए, प्रत्येक बार रेंज 32768 (2^15) से नीचे जाती है, तो आप उच्चतम बिट आउटपुट करते हैं, और बाकी को 2 से गुणा करते हैं (प्रभावी रूप से मूल्यों को एक बिट बाएं स्थानांतरित करते हैं)। लगातार इस तरह से, आप बिट्स को एक-एक करके आउटपुट कर रहे हैं, क्योंकि उन्हें अनुमानों की श्रृंखला से निपटारा जा रहा है।

अब संपीड़न के साथ संबंध स्पष्ट हो जाता है: जब सीमा तेजी से संकुचित हो जाती है (पूर्व: 5%), तो आप सीमा से ऊपर की सीमा को वापस पाने के लिए बहुत सारी बिट्स आउटपुट करते हैं। दूसरी ओर, जब संभावना बहुत अधिक है, तो सीमा बहुत धीरे-धीरे संकीर्ण होती है। आप अपनी पहली बिट्स को आउटपुट करने से पहले भी कई अनुमान लगा सकते हैं। इस तरह एक घटना को "थोड़ा सा अंश" में संपीड़ित करना संभव है।

मैंने जानबूझकर इस आलेख को सामान्य रखने के लिए "संभावना", "अनुमान", "घटनाओं" शब्द का उपयोग किया है। लेकिन डेटा संपीड़न के लिए, आप उन्हें अपने डेटा को मॉडल करने के तरीके के साथ प्रतिस्थापित करने के लिए। उदाहरण के लिए, अगली घटना अगले बाइट हो सकती है; इस मामले में, आपके पास 256 हैं।

Answer 2

सभी धन्यवाद के

प्रथम पर स्थित हो सकता!

मैं देख सकता हूँ कि इस विधि के लिए निम्न चरण होते हैं:

1. मानचित्रण बनाना: प्रत्येक अक्षर जो प्रत्येक वर्णमाला के लिए एक सीमा के आकार देता है के लिए घटना के अंश की गणना। तो फिर उन्हें ऑर्डर और
2. इष्टतम कोड

तीसरे भाग थोड़ा मुश्किल है ढूँढें से 0 1

संदेश को देखते हुए करने के लिए रेंज (बिल्कुल स्पष्ट IMHO) की गणना वास्तविक सीमाओं आवंटित। निम्नलिखित एल्गोरिदम का प्रयोग करें।

बी इष्टतम प्रतिनिधित्व होना चाहिए। इसे खाली स्ट्रिंग ('') में शुरू करें। एक्स को न्यूनतम मान और वाई अधिकतम मान दें।

1. डबल x और y: x = 2 * x, y = 2 * y
2. उन दोनों को 1 से अधिक ख को संलग्न 1 कर रहे हैं। चरण 1 पर जाएं।
3. यदि उनमें से दोनों 1 से कम हैं, तो 0 से बी जोड़ें। कदम < 1 1.
4. एक्स तो जाते हैं, लेकिन y> 1, तो ख को 1 संलग्न करें और रोक

ख अनिवार्य रूप से नंबर पर आप संचारण कर रहे हैं के आंशिक हिस्से में शामिल है। उदाहरण के लिए। यदि बी = 011, तो अंश बाइनरी में 0.011 से मेल खाता है।

कार्यान्वयन का कौन सा हिस्सा आपको समझ में नहीं आता है?

Answer 3

शायद यह स्क्रिप्ट अंकगणितीय कोडर का बेहतर मानसिक मॉडल बनाने के लिए उपयोगी हो सकती है: gen_map.py। मूल रूप से यह अंकगणितीय कोडर लाइब्रेरी के डीबगिंग को सुविधाजनक बनाने और इसके लिए यूनिट परीक्षणों की पीढ़ी को सरल बनाने के लिए बनाया गया था। हालांकि यह अच्छी ASCII विज़ुअलाइजेशन बनाता है जो अंकगणितीय कोडिंग को समझने में भी उपयोगी हो सकता है।

एक छोटा सा उदाहरण। कल्पना करें कि हमारे पास 3 प्रतीकों का वर्णमाला है: 0, 1 और 2 संभावनाओं के साथ 1/10, 2/10 और 7/10 संगत रूप से। और हम अनुक्रम [1, 2] को एन्कोड करना चाहते हैं।स्क्रिप्ट दे देंगे निम्नलिखित निर्गम (अब के लिए -b N विकल्प को अनदेखा):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

पहले 6 लाइनों (==== लाइन से पहले) 0.0 से 1.0 जो रिकर्सिवली प्रतीक संभावनाओं के लिए आनुपातिक अंतराल पर विभाजित किया जाता है करने के लिए एक सीमा का प्रतिनिधित्व करते हैं। एनोटेट प्रथम पंक्ति:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

तो हम फिर से प्रत्येक अंतराल पर उप-विभाजन:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

ध्यान दें, कि कुछ अंतराल उप-विभाजित नहीं कर रहे हैं। ऐसा तब होता है जब दिए गए परिशुद्धता के भीतर प्रत्येक सबिनटरवाल का प्रतिनिधित्व करने के लिए पर्याप्त जगह नहीं होती है (जिसे -b विकल्प द्वारा निर्दिष्ट किया गया है)।

प्रत्येक पंक्ति इनपुट से एक प्रतीक से मेल खाती है (हमारे मामले में - अनुक्रम [1, 2])। प्रत्येक इनपुट प्रतीक के लिए subintervals का पालन करके हम एक अंतिम अंतराल प्राप्त करेंगे कि हम न्यूनतम बिट्स के साथ एन्कोड करना चाहते हैं। हमारे मामले में यह दूसरी लाइन पर पहली बार एक 2 subinterval है:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

7 लाइनों ( ==== के बाद) के बाद

ही 1.0 अंतराल 0.0 प्रतिनिधित्व करते हैं, लेकिन द्विआधारी संकेतन के अनुसार उप-विभाजित किया। प्रत्येक पंक्ति आउटपुट का एक बिट है और 0 और 1 के बीच चयन करके आप बाएं या दाएं आधा-सबिनटरवल चुनते हैं। उदाहरण के लिए बिट्स 01 एक दूसरी पंक्ति पर [0.25, 05) subinterval से मेल खाती है:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

अंकगणित सांकेतिक शब्दों में बदलनेवाला के विचार उत्पादन बिट्स के लिए है (0 या 1) जब तक इसी अंतराल पूरी तरह से अंदर (या इसके बराबर) हो जाएगा अंतराल निर्धारित इनपुट अनुक्रम द्वारा। हमारे मामले में यह 0011 है। ~~~~ लाइन दिखाती है कि हमारे पास अंतराल की पहचान करने के लिए पर्याप्त बिट्स हैं जहां हम चाहते हैं।

| द्वारा बनाई गई लंबवत रेखाएं बिट अनुक्रमों (पंक्तियों) की श्रेणी दिखाती हैं जिनका उपयोग इनपुट अनुक्रम को एन्कोड करने के लिए किया जा सकता है।