अजगर उपसर्ग पेड़

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

संक्षेप में, हम मान सकते हैं कि datrie.Trie मानक अजगर तानाशाही के लिए एक प्रतिस्थापन है, जो कुछ शर्तों (कुंजी - तार) के तहत कम मेमोरी लेता है, एक एकल तत्व प्राप्त करने की एक तुलनीय गति है और अतिरिक्त संचालन का समर्थन करता है (किसी दिए गए स्ट्रिंग के सभी उपसर्ग प्राप्त करना, सभी प्राप्त करना किसी दिए गए लाइन, आदि से शुरू होने वाली लाइनें) जो शब्दकोश संचालन के रूप में तेजी से काम करती हैं।

पायथन 2.6-3.3 के तहत काम करता है, यूनिकोड, एलजीपीएल लाइसेंस का समर्थन करता है।



डेट्री लिबडाट्री लाइब्रेरी पर साइथन रैपर है। लिबडाट्री उपसर्ग वृक्ष के एक संस्करण को लागू करता है जिसमें नोड्स के बीच संक्रमण के लिए राज्य मशीन को विशेष 2 सरणियों + प्रत्यय संपीड़न में संग्रहीत किया जाता है (शाखाएं जो शाखा नहीं करती हैं उन्हें "पूंछ" के एक और अलग सरणी में संग्रहीत किया जाता है)। यह ट्राइ (HAT-trie और इतने पर तेज होना चाहिए) का एक "कला का राज्य" संस्करण नहीं है, लेकिन विकल्प काफी तेज / कुशल है और एक अच्छा तैयार-किए गए कार्यान्वयन के साथ (और कार्यान्वयन अभ्यास में किसी भी एल्गोरिथ्म को मार सकता है)।

अजगर के लिए त्रि-आकार की संरचनाओं के मौजूदा विकल्प मेरे लिए उपयुक्त नहीं थे। विशुद्ध रूप से पायथोनिक कार्यान्वयन अनिवार्य रूप से बहुत सारी स्मृति का उपभोग करेंगे, वे तुरंत बह गए। अजगर के लिए त्रि-आकार की संरचनाओं के अन्य कार्यान्वयन:

• बायोपथॉन में trie.c। यह यूनिकोड (हालांकि यह ठीक है) का समर्थन नहीं करता है, यह 3.x के तहत काम नहीं करता है (और इसे 3.x के तहत काम करने के लिए, आपको रैपर को फिर से लिखना होगा, क्योंकि लाइब्रेरी को "नंगे" सी-एक्सटेंशन के रूप में लागू किया गया है);
• buriy की github.com/buriy/python-chartrie काफी तेज है (__getitem__ अंत में डेटरी से तेज है), इसमें बहुत अधिक मेमोरी लगती है (इसे ठीक करने के लिए, आपको संभवतः डेटा संरचना को बदलने की आवश्यकता है, अर्थात लाइब्रेरी का आधार), पर्याप्त नहीं है। कार्यात्मक, यूनिकोड का समर्थन नहीं करता (हालांकि यह ठीक है);
• www.dalkescientific.com/Python/PyJudy.html - पुराना, जटिल, यह स्पष्ट नहीं है कि यह काम करता है (यह लिखा गया है कि 2.3 और 2.4 का समर्थन करता है)

हो सकता है कि कुछ और हो, लेकिन, किसी भी मामले में, मैंने "यह काम किया, यह सभी के लिए काम करता है!" विकल्प नहीं खोज पाया, इसलिए मुझे लगता है कि मैं सी को याद करने की इच्छा को कवर करने और एक सामान्य की कमी का उपयोग करके साइथॉन और पायथन में बेहतर होने में कामयाब रहा। अजगर के लिए trie कार्यान्वयन।

स्थापना (जैसा कि आमतौर पर एक्सटेंशन स्थापित करते समय होता है, आपको एक कंपाइलर की आवश्यकता होती है):

pip install datrie

निर्माण:

 import string import datrie trie = datrie.Trie(string.ascii_lowercase) 

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

यह मुझे लगता है कि cp1251 जैसे एकल-बाइट एन्कोडिंग के साथ अभ्यास करना संभव होगा और लगभग एक ही कार्यक्षमता और दक्षता है, लेकिन चरित्र श्रेणियों के साथ दृष्टिकोण भी अच्छी तरह से काम करता है, कि यह कैसे libdatrie और ठीक में किया गया था। इसलिए मैं लिखता हूं कि "यूनिकोड का समर्थन नहीं करता है - यह ठीक है" - ट्राइ के मामले में, एकल-बाइट एन्कोडिंग एक सुविधाजनक विकल्प हो सकता है।

