🔝 📷 🌩️ TextRadar फजी सर्च एल्गोरिदम। कलाकृतियों (भाग 2) 👉🏿 👩🏽‍💼 🥠

पिछले प्रकाशन में, TextRadar Fuzzy Search Algorithm। मुख्य दृष्टिकोण (भाग 1) को मुख्य दृष्टिकोण माना जाता है। व्यावहारिक समस्याओं को हल करते समय, उन स्थितियों की पहचान की गई जहां केवल मूल पद्धति का उपयोग खोज की आवश्यक गुणवत्ता प्रदान नहीं करता है। परिणामस्वरूप, ऐड-ऑन (एल्गोरिथ्म विकल्प) बनाए गए थे, जिस पर चर्चा की जाएगी।

खोज स्ट्रिंग के एक शब्द के टुकड़े एक डेटा स्ट्रिंग के कई शब्दों में स्थित हैं

खोज स्ट्रिंग ABCD और डेटा स्ट्रिंग ABCE DFG हो।

बुनियादी एल्गोरिथ्म का अनुप्रयोग निम्नलिखित परिणाम देगा:

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

खोज स्ट्रिंग शब्द का प्रारंभ टुकड़ा डेटा स्ट्रिंग शब्द के अंदर स्थित है

स्ट्रिंग XYZAB में स्ट्रिंग एबीसी खोजने के उदाहरण पर विचार करें।

मूल एल्गोरिथ्म निम्नलिखित का उत्पादन करेगा:

एक नियम के रूप में, इस तरह के परिणाम का कोई व्यावहारिक मूल्य नहीं है और इसे छोड़ दिया जाना चाहिए।

किसी डेटा पंक्ति में किसी शब्द की अपर्याप्त कवरेज, जिसमें अंश पाए जाते हैं

यदि हम ABXYZ शब्द के लिए ABCDEF लाइन में खोज करते हैं तो हमें यह

मिलता है:

यह परिणाम भी कोई मायने नहीं रखता है और इसे छोड़ दिया जाना चाहिए।

Overgroups

खोज स्ट्रिंग ABCXEF और डेटा स्ट्रिंग ABCEF ABCDEF को देखते हुए।

बुनियादी एल्गोरिथ्म के दृष्टिकोण से, डेटा स्ट्रिंग के दोनों शब्द बराबर हैं, लेकिन उनमें से पहली प्राथमिकता होगी (यदि, ceteris paribus, पहला शब्द जो चुना गया है) चुना गया है और फिर खोज परिणाम निम्नानुसार होगा:

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

लंबे समय तक शब्द

जब एक लंबे और छोटे शब्द वाले वाक्यांश की खोज करते हैं, तो एक लंबे शब्द के टुकड़े पाए जाते हैं, एक छोटे शब्द के टुकड़े को "अस्पष्ट" कर सकते हैं। यह प्रासंगिकता गुणांक की गणना में एक द्विघात फ़ंक्शन के उपयोग के कारण है।

इसके अलावा, खोज की गुणवत्ता के दृष्टिकोण से, एक लंबा शब्द हमेशा अधिक सार्थक नहीं होता है।

एक उदाहरण पर विचार करें। मान लें कि आपको दो पृष्ठों वाले पाठ में स्ट्रिंग ABCDEFG XYZ ढूंढना है:

1. ABCDEFG ...

QWE 2. ABCDEFO ... XYZ

समूह रचना गुणांक के अंश (हर के परिणाम पर गुणात्मक प्रभाव नहीं होता है, ऊपर दिए गए सूत्र को देखें) पहले पृष्ठ के लिए 49 है, दूसरे के लिए - 36 + 9 = 45. यही है, अगर हम लंबाई कारक परिणाम पर प्रभाव को छोड़ते हैं, तो पहले पृष्ठ पर खोज परिणाम। अधिक प्रासंगिकता होगी, जो अपेक्षाओं को पूरा नहीं करता है - कुछ मामलों में, पृष्ठ 2 पर खोज परिणाम अधिक मूल्यवान होगा।

