खेल में त्वरित शब्द खोज के लिए एल्गोरिथ्म

किसी तरह, एक सामाजिक नेटवर्क में, मैं गैर-मानक नियमों (बड़े क्षेत्रों और नोड्स) के साथ बुलडोजर के एक खेल में आया था। चयन कार्यक्रम मुख्य रूप से शास्त्रीय नियमों के अनुसार और 5x5 क्षेत्रों पर काम करते हैं। इसलिए, मुझे अपना स्वयं का चयन लिखने में एक खेल का शौक मिला, पूरी तरह से गैर-मानक नियमों के अनुकूल। और न केवल एक चयन लिखें, बल्कि सबसे तेज़ शब्द खोज एल्गोरिदम को लागू करें।


गैर-मानक नियमों में से, एक दिलचस्प "नोड्यूल" मोड को प्रतिष्ठित किया जाता है, जिसमें आप एक अक्षर का उपयोग करके 2 बार तक एक शब्द की रचना कर सकते हैं (उदाहरण के लिए, ऊपर दिए गए स्क्रीनशॉट में आप SHALASH, अक्षर W और A शब्द को 2 बार उपयोग कर सकते हैं)। जैसा कि बाद में पता चला, एक ही स्थिति में, एल्गोरिथ्म नोड्यूल के बिना शास्त्रीय मोड की तुलना में लगभग 1.5 गुना लंबे नोड्यूल मोड में खोजता है (यह आश्चर्य की बात नहीं है, क्योंकि शब्दों को संकलित करने के लिए अधिक विकल्प हैं और पाए गए शब्द लंबे समय तक हैं)। लेख के अंत में, वर्णित एल्गोरिथ्म को नोड्यूल मोड में एक परीक्षण स्थिति में परीक्षण किया जाएगा।

शब्दकोश

एल्गोरिथम के जीवन को और जटिल करने के लिए, ऐसे कार्यक्रमों में सबसे बड़े शब्दकोशों में से एक का उपयोग किया जाएगा। इसके लगभग 110,000 शब्द हैं।
एल्गोरिथम को प्रोग्राम मेमोरी में संग्रहीत करने के तरीके से एक महत्वपूर्ण भूमिका निभाई जाती है। लोड करते समय, प्रत्येक शब्द एक पेड़ के रूप में संरचना को लिखा जाता है। इस पेड़ के प्रत्येक नोड का अर्थ है शब्द का एक विशिष्ट अक्षर और 32 से अधिक उपप्रकारों को संदर्भित करता है (वर्णमाला में अक्षरों की संख्या से)। प्रोग्राम में ट्री नोड इस तरह दिखता है:

typedef TREE *NEXT; //    struct TREE { NEXT *next; //       char *str; //      char *wrd; //  NULL,      }; 

स्ट्रिंग फ़ील्ड में सभी अक्षरों के साथ एक स्ट्रिंग होती है जो इस नोड से निकलती है, next[] सरणी का आकार इस स्ट्रिंग की लंबाई के बराबर है।
किसी दिए गए पत्र के लिए next[] नोड्स के सरणी के बीच एक विशिष्ट नोड खोजने के लिए str फ़ील्ड का उपयोग किया जाता है। ऐसा करने के लिए, ind() फ़ंक्शन शुरू किया गया है, strchr(): आधार पर strchr():

 int k=ind('',str); //  ()  ''   str 

यदि k<0 , तो यह अक्षर str में नहीं है, अन्यथा next[k] इस पत्र के अनुरूप नोड को इंगित करता है। उदाहरण के लिए, यदि स्ट्रिंग में "" स्ट्रिंग है, तो इस नोड से ठीक 5 उपप्रकार आते हैं, और next[2] अक्षर '' को संदर्भित करता है, क्योंकि str[2]== '' , अन्य अक्षरों के साथ भी ऐसा ही है।
उपरोक्त सभी को समझने के लिए, मैं एक विशेष रूप से तैयार किए गए शब्दकोश पर एक पेड़ का उदाहरण दूंगा, जिसमें शब्द शामिल हैं:

 , , , ,  

