डेटा संरचना को स्टोर/पुनर्प्राप्त करें

Question

मैंने पाइथन में पूर्ण-पाठ-खोज करने के लिए प्रत्यय पेड़ लागू किया है, और यह वास्तव में अच्छी तरह से काम कर रहा है। लेकिन एक समस्या है: अनुक्रमित पाठ बहुत बड़ा हो सकता है, इसलिए हम रैम में पूरी संरचना नहीं कर पाएंगे।

छवि: शब्द BANANAS के लिए प्रत्यय पेड़ (मेरे परिदृश्य में, एक पेड़ 100000 गुना बड़ी कल्पना)।

तो, इसके बारे में थोड़ा सा शोध करने के बाद मुझे pickle मॉड्यूल मिला, "लोडिंग" और "डंपिंग" ऑब्जेक्ट्स के लिए एक महान पायथन मॉड्यूल/फ़ाइलों में से, और अनुमान लगाया? यह मेरी डेटा संरचना के साथ अद्भुत काम करता है।

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

---

पाद-टिप्पणी: हालांकि मैं python के रूप में इस सवाल का टैग किया है, प्रोग्रामिंग भाषा सवाल का महत्वपूर्ण हिस्सा नहीं है, डिस्क भंडारण/पुन: प्राप्त करने की रणनीति वास्तव में मुख्य बिंदु है।

Answer 1

यदि pickle पहले से ही आपके लिए काम कर रहा है, तो आप ZODB पर एक नज़र डालना चाहते हैं जो pickle के शीर्ष पर कुछ कार्यक्षमता जोड़ता है। प्रलेखन को देखते हुए, मैंने यह पैराग्राफ देखा जो आपके पास होने वाली आकार की चिंताओं को संबोधित करता है:

डेटाबेस स्मृति और संग्रहण के बीच स्वतंत्र रूप से वस्तुओं को स्थानांतरित करता है। यदि ऑब्जेक्ट का उपयोग थोड़ी देर में नहीं किया गया है, तो इसे रिलीज़ किया जा सकता है और अगली बार इसका उपयोग होने पर स्टोरेज से लोड की गई सामग्री हो सकती है।

Answer 2

sqlite में संग्रहीत करने के बारे में क्या?

SQLite:

• , डेटा की अप करने के लिए 2 टेराबाइट्स,
• एसक्यूएल प्रश्नों का समर्थन करता है के लिए समर्थन हासिल है
• इन-ऐप डेटा भंडारण के लिये महान प्रतिस्थापन है,
• समर्थन कर सकते हैं ~ 100k का दौरा प्रति दिन (यदि औसत वेब एप्लिकेशन के लिए उपयोग किया जाता है),

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

Answer 3

शायद आप सीपीकल और bsddb डेटाबेस को जोड़ सकते हैं जो आपको अपने मसालेदार नोड्स को एक डिक्शनरी-जैसी ऑब्जेक्ट में स्टोर करने की अनुमति देगा जो फाइल सिस्टम पर संग्रहीत किया जाएगा; इस प्रकार आप बाद में डेटाबेस लोड कर सकते हैं और वास्तव में अच्छे प्रदर्शन के साथ आवश्यक नोड्स से प्राप्त कर सकते हैं।

एक बहुत ही सरल तरीके से:

import bsddb 
import cPickle 

db = bsddb.btopen('/tmp/nodes.db', 'c') 
def store_node(node, key, db): 
    db[key] = cPickle.dumps(node) 

def get_node(key, db): 
    return cPickle.loads(db[key]) 

Answer 4

एक प्रभावी तरीका एक संरचना का प्रबंधन करने के लिए इस एक स्मृति-मैप की गई फ़ाइल उपयोग करने के लिए है की तरह। फ़ाइल में, नोड पॉइंटर्स के संदर्भों को संग्रहीत करने के बजाय, आप फ़ाइल में ऑफ़सेट स्टोर करते हैं। डिस्क पर संग्रहीत करने के लिए उपयुक्त स्ट्रीम में नोड डेटा को क्रमबद्ध करने के लिए आप अभी भी pickle का उपयोग कर सकते हैं, लेकिन pickle मॉड्यूल के बाद से आप संदर्भों को संग्रहीत करना चाहते हैं क्योंकि मॉड्यूल आपके पूरे पेड़ को एक बार में एम्बेड करना चाहता है (जैसा आपने देखा है)।

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

आप फ़ाइल की शुरुआत में पहला नोड स्टोर कर सकते हैं, और ऑफसेट्स जो अगले नोड को इंगित करते हैं। अगले नोड को पढ़ना सिर्फ फाइल में सही ऑफसेट से पढ़ने का मामला है।

मेमोरी-मैप की गई फ़ाइलों का लाभ यह है कि वे स्मृति में लोड नहीं होते हैं, लेकिन केवल आवश्यकता होने पर डिस्क से पढ़ते हैं। मैंने यह मशीन (64-बिट ओएस पर) एक मशीन पर 30 जीबी फ़ाइल के साथ किया है जिसमें केवल 4 जीबी रैम स्थापित है, और यह ठीक काम करता है।

Answer 5

संकुचित प्रत्यय पेड़ की बजाय कोशिश करें।

मुख्य विचार यह है कि 1 वर्ण के बहुत सारे नोड्स होने के बजाय, आप उन्हें कई अक्षरों के 1 नोड में कॉम्पैक्ट कर सकते हैं जिससे अतिरिक्त नोड्स बचाए जा सकते हैं।

यह लिंक यहां (http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml) कहता है कि आप 160 एमबी प्रत्यय पेड़ को 33 एमबी संपीड़ित प्रत्यय पेड़ में बदल सकते हैं। काफी लाभ।

ये संपीड़ित पेड़ विशाल तारों पर अनुवांशिक सबस्ट्रिंग मिलान के लिए उपयोग किए जाते हैं। मैं एक प्रत्यय पेड़ के साथ स्मृति से बाहर निकलता था, लेकिन जब मैंने इसे संपीड़ित किया, तो स्मृति त्रुटि से गायब हो गया।

मेरी इच्छा है कि मुझे एक अवैतनिक लेख मिल सके जो कार्यान्वयन को बेहतर तरीके से समझाता है। (http://dl.acm.org/citation.cfm?id=1768593)