PHP में trie उपसर्ग पेड़ के निम्न-स्तरीय कार्यान्वयन

प्रस्तावना

यहाँ वर्णित PHP trie कार्यान्वयन, शब्दकोश को अब तक बहुत मोटा बनाता है, जो तदनुसार स्मृति में लोड होने में काफी समय लेता है, जो अपने काम की बहुत अच्छी गति को बाहर करता है। खोज की गति ~ 80 हजार शब्द प्रति सेकंड है। डिक्शनरी opencorpora.org के शब्दकोश की सूची से बनाई गई है और इसमें 389844 शब्द शामिल हैं। असम्पीडित रूप में, शब्दकोश का वजन ~ 150mb और संकुचित gzip ~ 6mb है। हालांकि, बहुत अच्छे प्रदर्शन परिणाम यह साबित करते हैं कि शुद्ध PHP में आप पूरी तरह से कार्यात्मक ट्राइ प्रीफ़िक्स ट्री बना सकते हैं।

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

यह सब कैसे शुरू हुआ

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

PHP में पहले से ही एक समान पुस्तकालय है जिसे phpmorhy कहा जाता है। यह काफी तेज़ी से काम करता है और मैं इसका उपयोग करूँगा और कुछ भी आविष्कार नहीं करूँगा, लेकिन इसमें डिक्शनरी कंपाइलर को एक अलग गैर-PHP अनुप्रयोग के रूप में बनाया गया है, जिससे मेरे लिए इस लाइब्रेरी का उपयोग करना असंभव हो जाता है। पुस्तकालय स्वयं लंबे समय से प्रतीक्षित एओटी शब्दकोश के आधार पर बनाया गया है, जो इसकी उपयोगिता को और कम कर देता है।

सप्ताह और महीने बीत गए, मैंने खाबरोवचनिन का एक लेख पढ़ा, फिर आई। सेगलोविच का एक लेख , एक खोज इंजन के लिए एक तेज़ रूपात्मक एल्गोरिथम पर, फिर विभिन्न लेखों का एक गुच्छा।

थोड़ा-थोड़ा करके, मैं अपने खुद के लुनपार्क को लाठी और एक रूपात्मक विश्लेषक की हड्डियों के साथ लिखने के लिए परिपक्व हो गया हूं। मुझे लगता है: " ठीक है, प्रगति आगे बढ़ी है, पीएचपी में आप पहले से ही मानव जीनोम को पार्स कर सकते हैं! "

मैंने opencorpora.org शब्दकोश लिया, इसे mysql में डाला और 2 हजार शब्दों प्रति सेकंड की खोज गति प्राप्त की। मुझे लगता है कि शब्दकोश को स्मृति में लोड करना आवश्यक है। और यहाँ यह पता चला है कि एक सरणी या एक वस्तु की तरह PHP में नियमित रूप से डेटा संरचनाएं उपलब्ध कराने के लिए, आपको 3 मिलियन के शब्दकोश में लगभग 3 जीबी रैम स्टोर करने की आवश्यकता है। सभी php trie कार्यान्वयन जो मेरे सामने आए, वे केवल कार्य के तर्क को प्रदर्शित करने के लिए एक ट्यूटोरियल के रूप में उपयुक्त थे, क्योंकि वे स्वयं मूल PHP डेटा भंडारण संरचनाओं पर बनाए गए थे।

शब्दकोश भंडारण उपकरण और संचालन का सिद्धांत

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

जैसा कि आप जानते हैं, तीनों उपसर्ग पेड़ नोड्स के होते हैं। एक नोड एक उपसर्ग को संग्रहीत करता है, बाद के नोड्स (वंशज) से जोड़ता है, और इस तथ्य के लिए एक संकेतक है कि यह उपसर्ग श्रृंखला में अंतिम है। भारतीय यहाँ त्रि के बारे में काफी समझदारी से कहते हैं ।

मेरे त्रि-कार्यान्वयन में नोड्स 154 बाइट्स की निश्चित लंबाई के डेटा ब्लॉक हैं। पहले 6 बाइट्स (48 बिट्स) में वारिस का बिट मास्क होता है। पहले 46 बिट्स रूसी वर्णमाला, संख्या, उद्धरण चिह्न, हाइफ़न और एपोस्ट्रोफ़ हैं। एपोस्ट्रोफ को इसलिए जोड़ा गया क्योंकि opencorpora.org शब्दकोश में "कोटे डी -वायर" शब्द है, जो एपोस्ट्रोफ संकेत का उपयोग करता है। 47 वें बिट का उपयोग शब्द के ध्वज को संग्रहीत करने के लिए किया जाता है। बिटमास्क के बाद निम्न 148 बाइट्स का उपयोग नोड के वारिसों के संदर्भों को संग्रहीत करने के लिए किया जाता है। प्रति चरित्र 3 बाइट्स (46 * 3 = 148)।

