TextRadar फजी खोज एल्गोरिथ्म - मूल दृष्टिकोण

TextRadar फजी खोज एल्गोरिथ्म - मूल दृष्टिकोण

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

समस्या का बयान

एक डेटा स्ट्रिंग और एक खोज स्ट्रिंग को मनमाने ढंग से वर्ण सेट के रूप में दिया जाता है जिसमें शब्दों के समूह होते हैं - रिक्त स्थान द्वारा अलग किए गए वर्णों के समूह।

वर्णों की संरचना और सापेक्ष स्थिति द्वारा खोज लाइन के निकटतम अंशों के सेट को डेटा लाइन में ढूंढना आवश्यक है।

खोज परिणाम की गुणवत्ता का आकलन करने के लिए, प्रासंगिकता गुणांक की गणना करें, जिसका मान 0 से 1 तक की सीमा में होना चाहिए, जहां 0 को डेटा स्ट्रिंग में खोज स्ट्रिंग के वर्णों की पूर्ण अनुपस्थिति के अनुरूप होना चाहिए, और 1 को डेटा स्ट्रिंग में मौजूद डेटा स्ट्रिंग की मौजूदगी में मौजूद नहीं होना चाहिए।

स्रोत लाइनों के चरित्र-दर-चरित्र विश्लेषण द्वारा खोज की जानी चाहिए, लाइनों में वर्णों और शब्दों की पारस्परिक व्यवस्था को ध्यान में रखते हुए, लेकिन भाषा के वाक्यविन्यास और आकृति विज्ञान को ध्यान में रखे बिना।

एल्गोरिथम विवरण

खोज कई चरणों में की जाती है।

संयोगों के एक मैट्रिक्स का निर्माण

मैच मैट्रिक्स (M) एक द्वि-आयामी मैट्रिक्स है, जिसके स्तंभों की संख्या डेटा स्ट्रिंग की लंबाई और खोज स्ट्रिंग की लंबाई के लिए पंक्तियों की संख्या से मेल खाती है। संयोग मैट्रिक्स के तत्व मानों को 0 या 1 के आधार पर लेते हैं, भले ही लाइनों के संबंधित वर्ण रिक्त स्थान के अपवाद के साथ मेल खाते हैं या नहीं (शब्द विभाजक)।
डेटा स्ट्रिंग "ABCD EF" और खोज स्ट्रिंग "ABC" के लिए मिलान मैट्रिक्स का रूप है:



मैच मैट्रिक्स एलिमेंट मी (i, j) = 1 यदि d (i) = s (j), जहां D डेटा स्ट्रिंग वर्णों की एक सरणी है, S खोज स्ट्रिंग वर्णों की एक सरणी है, तो मैं मैच मैट्रिक्स M का कॉलम नंबर (डेटा स्ट्रिंग का वर्ण संख्या) हूं ), j मैच मैट्रिक्स की पंक्ति संख्या (खोज स्ट्रिंग में वर्ण की संख्या) है। अन्य मामलों में, m (i, j) = 0. शब्द विभाजकों के मेल (हमारे मामले में, रिक्त स्थान) पर ध्यान नहीं दिया जाता है, वह है: m (i, j) = 0 यदि d (i) = s (j) = '' ।

मैच मैट्रिक्स विकर्ण

संयोग मैट्रिक्स एम के तत्व विकर्ण हैं। मैट्रिक्स के तत्व एक ही विकर्ण पर होते हैं यदि उनके सूचकांक i और j एक साथ +1 या 1 से भिन्न होते हैं।



विकर्ण डेटा स्ट्रिंग के साथ ऑफ़सेट के अनुक्रम में खोज स्ट्रिंग की स्थिति के अनुरूप हैं।



विकर्णों में से एक के तत्वों और ऊपर की आकृति में इसी बदलाव को नीले रंग में हाइलाइट किया गया है।

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



विकर्णों की कुल संख्या सूत्र द्वारा गणना की जाती है:



विकर्णों की लंबाई खोज स्ट्रिंग की लंबाई के बराबर होती है।

मैच समूह

संयोग मैट्रिक्स के विकर्णों में उत्तराधिकार में निम्नलिखित इकाइयाँ मिलान के समूह बनाती हैं। नीचे डेटा स्ट्रिंग “ABCD DEF JH” और खोज स्ट्रिंग “ABC DE J” के लिए मिलान समूह हैं - विभिन्न विकर्णों पर स्थित 4 समूह।

प्रोजेक्शन मैट्रिसेस

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



उपरोक्त आकृति में, मिलान मैट्रिक्स के दाईं ओर स्थित खोज स्ट्रिंग पर अनुमानों का मैट्रिक्स है - MPS, नीचे - MPD डेटा स्ट्रिंग पर अनुमानों का मैट्रिक्स। एमपीएस कॉलम की संख्या एमपीडी पंक्तियों की संख्या के बराबर और मैच मैट्रिक्स के विकर्ण की संख्या के बराबर है - हमारे उदाहरण में, 18 हैं।