यदि str==NULL फ़ील्ड, तो यह नोड एक पत्ती है और इसमें डिक्शनरी शब्द wrd । '' अक्षर के अनुरूप नोड में "" शब्द होता है, और यह एक शीट नहीं है, क्योंकि इस शब्दकोश में - शुरू होने वाला एक और शब्द है। wrd फ़ील्ड में एक स्ट्रिंग होती है, जिसे यदि हम रूट से संबंधित नोड पर जाते हैं, तो प्राप्त किया जाता है, लेकिन यदि यह स्ट्रिंग डिक्शनरी शब्द नहीं है, तो wrd में NULL होता NULL ।
हम इस पेड़ को शब्दकोश कहते हैं, इसमें शब्दकोश के सभी शब्द हैं। शब्दकोश पेड़ के अलावा, एक और एक तैयार करना आवश्यक है, जिसमें प्रत्येक शब्द के लिए सभी संभव उल्टे शब्द उपसर्ग शामिल हैं (चलो इस पेड़ को औंधा कहते हैं)। उदाहरण के लिए, "" शब्द के "" निम्नलिखित पंक्तियां उल्टे पेड़ पर "", "", "", "", "" : "", "", "", "", "" । यहां तक ​​कि पांच शब्दों वाले एक परीक्षण शब्दकोश के लिए, ऐसा पेड़ बोझिल हो जाएगा, इसलिए मैं एक सरलीकृत संस्करण दूंगा:

शब्द इस पेड़ में शब्दावली शब्दों के उपसर्ग वापस सामने स्थित हैं। लाल घेरे में नोड शब्द शब्द के उल्टे उपसर्ग के अंतिम अक्षर से मेल खाता है, अर्थात्। शब्द के पहले अक्षर से मेल खाता है। एक शब्दकोश शब्द की शुरुआत को पढ़ने के लिए, आपको लाल नोड से रूट पर जाने की आवश्यकता है। उलटे पेड़ और शब्दकोश पेड़ के बीच एकमात्र अंतर यह है कि झंडे एक ध्वज ( NULL/ NULL ) के रूप में कार्य करता है। यानी यह एक उल्टे शब्द उपसर्ग के साथ एक स्ट्रिंग नहीं रखता है, लेकिन:

• 1) वैश्विक स्ट्रिंग का पता (स्ट्रिंग की सामग्री कोई फर्क नहीं पड़ता) अगर यह नोड डिक्शनरी शब्द के पहले अक्षर से मेल खाती है
• 2) अन्य सभी नोड्स के लिए NULL ।

यह अंतरिक्ष को बचाने के लिए किया जाता है। सभी लाल नोड्स के लिए wrd!=NULL , बाकी wrd==NULL । उदाहरण के लिए:

 root_inv->str == ””; root_inv->next[0]->str == ””; root_inv->next[5]->next[0]->wrd == NULL; //      root_inv->next[5]->next[0]->next[1]->wrd != NULL; //     

दोनों पेड़ स्मृति में 33M पर कब्जा कर लेते हैं, और सीधे शब्दकोश से वे i5 पर लगभग 5 सेकंड में निर्मित होते हैं, इसलिए पेड़ों की छवि को एक फ़ाइल में सहेजने और बाद में इसे लोड करने का निर्णय लिया गया। इसलिए डाउनलोड की गति केवल 300 मिली सेकंड थी।

खोज एल्गोरिथ्म

इस कदम के लिए बुलडोजर के नियमों के अनुसार, आपको एक खाली सेल का चयन करना होगा, और वहां कोई भी पत्र डालना होगा।

फिर आपको आपूर्ति किए गए पत्र का उपयोग करके एक शब्द रचना करने की आवश्यकता है। यह अक्षर शब्द में पहला अक्षर हो सकता है, और पहला अक्षर नहीं (हालांकि कप्तानी है, लेकिन यह महत्वपूर्ण है)। यदि नियमों में कहा गया है कि सेट लेटर बिल्कुल पहले होना चाहिए, तो हम केवल डिक्शनरी ट्री का उपयोग करते हैं, एक ही समय में पेड़ से नीचे जाने वाले सेट लेटर से पूरे क्षेत्र में घूमते हैं। लेकिन कब से प्रदत्त पत्र पहले वाला नहीं हो सकता है, शब्दकोश पेड़ का उपयोग नहीं किया जा सकता है, क्योंकि यह ज्ञात नहीं है कि खोज शुरू करने के लिए कौन सा नोड है। लेकिन हमारे पास अभी भी एक उल्टा पेड़ है।
विचार यह है: पिंजरे से पत्र सेट के साथ, हम मैदान के साथ आगे बढ़ते हैं, उल्टे पेड़ के नीचे जाते हैं। यदि हमें wrd!=NULL (लाल नोड) के साथ एक नोड wrd!=NULL , तो यह एक मान्य उल्टा शब्द उपसर्ग है। उपसर्ग शब्द होने से, आप शब्दकोश पेड़ में एक नोड पा सकते हैं जो आपके द्वारा सेट किए गए अक्षर से मेल खाती है, और फिर इस नोड से शुरू होने वाले शब्द का शेष टुकड़ा पहले से ही शब्दकोश पेड़ में "दान" कर दें।
एल्गोरिदम को उन कोशिकाओं में प्रवेश करने से रोकने के लिए जो पहले से ही किसी दिए गए शब्द के लिए पारित हो गए थे, प्रत्येक सेल में count का उपयोग करने के लिए एक काउंटर है। खोज शुरू करने से पहले, इस काउंटर को नंबर 2 (नोड्यूल मोड के लिए) या 1 (क्लासिक मोड के लिए) के साथ आरंभीकृत किया जाता है - यह एल्गोरिथम के दृष्टिकोण से मोड के बीच एकमात्र अंतर है।
अधिक विस्तृत एल्गोरिथ्म:

• 1) हम सभी खाली आसन्न कोशिकाओं के माध्यम से सॉर्ट करते हैं
• 2) प्रत्येक सेल के लिए, हम वर्णमाला के सभी अक्षरों के माध्यम से क्रमबद्ध करते हैं (32 अक्षर)
• 3) वर्तमान सेल में दर्ज करें (इसके निर्देशांक [x, y] ) वर्तमान अक्षर s । तो हम 32 * n अलग-अलग स्थिति प्राप्त करते हैं, जहां n प्रारंभिक स्थिति में आसन्न कोशिकाओं की संख्या है
• 4) प्रवेशित अक्षर को उल्टे उपसर्गों के लिए पहला अक्षर माना जाता है।
  इसलिए, root_inv->next[] बीच में हम वर्तमान पत्र के अनुरूप नोड t_inv पाते हैं, अर्थात्। t_inv - वर्तमान पत्र के साथ शुरू होने वाली सबट्री:
  

   int k = ind(s, root_inv->str); //s –   if(k<0) continue; //         TREE * t_inv = root_inv->next[k]; 

• 5) count[x, y] कम करें count[x, y] और खोज फ़ंक्शन को कॉल करें सबट्री (जिसके बारे में नीचे) t_inv और सेल [x, y]
• 6) चक्र मंत्र का अंत
• 7) आसन्न कोशिका चक्र का अंत

स्वाभाविक रूप से, चक्र के बाद, हम वर्तमान आसन्न सेल को जादू करते हैं।
खोज सबट्री सर्च फंक्शन प्लेइंग फील्ड, ट्री नोड ( tree ) और सेल कोऑर्डिनेट्स (i, j) स्वीकार करता है, जिसमें से पेड़ के नीचे जाकर फर्श के साथ चलना शुरू करना आवश्यक है:

• 1) अगर tree->wrd!=NULL , तो एक वैध विकल्प पाया जाता है
  
  • एक। यदि यह नोड एक डिक्शनरी ट्री से संबंधित है, तो यह विकल्प आमतौर पर एक डिक्शनरी शब्द है, पाए गए शब्दों की सरणी में tree->wrd जोड़ें।
  • ख। यदि नोड एक उल्टे पेड़ का है, तो यह विकल्प शब्द का उल्टा उपसर्ग है। डिक्शनरी ट्री में हम इस उपसर्ग के अनुरूप नोड t पाते हैं, और t और सेल [x, y] (ध्यान दें [x, y] के find फंक्शन फ़ंक्शन को कॉल करते find (ध्यान दें! इस फ़ंक्शन को पारित नहीं किया गया था, लेकिन सेल जो एल्गोरिथ्म चरण 3 में गया था):
    

     TREE *t=root; //   loopi(strlen(prefix)) //prefix     { int k=ind(prefix[i],t->str); t=t->next[k]; } find(t,x,y); 

• 2) मूल्य के tree->wrd जारी है
• 3) हम [i, j] से सटे सेल (क्षेत्र के केंद्र में कोने में 2 से 4 तक) को क्रमबद्ध करते हैं।
• 4) हम वर्तमान निकटवर्ती सेल [i1, j1] की सामग्री का विश्लेषण करते हैं।
  
  • एक। यदि यह खाली है, तो चरण (3) पर जाएं
  • ख। यदि इस सेल में अक्षर tree->str में नहीं tree->str , तो स्टेप पर जाएं (3)
  • सी। यदि count[i1, j1]==0 , तो चरण (3) पर जाएं
  • घ। अन्यथा, चरण (5) पर जाएं