फिर trie के साथ आप एक शब्दकोश की तरह काम कर सकते हैं:

 >>> trie[u'foo'] = 5 >>> trie[u'foobar'] = 10 >>> trie[u'bar'] = 'bar value' >>> trie.setdefault(u'foobar', 15) 10 >>> u'foo' in trie True >>> trie[u'foo'] 5 

चाबियाँ यूनिकोड होनी चाहिए :) अजगर 3.x में यह काफी स्वाभाविक है, 2.x में आपको अक्षर u को उदाहरणों में डालना होगा, माफ करना। मान किसी भी पाइथोनिक ऑब्जेक्ट हो सकते हैं, जो ट्राई सी-कार्यान्वयन के लिए विशिष्ट नहीं है (आमतौर पर मान के रूप में पूर्णांक होता है)। दरअसल, "अंदर" मान वास्तव में पूर्णांक हैं, लेकिन "वास्तविक" मानों की एक सरणी में उनका उपयोग सूचकांक के रूप में किया जाता है। उन लोगों के लिए जिन्हें इस सुविधा की आवश्यकता नहीं है (उदाहरण के लिए, मान बिल्कुल दिलचस्प नहीं हैं), डेट्री में डेटरी है।बेसटी है, जो थोड़ा तेज है और केवल संख्याओं को संग्रहीत कर सकता है।

गति के बारे में थोड़ा सा। सभी माप तीनों पर किए गए थे। एक सौ हज़ार अद्वितीय रूसी और अंग्रेजी शब्दों (50/50) और "1" के अंतर-मूल्यों के साथ, अन्य माप (एक मिलियन यूआरएल में) यहां या अपने स्वयं के डेटा पर किए जा सकते हैं । । मैंने केवल मात्रा के क्रम के कुछ सामान्य विचार रखने के लिए, और पुस्तकालय में रजिस्टरों को ट्रैक करने के लिए गति माप लिया, इसलिए उन्हें तदनुसार रखा; सभी स्रोत कोड और डेटा भंडार में हैं। इसके अलावा, मैं विभिन्न कार्यों की असममित जटिलता के बारे में कहीं भी नहीं लिखूंगा, क्योंकि उसकी खोजबीन नहीं की। सिद्धांत रूप में, यह विकिपीडिया से उदाहरण के लिए होना चाहिए (उदाहरण के लिए, एक तत्व प्राप्त करना या उपसर्ग द्वारा खोजना - O (m), जहाँ m प्रमुख लंबाई है), लेकिन कार्यान्वयन विवरण (दोनों libdatrie और मेरे आवरण) सब कुछ बदल सकते हैं; अगर कोई उपयुक्त ग्राफ बनाता है, तो मैं निश्चित रूप से आभारी रहूंगा।

एक तत्व प्राप्त करने के संचालन, में जाँच करना, एक मानक शब्दकोश की तुलना में औसत 2-3 गुना धीमी गति से एक तत्व के काम को अद्यतन करना (यानी जल्दी से, मेरे बीच में यह पूर्वोक्त त्रि के लिए 1 से 3 मिलियन संचालन प्रति सेकंड से है)। एक अपवाद तीनों में एक नए मूल्य का सम्मिलन है, यह बहुत धीमी गति से काम करता है (रूसी और अंग्रेजी शब्दों के साथ एक ही त्रि के लिए प्रति सेकंड लगभग 50 हजार ऑपरेशन)। एक ही समय में, ऐसे डेटा पर तीनों रैम में बहुत कम जगह लेते हैं: 3-5M (दुभाषिया पर निर्भर करता है) बनाम 20M + एक नियमित शब्दकोश में (मैंने स्मृति अनाड़ी को मापा और मैं विशिष्ट संख्याओं के लिए वाउच नहीं कर सकता) ।

यानी datrie.Trie को तानाशाही के प्रतिस्थापन के रूप में इस्तेमाल किया जा सकता है, यदि बड़ी संख्या में बहुत लंबी लाइनें नहीं हैं (उदाहरण के लिए, शब्द या यूआरएल), डेटा का उपयोग मुख्य रूप से रीड-ओनली मोड (या "अपडेट-ओनली") में किया जाता है और आप रैम मेमोरी को सेव करना चाहते हैं। 2-3 गुना कम गति की लागत पर।