समूहों के परिणाम सेट के लिए खोजें

समस्या को हल करने के लिए, ऐसे समूहों का एक समूह ढूंढना आवश्यक है जो कि खोज स्ट्रिंग को सबसे अधिक "कवर" करता है, कम से कम विखंडन के साथ (जितना संभव हो उतना बड़ा), प्रोजेक्शन मैट्रिसेस में पारस्परिक चौराहों के बिना, और डेटा स्ट्रिंग पर मानचित्रण "मूल" - खोज स्ट्रिंग के सबसे करीब होगा। ।

प्रक्षेपण मैट्रिक्स में समूहों का अंतर

हमारे उदाहरण में, MPS मैट्रिक्स में इंटरसेक्टिंग समूह हैं - नीचे दिए गए आंकड़े में वे लाल रंग में हाइलाइट किए गए हैं। इसके अलावा, एमपीडी मैट्रिक्स में, ये वही समूह प्रतिच्छेद नहीं करते हैं, जिस आकृति में वे हरे रंग में हाइलाइट किए जाते हैं।



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

परिणाम सेट की खोज सभी समूहों की तालिका के "अनंत" चक्र (चक्र की पुनरावृत्तियों की संख्या समूहों की संख्या से अधिक नहीं) से होकर की जा सकती है , जिसमें मिलान के मैट्रिक्स के समूह शुरू में रखे जाते हैं, जिनमें से प्रत्येक पुनरावृत्ति पर कार्य किया जाएगा:

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

हमारे उदाहरण के लिए समूहों का इष्टतम सेट नीचे दिए गए आंकड़े में प्रस्तुत किया गया है - सेट समूह नारंगी में हाइलाइट किए गए हैं।



चौराहे के प्रसंस्करण के दौरान हटाए गए समूह (दूसरे पुनरावृत्ति के सबसे अच्छे समूह के साथ एमपीएस मैट्रिक्स में प्रतिच्छेद) को लाल रंग में हाइलाइट किया गया है।

डेटा पंक्ति में खोज परिणाम इस तरह दिखाई देगा:

प्रासंगिकता गुणांक की गणना

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



जहाँ समूह रचना गुणांक की गणना खोज समूह के शब्दों की वर्ग लंबाई के योग में पाए गए समूहों की वर्ग लंबाई के योग के अनुपात के रूप में की जाती है:



लंबाई कारक डेटा स्ट्रिंग पर पाया समूहों की कुल लंबाई के लिए खोज स्ट्रिंग की लंबाई का अनुपात है। यदि इस तरह से प्राप्त मूल्य 1 से अधिक है, तो इसका व्युत्क्रम मान लिया जाता है:



हमारे उदाहरण के लिए:

कम्प्यूटिंग का अनुमानित दायरा

सबसे अधिक संसाधन गहन संचालन हैं:

• मैच मैट्रिक्स एम का निर्धारण - मैट्रिक्स तत्वों की संख्या को डेटा स्ट्रिंग की लंबाई से खोज स्ट्रिंग की लंबाई के उत्पाद के रूप में परिभाषित किया गया है: एलएपी * एलयू;
• डेटा और खोज स्ट्रिंग्स पर प्रोजेक्शन मैट्रिसेस की परिभाषा - मैट्रिक्स तत्वों की संख्या एमपीएस के लिए होगी: (एलएपी + एलयूजी - 1) * एलपीई, एमपीडी के लिए: (एलओपी + एलआईजी - १) * लेग;
• सभी समूहों की तालिका का गठन - समूहों की संख्या मूल्य LUP * L / 2 से अधिक नहीं होगी;
• समूह के परिणामी समूह के लिए खोज - चक्र की पुनरावृत्तियों की संख्या समूहों की प्रारंभिक संख्या से अधिक नहीं है, अर्थात, एलएपी * एलयूजी / 2।

इस प्रकार, डेटा स्ट्रिंग की लंबाई से गणना की कुल राशि खोज स्ट्रिंग की लंबाई के उत्पाद का एक गुणक होगी:



स्रोत डेटा के आकार के सापेक्ष गणना की मात्रा की रैखिकता एल्गोरिथम के व्यावहारिक अनुप्रयोग के पक्ष में एक महत्वपूर्ण तर्क है।

nonlinearity

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

शेष राशि ज्ञात कीजिए

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

Textradar.ru वेबसाइट पर एक डेमो स्टैंड तैनात किया गया है जहां आप एल्गोरिथ्म के संचालन का परीक्षण कर सकते हैं।

एनालॉग्स के साथ तुलना: TextRadar फजी सर्च एल्गोरिदम की तुलना एनालॉग्स के साथ: Lucene, Sphinx, Yandex, 1C