एक अनुरोध का इतिहास

किसी नए काम में अपने पहले दिन की कल्पना करें। कार्यालय पूरी तरह से अपरिचित कुर्स्काया मेट्रो स्टेशन के क्षेत्र में स्थित है। दोपहर का भोजन निकट आ रहा है। आप खोज एप्लिकेशन खोलें, "कुर्स्क पर खाएं" लिखें और उन विकल्पों का चयन करें जहां आप भोजन कर सकते हैं।

"कुर्स्क पर खाएं" अनुरोध के पीछे क्या है और यह कैसे संसाधित किया जाता है ताकि आपको इसकी आवश्यकता हो? लेख में मैं आपको बताऊंगा कि कैसे 2GIS खोज टीम उपयोगकर्ताओं के लिए शहरों में जीवन को अधिक सुविधाजनक और आरामदायक बनाने के लिए हर संभव प्रयास करती है।

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

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

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

नीचे मैं हमारी खोज के जादू को कवर करने वाली गोपनीयता का पर्दाफाश करेगा। एक उदाहरण के रूप में, हम उल्लिखित अनुरोध "कुर्स्क पर खाएं" लेते हैं । इसके प्रसंस्करण के चरणों पर विचार करें और उनमें से प्रत्येक पर क्या होता है। तो चलिए!

चरण 1. पारस

इनपुट पैरामीटर: अनुरोध "कुर्स्क पर खाएं"

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

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

चरण 2. शब्दकोश खोज

इनपुट पैरामीटर: टोकन "खाओ" , "पर" , "कुर्स्क"


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

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

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

तो टोकन के लिए हम शब्द रूप पाते हैं:

• "खाने" के लिए 13 रूप: "खाओ", "खाओ", "पैसा", "तनख्वाह", ...
• "पर" के लिए 3 रूप: "ना", "नु", "पर"
• "कुर्स्क" : "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुराको", ...

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

इसलिए टोकन के लिए नियम बनाए जाएंगे:

• "खाओ" : "खाओ", "खाओ", "खाओ", "खाओ", "खाओ"
• "ऑन" : "ऑन", "ना", "न्यू"
• "कुर्स्क" : "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुर्स्क"

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

चरण 3. डेटा एंट्री ढूँढना

इनपुट: अनुरोध के प्रत्येक भाग के लिए शर्तों का एक सेट

• "खाओ" : "खाओ", "खाओ", "खाओ", "खाओ", "खाओ"
• "ऑन" : "ऑन", "ना", "न्यू"
• "कुर्स्क" : "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुर्स्क", "कुर्स्क"

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

अनुरोध के प्रत्येक भाग के लिए और इन भागों में से प्रत्येक के लिए, हम शब्दों में एन्कोड किए गए दस्तावेज़ों की तलाश कर रहे हैं। इसलिए, अनुरोध के कुछ हिस्सों के लिए, प्रविष्टियां सभी शर्तों में मिलेंगी:

• “बिना खाएं : 18 प्रविष्टियाँ
• पर : 4,304 प्रविष्टियाँ
• कुर्स्क : 79 प्रविष्टियाँ

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


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

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

चरण 4. खोज का दिल

प्रवेश: हिट सूची

• “बिना खाएं : 18 प्रविष्टियाँ
• पर : 4,304 प्रविष्टियाँ
• कुर्स्क : 79 प्रविष्टियाँ

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

इसलिए, निम्नानुसार इनपुट डेटा प्रदर्शित करना अधिक सही होगा:
प्रवेश: दस्तावेज़ नोड्स के कंटेनर

• document1: {हिट, ...}
• document2: {हिट्स, ...}
• document3: {हिट्स, ...}
• document4: {हिट्स, ...}
• ...

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

चरण 5. विश्लेषण

इनपुट: दस्तावेज़ नोड : {हिट, ...}


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

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

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

नतीजतन, हमारे पास सूचकांक से सिर्फ एक दस्तावेज नहीं है, लेकिन संरचनात्मक डेटा का एक सेट है, जो इस जानकारी के साथ संभावित परिणाम का प्रतिनिधित्व करता है कि यह कैसे पाया जा सकता है।

चरण 6. मूल्यांकन

इनपुट: दस्तावेज़ नोड : {हिट, ...}


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

इसके बाद एक-दूसरे के साथ जुड़े नोड्स के शीर्षकों का विश्लेषण शुरू होता है। वास्तव में, कई नोड्स एक नोड ग्राफ में संयुक्त होते हैं, जिनका हम मूल्यांकन करते हैं।

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

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

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

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

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

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

चरण 7. पोस्ट प्रोसेसिंग

इनपुट: नोड से निर्मित परिणाम


विश्लेषक परिणाम बनने से पहले सूचकांक से कई रिकॉर्डों को फ़िल्टर करता है। हालांकि, विश्लेषण के दौरान, कई संभावित परिणामों का मूल्यांकन किया जा सकता है और प्रसंस्करण के लिए भेजा जा सकता है। प्रासंगिकता के क्रम में उपयोगकर्ता को केवल सबसे उपयोगी दिखाने के लिए, हमें विश्लेषक द्वारा पाए गए सबसे खराब विकल्पों को काटने की आवश्यकता है।

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

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

निष्कर्ष

हमने कई कैफे और रेस्तरां के साथ प्रत्यर्पण प्राप्त किया और, खुश होकर, हम रात के खाने पर जाते हैं। एक स्प्लिट सेकंड में हमें सारे परिणाम मिले। और न ही हमें इंटरनेट कनेक्शन की आवश्यकता है।

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

आज मैंने अपने खोज इंजन के हुड को खोलने की कोशिश की और दिखाया कि कैसे हम उपयोगकर्ताओं को शहर में उनकी ज़रूरतों को पूरा करने में मदद करते हैं और इसे जल्दी और आसानी से करते हैं। मुझे उम्मीद है कि यह जानकारीपूर्ण था।