नोड्स को एक स्ट्रिंग में बाइनरी डेटा के रूप में संग्रहीत किया जाता है। वांछित अनुभाग तक पहुंच को रूट () फ़ंक्शन और बाद के अनपैक () अनपैकिंग का उपयोग करके किया जाता है।

फिक्स्ड-लेंथ नोड्स का उपयोग एड्रेसिंग प्रक्रिया को सरल करता है। वांछित नोड पर स्विच करने के लिए, इसकी क्रम संख्या (आईडी) और नोड की लंबाई जानना पर्याप्त है। हम लंबाई से सीरियल नंबर को गुणा करते हैं और लाइन की शुरुआत के सापेक्ष ऑफसेट का पता लगाते हैं - सब कुछ बहुत सरल है।

अंजीर। 1 संग्रहण योजना

कमियों

भंडारण योजना का उपयोग पते को सरल करता है, लेकिन यह अंतरिक्ष को खा जाता है। 380 हजार शब्दों के भंडारण के लिए सिर्फ एक लाख से अधिक नोड्स की आवश्यकता होती है। 154 बाइट्स * 1,000,000 नोड्स = 146.86 मेगाबाइट्स। यानी लगभग 400 बाइट्स प्रति शब्द। यदि आप utf8 में एन्कोडेड एक साधारण टेक्स्ट फ़ाइल में शब्द लिखते हैं, तो ये 380 हजार शब्द 16 मेगाबाइट में फिट हो सकते हैं।

योजनाओं

मेमोरी को अधिक तर्कसंगत रूप से उपयोग करने के लिए, मैं नोड्स की एक चर लंबाई पर स्विच करना चाहता हूं, फिर एक लिंक के रूप में मुझे नोड आईडी नहीं, बल्कि बाइट्स में इसका स्थान रिकॉर्ड करना होगा। वांछित नोड के लिंक का स्थान निम्नानुसार निर्धारित किया जाएगा। "Abv" शब्द के उदाहरण पर।

अक्षर "ए" वर्णमाला में पहला है, इसलिए, इसका नोड भी क्रमशः पहला है, ऑफसेट 0। 6 बाइट्स पढ़ें, 0 से शुरू।

$str = substr($dic, 0, 6); 

लाइन अनपैक करें:

 $mask = (ord($str[5]) << 40) + (ord($str[4]) << 32) + (ord($str[3]) << 24) + (ord($str[2]) << 16) + (ord($str[1]) << 8) + ord($str[0]); 

हम 2 बिट ("बी" अक्षर) का मुखौटा देखते हैं

 bit_get($mask, 2); 

बिट सेट है, अब हम नकाब में उठाए गए बिट्स की संख्या को 2 तक गिनते हैं। मान लीजिए कि हमारे नोड में "बिट" अक्षर भी उठाया गया है, इसलिए हमारा बिट अक्षर "बी" दूसरा बिट उठाया जाएगा। लिंक पढ़ने के लिए ऑफसेट गणना करें

 $offset = 6 + 3; 

6 बाइट्स मास्क + 3 बाइट्स, जिसमें पहला लिंक होता है, 9 बाइट्स निकलता है। हम स्ट्रिंग का वांछित टुकड़ा पढ़ते हैं।

 $str = substr($dic, $offset, 3); 

लिंक अनपैक करें:

 $ref = (ord($str[2]) << 16) + (ord($str[1]) << 8) + ord($str[0]); 

अगले नोड पर जाएं और फिर से सब कुछ दोहराएं। अंतिम पत्र में, हम मुखौटा में 47 बिट्स की उपस्थिति की जांच करते हैं, अगर यह सेट है, तो हमारे त्रि में एक खोज शब्द है।

मुझे उम्मीद है कि प्रति सेकंड कम से कम 50 हजार शब्दों की गति बनाए रखना संभव होगा।

धन्यवाद

मैं मंच के प्रतिभागियों को nulled.cc और php.ru को बिटवाइज़ फ़ंक्शंस की मदद के लिए धन्यवाद देना चाहता हूं।