संकुचित स्ट्रिंग स्टोरेज

Question

आइए कहें कि मेरे पास कई ऑब्जेक्ट्स हैं जिनमें गैर-तुच्छ लंबाई (लगभग ~ 3-4 केबी) की तार शामिल हैं। स्ट्रिंग्स एक-दूसरे से अलग हैं, फिर भी एक ही समय में बहुत सारे सामान्य भाग/बाद के होते हैं। औसतन किसी भी व्यक्तिगत स्ट्रिंग का 80-90% दूसरों के साथ भी निहित होता है। डेटा को संपीड़ित करने के लिए इस विशाल अनावश्यकता का स्वचालित रूप से उपयोग करने का कोई आसान तरीका है?
आदर्श रूप से समाधान सी ++ होगा और उपयोगकर्ता के लिए पारदर्शी होगा (यानी मैं इसका उपयोग कर सकता हूं जैसे कि मैं नियमित रूप से पढ़ने के लिए केवल std :: स्ट्रिंग का उपयोग कर रहा था लेकिन संकुचित स्टोरेज से पढ़ने के बजाय)।

Answer 1

एल्गोरिदमिक रूप से, Lempel–Ziv–Welch सभी वस्तुओं/तारों के लिए एक शब्दकोश के साथ एक अच्छी शुरुआत हो सकती है।

Answer 2

तार के आम भागों आम कर रहे हैं, क्योंकि वे दूसरे तार से बना रहे हैं, तो आप कुछ कर्षण stlportrope वर्ग है, जो एक std :: स्ट्रिंग की तरह पूरी दुनिया के लिए लग रहा है का उपयोग करके प्राप्त कर सकता है, लेकिन स्ट्रिंग का उपयोग करता है लिखने पर प्रति के साथ पेड़ प्रतिनिधित्व कि उन दोनों को बहुत अंतरिक्ष कुशल (आम सबस्ट्रिंग साझा कर रहे हैं) और आवेषण और नष्टकरण (लॉग (एन)) में बहुत अच्छा बना देता है

रस्सी उपयोग कब करें:

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

रस्सी का उपयोग करने के लिए नहीं है:

• आप अपने आवेदन (डिस्क से, या एक नेटवर्क पर) के डोमेन से बाहर के कई दस्तावेज लोड हो रहा है और संशोधन के बिना उन्हें प्रयोग कर रहे हैं। रस्सी तारों को साझा नहीं करती है अगर उन्हें एक रस्सी से दूसरे में कॉपी नहीं किया जाता है। यदि आप आम सबस्ट्रिंग्स को खोजने के लिए काम करने के लिए सक्षम हो सकते हैं, तो रस्सी का उपयोग अभी भी आपके अंतिम प्रतिनिधित्व में सुधार के लिए किया जा सकता है।

Answer 3

आप huffman coding कार्यान्वयन का उपयोग नहीं कर सकते हैं, इसके अलावा भाषाओं में ज़िप एल्गोरिदम भी हैं (जैसे सी # और जावा) और आप उनका उपयोग कर सकते हैं।

यदि आप सुनिश्चित करते हैं कि 80-90% सभी में दोहराया गया है, तो सभी शब्दों का एक शब्दकोश बनाएं, फिर प्रत्येक स्ट्रिंग को शब्दकोष शब्द की स्थिति संग्रहित करने के लिए, इसका मतलब बड़े आकार (10000 यानी) का थोड़ा सरणी है और चिह्नित करें संबंधित स्थिति bits[i] से 1 यदि वर्तमान स्ट्रिंग में words[i] मौजूद है। लगता है कि प्रत्येक शब्द की लंबाई 5 वर्ण है तो संक्षिप्त नाम 1/5 आकार लेता है।

Answer 4

जैसा कि @ सईद ने उल्लेख किया है, एक सरल हफमैन कोडिंग यहां अच्छा प्रदर्शन करेगा।

शब्दकोश में कोई आवश्यकता नहीं है, यदि आम शब्द apriori (आपने उल्लेख किया है कि यह एक HTML है) है। बस कई HTML फ़ाइलों से सांख्यिकीय डेटा का उपयोग करके एक हफमैन तालिका का प्रीकंप्यूट करें (ध्यान दें कि आप एक ही प्रतीक से पूरे टैग को एन्कोड कर सकते हैं, और आपके पास जितने चाहें उतने प्रतीक हो सकते हैं)।