चालाक उपसर्ग ट्री सी कार्यान्वयन

परिचय

उपसर्ग वृक्ष के निम्न-स्तरीय कार्यान्वयन में मेरे प्रयास के बारे में लेख के प्रकाशन के चार महीने बीत चुके हैं। मेरे सभी प्रयासों के बावजूद, जिस छत पर उपसर्ग वृक्ष का मेरा पिछला कार्यान्वयन सक्षम था, वह प्रति सेकंड ~ 80 हजार शब्द था। मैंने तब बहुत समय और ऊर्जा खर्च की, लेकिन परिणाम केवल कंप्यूटर विज्ञान में प्रयोगशाला के काम के रूप में उपयुक्त होगा।

कई लोगों ने मुझे बताया: “एक साइकिल का आविष्कार न करें जिसे हमने पहले ही आविष्कार किया है! टर्नकी समाधान का उपयोग करें। ” कठिनाई यह है कि मैं ऐसी चीज का उपयोग नहीं कर सकता था जिसे मैं कम से कम सामान्य शब्दों में नहीं समझता।

मुझे लगता है कि मैंने उपसर्ग के पेड़ को समझा, और यह वही है जिसे मैंने हासिल किया।

कार्य सिद्धांत

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

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

इस समस्या को हल करने के लिए, उपसर्ग वृक्षों की कई किस्में दिखाई दी हैं, जिनमें शामिल हैं: HAT-trie, double-array trie, tripple-array trie। यह वास्तव में तथ्य था कि मैं उनके काम के सिद्धांत को अच्छी तरह से समझ नहीं पाया था, जिसने मुझे एक पुस्तकालय कार्ड फ़ाइल के रूप में एक पेड़ पर धकेल दिया।

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

मैं सी में एक ही PHP योजना को लागू करने में कामयाब रहा।

1. स्थापित तालिका के अनुसार शब्द का प्रत्येक अक्षर 2 से 95 तक की संख्या के साथ एन्कोडेड है। उदाहरण के लिए, शब्द "abv" तीन संख्याओं के साथ एन्कोडेड है: 11, 12, 13. अधिकतम प्रदर्शन के लिए, संख्या 1 का एक द्वि-आयामी सरणी 1 बाइट uint8_t abc[256][256] = {}; किसी प्रोग्राम को कन्वर्ट करने के लिए, यह 1 बाइट द्वारा एक लाइन पढ़ता है, यह हमारे एरे में प्रत्येक बाइट का मान लेने की कोशिश करता है। उदाहरण के लिए, अंक कोड 1 = 49 है, इसलिए हम abc[49][0]; । यदि '\ 0' के अलावा कोई मूल्य निहित है, तो यह हमारे पत्र का कोड है, इसे याद रखें और अगले बाइट पर जाएं। हमारे मामले में, शब्द "abv" में 6 बाइट्स का एक क्रम होता है, प्रति अक्षर दो बाइट्स: 208, 176, 208, 177, 208, 178. चूंकि utf-8 एन्कोडिंग को डिज़ाइन किया गया है ताकि सिंगल-बाइट वर्णों के पहले बाइट्स मल्टी-बाइट के पहले बाइट्स के साथ कभी मेल नहीं खाते। में, हमारे abc[208][0] = 0; ।

हालाँकि, बाइट जोड़े के लिए कुछ मैच हैं:

 /*  [11] */ abc[208][176] = 11; /*  [12] */ abc[208][177] = 12; /*  [13] */ abc[208][178] = 13; 

2. अब हमें अपने पेड़ के बक्सों में 11, 12 और 13 नंबर लिखना होगा। पेड़ में मेमोरी के 2 अलग-अलग गैर-विस्फोटक ब्लॉक होते हैं, पहला नोड्स का एक ब्लॉक होता है, दूसरा लिंक का एक ब्लॉक होता है, साथ ही लिंक वाले ब्लॉक के कब्जे वाले नोड्स और कब्जे वाली कोशिकाओं के दो काउंटर होते हैं। प्रत्येक ट्री नोड में लिंक ब्‍लॉक की आईडी को स्‍टोर करने के लिए 16 बाइट्स, 12 बिटमेस और 12 बाइट्स होते हैं। मास्क आपको 2 से 96 बिट्स की संख्या स्टोर करने की अनुमति देता है। इस नोड पर शब्द के अंत को फ़्लैग करने के लिए मास्क का पहला बिट प्रयोग किया जाता है। प्रत्येक नोड लिंक ब्लॉक से आईडी के अनुरूप हो सकता है यदि कम से कम 1 पत्र इस नोड में लिखा गया है, या नहीं, तो पत्र पेड़ों के संदर्भ में एक "पत्ती" है, अर्थात, एक शब्द बस उस पर समाप्त होता है। एक पुस्तकालय, एक खाली दराज में व्यक्त किया।