ताकि यह छद्म-रीड-ओनली बहुत शर्मनाक न हो, ट्राई को एक फाइल में सेव किया जा सकता है और एक फाइल से लोड किया जा सकता है:

 >>> trie.save('my.trie') >>> trie2 = datrie.Trie.load('my.trie') 

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

आप जांच कर सकते हैं कि क्या त्रि में ऐसे तत्व हैं जिनकी कुंजी इस उपसर्ग से शुरू होती है (यह चेक में एक साधारण से भी तेज है):

 >>> trie.has_keys_with_prefix(u'fo') True 

आप इस पंक्ति के सभी उपसर्गों को ढूँढ सकते हैं जो इस त्रि में हैं (यह धीमी है, परीक्षणों के अनुसार - 500-600 हजार ऑपरेशन / सेकंड):

 >>> trie.prefixes(u'foobarbaz') [u'foo', u'foobar'] >>> trie.prefix_items(u'foobarbaz') [(u'foo', 5), (u'foobar', 10)] 

आप उन सभी तत्वों को पा सकते हैं जिनकी कुंजी इस लाइन से शुरू होती है:

 >>> trie.keys(u'fo') [u'foo', u'foobar'] >>> trie.items(u'fo') [(u'foo', 5), (u'foobar', 10)] >>> trie.values(u'foob') [10] 

अंतिम उदाहरण में, अधिकांश समय अब ​​निर्माण परिणामों पर खर्च किया जाता है, बजाय खोज के, इसे अनुकूलित किया जा सकता है; अब गति लगभग 150-300 हजार मान / सेकंड थी (उदाहरण के लिए, लंबाई 7 के उपसर्ग और 3 मानों की औसत के साथ, यह 70 हजार ऑपरेशन / सेकंड है)।

Datrie.Trie में अभी भी विभिन्न विधियाँ हैं, उन पर मदद और गति माप के अतिरिक्त परिणाम रिपॉजिटरी में README में देखे जा सकते हैं।

Pypy के तहत, सब कुछ डेबियन पर शुरू हुआ (cpython के मुकाबले 10 गुना धीमा); पेपी के नीचे एक खसखस ​​पर यह शुरू नहीं हुआ (एक नियमित अजगर के साथ इसे एक खसखस, और लिनक्स पर, और खिड़कियों के नीचे काम करना चाहिए)। C API - pypy में एक्सटेंशन हमेशा धीमा रहेगा क्योंकि एक cpyext बैसाखी के माध्यम से काम करते हैं, और साइथन सी एक्सटेंशन एपीआई उत्पन्न करता है। आप ctypes में एक आवरण लिख सकते हैं, लेकिन यह नियमित अजगर के तहत धीमा होगा (और यह तथ्य नहीं है कि pypy के तहत तेजी से) + ctypes एक्सटेंशन वितरित करना असुविधाजनक है। Pypy के लोग अब cffi को देख रहे हैं, यह वादा करते हुए कि यह तेज़ होगा (cpython और pyp दोनों के तहत)। इसके अलावा, शायद साइफन Cffi एक्सटेंशन उत्पन्न करने के लिए किसी दिन सीखेंगे, सी एक्सटेंशन एपीआई नहीं। तब, शायद, खुशी आएगी) इस बीच, मुझे नहीं पता कि मुझे क्या करना है। मैं नहीं, शायद; किसी भी तरह सब कुछ लिनक्स और ठीक काम करता है।

कार्यान्वयन के दौरान, मुझे अजगर में एक रुका हुआ utf_32_le कोडेक मिला। पैच के साथ एक बग है ( bugs.python.org/issue15027 ), लेकिन पैच अभी तक प्रतिबद्ध नहीं है। प्रारंभ में, डेट्री में सभी ऑपरेशनों ने 10 गुना धीमी गति से काम किया, लेकिन फिर एक जगह वे मानक अजगर utf_32_le के साथ स्ट्रिंग को एन्कोडिंग के बिना करने में कामयाब रहे और सब कुछ बेहतर काम किया। इस कोडेक का उपयोग "हॉट" स्थानों के एक जोड़े में किया जाता है, इसलिए मुझे लगता है कि यदि इसे त्वरित किया जाता है, तो डेट्री में कुछ ऑपरेशन 2 गुना तेजी से कमा सकते हैं।

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

हमेशा की तरह, पैच, बग रिपोर्ट, विचार, बेंचमार्क, पुल अनुरोध, आदि का स्वागत है!

github / bitbucket , जो भी अधिक सुविधाजनक हो।