समाधानों में से एक समूहों की अधिकतम लंबाई पर प्रतिबंध लागू करना हो सकता है । हमारे उदाहरण में, यदि अधिकतम समूह की लंबाई 6 तक सीमित है, उदाहरण के लिए, हमें पहले पृष्ठ के लिए 36 और दूसरे के लिए 45 मिलते हैं, जो हमें अपेक्षित परिणाम प्रदान करेगा - दूसरे पृष्ठ की प्रासंगिकता पहले की तुलना में अधिक होगी।

उनकी लंबाई के समग्र परिणाम में खोज वाक्यांश के शब्दों के महत्व की असंगति की समस्या को हल करने का एक और तरीका यह है कि इसमें शामिल किए गए शब्दों की प्रासंगिकता के औसत के रूप में , स्वतंत्र रूप से गणना की गई खोज वाक्यांश की प्रासंगिकता की गणना करें। लेकिन यहां विपरीत समस्या उत्पन्न होती है - छोटे शब्दों के महत्व को कम करने की आवश्यकता, जिसे एक समान तरीके से हल किया जा सकता है - समग्र प्रासंगिकता के गठन में शामिल शब्दों की लंबाई तक सीमा मूल्य निर्धारित करके, लेकिन पहले से ही न्यूनतम मूल्य तक।

वांछित अंशों की पुनरावृत्ति

कथन के अनुसार, कार्य टुकड़ों के सेट के लिए सबसे अधिक प्रासंगिक खोज स्ट्रिंग की खोज करना है, इसलिए पाठ में वांछित अंशों के बार-बार दोहराए जाने का तथ्य परिणाम को प्रभावित नहीं करता है - पहले उपयुक्त टुकड़े का उपयोग खोज परिणाम के रूप में किया जाएगा, बाकी प्रसंस्करण के दौरान छोड़ दिया जाएगा। स्ट्रिंग ABCD ABCE ABCF ABCG में स्ट्रिंग ABC को खोजने के एक उदाहरण पर विचार करें।

बुनियादी एल्गोरिथ्म का अनुप्रयोग निम्नलिखित परिणाम देगा:

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

डाटा प्रोसेसिंग की गति

ऑन-द-फ्लाई डेटा प्रोसेसिंग की कुछ गति आवश्यकताएं हैं - खोज को बहुत लंबा नहीं होना चाहिए।

संसाधित समूहों के न्यूनतम आकार को सीमित करना, खोज विकल्पों

को अक्षम करना खोज गति को बढ़ाने के लिए, आप संसाधित समूहों की न्यूनतम लंबाई को सीमित कर सकते हैं।

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

समानांतर डाटा प्रोसेसिंग

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

परिणाम

वर्णित दृष्टिकोणों के आवेदन ने हमें विभिन्न प्रकार के टाइपो - अतिरिक्त, लापता पात्रों, क्रमपरिवर्तन, आदि पर इसके परिणामों की निर्भरता को कम करने और, और अधिक महत्वपूर्ण बात, जहां ये टाइपो स्थित हैं - कोई फर्क नहीं पड़ता - खोज पट्टी में ही या पाठ में। जिसकी तलाश की जा रही है।

वर्णित दृष्टिकोणों को लागू करने के परिणाम वेबसाइट textradar.ru पर तैनात डेमो स्टैंड पर देखे जा सकते हैं । उपन्यास के पाठ में एक खोज के उदाहरण पर एल.एन. टॉल्स्टॉय के "युद्ध और शांति" एल्गोरिदम के मूल और उन्नत संस्करणों का उपयोग करके खोज परिणामों की तुलना कर सकते हैं।

उन्नत कार्यक्षमता के साथ डेमो प्रोजेक्ट डाउनलोड या देखें (C # ASP.NET MVC) यहां ।

TextRadar फजी सर्च एल्गोरिदम। कलाकृतियों (भाग 2)