3. पहले (रूट) नोड का मुखौटा लें। trie-> नोड्स [0]। mask; हम इस मुखौटा में उठाए गए बिट्स की गणना करते हैं, दूसरे से शुरू होता है (शब्द अंत ध्वज के लिए पहला)। यदि मुखौटा में कोई बिट नहीं उठाया जाता है, अर्थात्। चूंकि नोड खाली है, तो हमें अपने नंबर 11 को संग्रहीत करने के लिए आकार 1 के लिंक ब्लॉक की आवश्यकता है, ब्लॉक के लिंक संदर्भ काउंटर से नंबर लें और पुराने मूल्य को एक से बढ़ाएं (क्योंकि हमें आकार 1 की आवश्यकता है)। हम नोड काउंटर से संख्या लेते हैं और पुराने मान को भी 1 से बढ़ाते हैं। हम अपने रूट नोड में लिंक ब्लॉक की आईडी लिखते हैं, जो लिंक ब्लॉक के काउंटर से प्राप्त संख्या है। और लिंक ब्लॉक की इस आईडी में, नए नोड की आईडी लिखें, यानी नोड काउंटर से प्राप्त संख्या। अब, रूट नोड (आईडी 0) के अलावा, हमारे पास "ए" (आईडी 1) अक्षर का नोड है। पत्र "बी" के अनुरूप संख्या 12 लिखने के लिए, हम ऐसा ही करते हैं, लेकिन अक्षर "ए" के नोड के साथ।

4. अंतिम पत्र "c" पर हमें लिंक ब्लॉक में जगह की आवश्यकता नहीं है, क्योंकि हमारे पास शाखा या नोड - शीट पर अंतिम नोड होगा। इस तरह के नोड में उठाए गए मुखौटे में केवल 1 बिट है।

5. एक पेड़ के काम का सबसे कठिन हिस्सा तब होता है जब इसे एक नोड को लिखा जाता है जिसमें कुछ पत्र पहले ही लिखे जा चुके होते हैं। इस मामले में, ऑपरेशन योजना इस प्रकार है:

मान लीजिए कि हम अपने पेड़ में "bvg" (12, 13, 14) शब्द जोड़ना चाहते हैं, जिसमें "abv" (11, 12, 13) शब्द पहले से ही लिखा हुआ है। हम रूट नोड के मास्क में बिट्स को हमारे लिए रुचि के पत्र के बिट तक गिनते हैं। हमारे पास कोड 12 के साथ "b" अक्षर है, जिसका अर्थ है कि इस पत्र का बिट 12 है, मुखौटा में 1 से 12 बिट बिट 11 से पत्र "a" पहले ही उठाया जा चुका है। इसलिए हमारे पास रूट नोड के लिए लिंक ब्लॉक का वर्तमान आकार है। हम दूसरे पत्र लिखते हैं, इसलिए अब हमें आकार के लिंक ब्लॉक की आवश्यकता है। यहां से मुक्त ब्लॉक की रजिस्ट्री खेल में आती है, जिसमें लिंक ब्लॉक में आईडी और अनुभागों का आकार नोड्स द्वारा उपयोग नहीं किया जाता है। पेड़। आकार 1 के रूट नोड के लिए लिंक ब्लॉक की हमारी पुरानी आईडी सिर्फ आकार 1 के मुक्त वर्गों की रजिस्ट्री में मिलती है, क्योंकि हमारे रूट नोड को बड़े आकार की आवश्यकता होती है। हमारी रजिस्ट्री में आकार 2 का उपयुक्त खंड नहीं है और हम लिंक ब्लॉक के काउंटर से फिर से वैल्यू लेते हैं, लिंक ब्लॉक की नई आईडी के रूप में। काउंटर को बढ़ाकर 2. लिंक ब्लॉक के नए पते पर उसी क्रम में जिसमें बिट्स नोड मास्क में स्थित हैं, हम आईडी वैल्यू लिखते हैं। पहले शब्द के अक्षर "a" के लिए लिंक के पुराने ब्लॉक से नोड और दूसरे शब्द के अक्षर "b" के सिर्फ बनाए गए नोड के मूल्य।

काम की गति

ड्रम रोल लगता है ... अंतिम परिणाम याद है? लगभग 80 हजार शब्द प्रति सेकंड। पेड़ को सभी रूसी शब्दों के शब्दकोश से बनाया गया था OpenCorpora 3 039 982 शब्द। और यहाँ अब क्या हुआ:

 yatrie creation time: 4.588216s (666k wps) yatrie search time 1 mln. rounds: 0.565618s (1.76m wps) 

UPDATE 11/01/2018:
संस्करण 0.0.2 में, मैक्रो फ़ंक्शंस के साथ पूर्ण कार्यों को बदलकर गति को लगभग 2 गुना बढ़ाना संभव था, साथ ही नोड मास्क की संरचना को uint32_t मास्क [3] में बदलना, पहले यह uint8-t मास्क [12] था।
इसके अलावा मैक्रो LIKELY () UNLIKELY () को उन परिणामों में अपेक्षित परिणामों का अनुमान लगाने के लिए जोड़ा गया है, यदि संभव हो तो ब्लॉक करें।
अद्यतन 11/05/2018:
थोड़ा और मुड़ गया। मैं संकलन -O3 और -Ofast होने पर भी इसे ठीक काम करने में कामयाब रहा। पेड़ में खोज की गति ~ 0.2 μs या 0.2c प्रति 1 मिलियन पुनरावृत्ति है। जाहिरा तौर पर यह गति मास्क के एक अलग प्रारूप में संक्रमण के कारण प्राप्त हुई थी। पहले, 8 बिट्स के 12 बाइट्स थे, और अब इंट इंट 32 में बिट्स की गिनती के लिए 3 इंट 32 और एक बहुत तेज फ़ंक्शन है।

यह कितना कॉम्पैक्ट है?

निर्दिष्ट OpenCorpora शब्दकोश ~ 84MB लेता है, जो लिबडाट्री से बहुत बदतर नहीं है, जो ~ 80MB देता है।

→ सोर्स कोड

आपका स्वागत है!