• 5) tree->next[] के tnext tree->next[] हम tnext नोड को अक्षर [i1, j1] अनुरूप पाते हैं।
• 6) उपयोग काउंटर count[i1, j1] को कम करें और tnext और cell [i1, j1] लिए कॉल find
• 7) आसन्न अक्षरों द्वारा चक्र का अंत

उदाहरण के रूप में निम्न स्थिति का उपयोग करके केंद्रीय सेल के लिए एल्गोरिथ्म के संचालन पर विचार करें:

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

उल्टे पेड़ के बाकी अक्षरों के लिए वैध उपसर्ग मिलेंगे:
– , – , – , – , – । प्रत्येक उपसर्ग के लिए, हम शब्दकोश पेड़ में एक नोड पाते हैं (जैसा कि खंड 1. बी में वर्णित है) और इसके लिए find फ़ंक्शन को कॉल करें।
उपसर्ग “” root->next[0]->next[0]->next[0] नोड से मेल खाती है:

अगला आसन्न पत्र या हो सकता , लेकिन इस नोड के str क्षेत्र में “” , इसलिए हम तुरंत find फ़ंक्शन को समाप्त करते find , अर्थात। - और - शुरू होने वाले पेड़ में कोई शाखा नहीं होती है। “” उपसर्ग के लिए “” शब्दकोश पेड़ में कोई शाखाएं नहीं हैं जो -, -, -, - , -, -, -, - , -, -, -, - , -, -, -, - शुरू -, -, -, - , वही “” और “” उपसर्गों के लिए सच है।

उपसर्ग “” root->next[0]->next[0]->next[2] नोड से मेल खाती है।
क्योंकि फ़ील्ड wrd!=NULL , स्ट्रिंग wrd () में पाए गए शब्दों की सरणी में प्रवेश करें और आगे खोज जारी रखें। और लाइनों के लिए कोई शाखाएं नहीं हैं, हम उनके लिए find फ़ंक्शन को समाप्त करते find , लेकिन लाइन पेड़ में निहित है, इसे पाया शब्दों की एक सरणी में डाल दिया।

परिणाम

एल्गोरिथ्म का परीक्षण निम्नलिखित क्षेत्र में किया गया था (ज़ाहिर है, परीक्षण शब्दकोश पर नहीं, बल्कि 110,000 शब्दों के शब्दकोश में):

यह वास्तव में खेला जाने वाला खेल है।
यहां फ़ील्ड 99 , और यह आधा भरा हुआ है (शायद यह किसी भी एल्गोरिथ्म के लिए सबसे खराब स्थिति में से एक है, क्योंकि वहां बहुत सारी कोशिकाएं हैं जहां आप जा सकते हैं, और पत्रों की अच्छी आपसी व्यवस्था, जिसके कारण कई लंबे शब्दों की रचना हो सकती है)। नोड्यूल मोड में, एल्गोरिथ्म निम्नलिखित समय के लिए सभी शब्द पाता है:

• 1) मैक मिनी i7 - 7 मिलीसेकंड (मूल अनुप्रयोग नहीं, लेकिन iPhone एमुलेटर में)
• २) कम्प। i5 के साथ - 12 मिलीसेकंड
• 3) आईपैड 4 - 30 मिली सेकेंड
• 4) सैमसंग गैलेक्सी ऐस (तीन साल पहले लोहा) - 50 मिलीसेकंड (NDK का उपयोग करके)

अन्य पंक्ति वस्तुओं के लिए, खोज समय और भी कम है।

आवेदन

यह एल्गोरिथ्म iOS (ऐप स्टोर में उपलब्ध) और एंड्रॉइड के लिए एप्लिकेशन में उपयोग किया जाता है। सभी शब्दों की खोज के अलावा, दो और प्रकार की खोज कार्यान्वित की जाती है:

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

एक अन्य विशेषता: जो शब्द लंबाई में समान होते हैं, उन्हें जोड़े जाने वाले अक्षर की दुर्लभता द्वारा क्रमबद्ध किया जाता है (उदाहरण के लिए, अक्षर साथ जाने के लिए अक्षर तुलना में अधिक लाभप्रद है)।