LZW संपीड़न कम स्मृति की स्थिति

Question

के तहत/विसंपीड़न

किसी को भी संकेत दिए गए कि कैसे मैं कम स्मृति की स्थिति (< 2k) में LZW संपीड़न/विसंपीड़न लागू कर सकते हैं दे सकते हैं। क्या यह संभव है?

Answer 1

मेरे सबसे अच्छा सिफारिश BusyBox स्रोत की जांच करने और उनके LZW कार्यान्वयन पर्याप्त अपने वातावरण में काम करने के लिए छोटा है, तो देखने के लिए है।

Answer 2

यह 15 साल से अधिक कर दिया गया है के बाद से मैं पिछले, LZW संपीड़न एल्गोरिथ्म के साथ खेला जाता तो एक अलग नज़रिए के साथ निम्न ले।

स्मृति बाधाओं को देखते हुए, यह सबसे अच्छा होना मुश्किल होगा। आपके द्वारा निर्मित शब्दकोश जो आपके पास उपलब्ध है, उसके विशाल बहुमत का उपभोग करने जा रहा है। (कि कोड + स्मृति < = 2k मान लिया जाये।)

अपने शब्दकोश के लिए एक छोटे से तय आकार उठाओ। 1024 प्रविष्टियां कहें।

शब्दकोष की प्रत्येक प्रविष्टि का रूप ले चलो ....

struct entry { 
    intType prevIdx; 
    charType newChar; 
}; 

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

। आप यथासंभव कसकर चीजों को पैक करना चाहते हैं। 1024 प्रविष्टियों को स्टोर करने के लिए 10 बिट ले जाएगा। आपका नया चरित्र, 8 बिट्स लेगा। कुल = 18 बिट्स।

18 बिट्स * 1024 प्रविष्टियां = 18432 बिट्स या 2304 बाइट्स।

पहली नज़र में यह बहुत बड़ा दिखाई देता है। हम क्या करें? इस तथ्य का लाभ उठाएं कि पहली 256 प्रविष्टियां पहले ही ज्ञात हैं - आपके सामान्य विस्तारित एसीआई सेट या आपके पास क्या है। इसका मतलब है कि हमें वास्तव में 768 प्रविष्टियों की आवश्यकता है।

768 * 18 बिट्स = 13824 बिट्स या 1728 बाइट्स।

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

मुझे आशा है कि इस मदद करता है। कि हर किसी का उपयोग करता है

Answer 3

zlib पुस्तकालय (एम्बेडेड के लिए) अन्य समस्याओं के साथ फूला हुआ है। मुझे पूरा यकीन है कि यह आपके मामले के लिए काम नहीं करेगा। मेरे पास 16K शायद थोड़ी अधिक स्मृति थी और इसे फिट नहीं कर सका। यह स्मृति के बड़े हिस्से आवंटित करता है और शून्य करता है और सामान की प्रतियां रखता है, आदि। एल्गोरिदम शायद ऐसा कर सकता है लेकिन मौजूदा कोड ढूंढना चुनौती है।

मैं http://lzfx.googlecode.com साथ चला गया विसंपीड़न पाश छोटे है, यह बड़े lz प्रकार संपीड़न कि पहले परिणाम पर निर्भर करता है, ताकि आप असम्पीडित परिणाम के लिए उपयोग की आवश्यकता है ... अगले बाइट एक 0x5, अगले बाइट है 0x23 है, अगले 15 बाइट्स 15 200 बाइट्स की एक प्रतिलिपि हैं, अगले 6 बाइट 127 की एक प्रति हैं ... नई एलजी एल्गोरिदम चरणीय चौड़ाई तालिका आधारित है जो लागू हो सकती है या नहीं ।

मैं दोहराव वाले डेटा से निपट रहा था और कुछ के नीचे कुछ के नीचे निचोड़ने की कोशिश कर रहा था, मुझे लगता है कि संपीड़न लगभग 50% था, बहुत अच्छा नहीं था, लेकिन नौकरी और डिकंप्रेशन दिनचर्या छोटी थी।उपरोक्त lzfx पैकेज छोटा है, ज़्लिब की तरह नहीं, दो मुख्य कार्यों की तरह, जिनके पास कोड है, न कि फाइलों के दर्जनों। यदि आप चाहें तो आप बफर की गहराई को बदल सकते हैं, शायद संपीड़न एल्गोरिदम में सुधार कर सकते हैं। मुझे डिकंप्रेशन कोड (जैसे कोड की 20 या 30 लाइनों की तरह) को संशोधित करना पड़ा था, यह पॉइंटर भारी था और मैंने इसे सरणी में बदल दिया क्योंकि मेरे एम्बेडेड वातावरण में पॉइंटर्स गलत जगह पर थे। शायद यह एक अतिरिक्त रजिस्टर जलता है या इस पर निर्भर करता है कि आप इसे कैसे लागू करते हैं और आपके कंपाइलर को कैसे लागू करते हैं। मैंने यह भी किया ताकि मैं बाइट्स के फायर और स्टोर्स को सार कर सकूं क्योंकि मैंने उन्हें स्मृति में पैक किया था जो बाइट एड्रेसेबल नहीं था।

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

Answer 4

क्या कोई पॉइंटर्स दे सकता है कि मैं कम स्मृति स्थितियों में 0z2k) में lzw संपीड़न/डिकंप्रेशन कैसे कार्यान्वित कर सकता हूं। क्या यह संभव है?

क्यों LZW? एलजेडब्लूडब्ल्यू को बहुत सारी मेमोरी चाहिए। यह हैश/शब्दकोश और संपीड़न अनुपात पर आधारित हैश/शब्दकोश आकार के आनुपातिक है। अधिक स्मृति - बेहतर संपीड़न। कम स्मृति - आउटपुट इनपुट से भी बड़ा हो सकता है।

मैंने बहुत लंबे समय तक एन्कोडिंग को छुआ नहीं है, लेकिन आईआईआरसी Huffman coding स्मृति खपत की बात आती है तो थोड़ा बेहतर है।

लेकिन यह सब उस जानकारी के प्रकार पर निर्भर करता है जिसे आप संपीड़ित करना चाहते हैं।

Answer 5

यदि संपीड़न एल्गोरिदम की पसंद पत्थर में सेट नहीं है, तो आप इसके बजाय gzip/LZ77 आज़मा सकते हैं। यहाँ एक बहुत ही सरल कार्यान्वयन मैं का इस्तेमाल किया और एक बार अनुकूलित है:

ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c

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

बड़ा प्लस यह है कि यह सार्वजनिक डोमेन है ताकि आप इसका उपयोग कर सकें, हालांकि आप इसे पसंद कर सकते हैं!

Answer 6

मैंने LZSS का उपयोग किया है। मैंने codeHaruhiko Okumura से आधार के रूप में उपयोग किया। यह शब्दकोश के रूप में असंपीड़ित डेटा (2 के) के अंतिम भाग का उपयोग करता है। यदि आपके पास स्मृति में उपलब्ध सभी असम्पीडित डेटा हैं तो मेरे द्वारा लिंक किए गए कोड को लगभग कोई स्मृति उपयोग करने के लिए संशोधित किया जा सकता है। थोड़ी सी गुगल के साथ आप पाएंगे कि कई सारे कार्यान्वयन।

Answer 7

typedef unsigned int  UINT; 
typedef unsigned char BYTE; 

BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize); 
BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);