🏄 🛢️ 🗯️ आपकी खोज वापस लौटी: फ़ज़ी सर्च कार्यान्वयन 🤦🏽 🤽🏾 ✍🏿

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

प्रारंभिक खोज अवस्था

ऑनलाइन स्टोर 1C-Bitrix: साइट प्रबंधन प्लेटफ़ॉर्म पर विकसित किया गया था। खोज को कार्यान्वित करने के लिए, हमने मानक बिट्रिक्स खोज मॉड्यूल और स्फिंक्ससर्च पूर्ण-पाठ इंजन का उपयोग किया। स्फिंक्ससर्च में, रियल टाइम (आरटी) इंडेक्स प्रकार का उपयोग किया गया था, जिसके लिए स्थैतिक डेटा स्रोत की आवश्यकता नहीं होती है, लेकिन वास्तविक समय में किसी भी समय आबाद किया जा सकता है। यह आपको खोज अनुक्रमणिका को लचीले ढंग से अपडेट करने की अनुमति देता है बिना इसे पूरी तरह से रीएन्डेक्स किए चूंकि आरटी इंडेक्स क्वेरी प्रोटोकॉल के रूप में केवल SphinxQL का उपयोग करता है, इसलिए इसके माध्यम से एकीकरण किया गया था। SphinxQL एक mysql जैसा क्वेरी प्रोटोकॉल है जो मानक mysql क्लाइंट के माध्यम से कनेक्ट करने की क्षमता को लागू करता है, जबकि कुछ सीमाओं और अपने स्वयं के गुणों के साथ sql सिंटैक्स प्रदान करता है। खोज मॉड्यूल प्रश्नों का चयन / डालने / बदलने / हटाने का उपयोग करता है।

बिट्रिक्स सिस्टम में माल, श्रेणियों और ब्रांडों के डेटा को अनुक्रमित करने की प्रक्रिया को अंजाम दिया गया। इन संस्थाओं की जानकारी स्फिंक्स को हस्तांतरित की गई थी, जिसने आरटी इंडेक्स को अपडेट किया। जब ऑनलाइन स्टोर में डेटा अपडेट किया जाता है, तो एक घटना शुरू हो जाती है जो Sphinx में डेटा को अपडेट करती है। ऑनलाइन स्टोर में इकाई पहचानकर्ता के माध्यम से डेटा की संगति की जाती है।

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

प्रौद्योगिकी चयन

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

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

डालने
निष्कासन
प्रतिस्थापन

दमेराउ-लेवन्सहाइट दूरी लेवेंसाइटिन दूरी का एक विस्तारित संस्करण है और एक और ऑपरेशन जोड़ता है: ट्रांसपोज़िशन, यानी दो आसन्न वर्णों का क्रमचय।

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

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

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

दमरेउ-लेवेनश्टाइन दूरी की गणना करने के बाद, सबसे उपयुक्त एक का चयन करने के लिए समानता की डिग्री के आधार पर परिणामों को क्रमबद्ध करना आवश्यक था। ऐसा करने के लिए, हमने ओलिवर एल्गोरिथम का उपयोग किया: दो रेखाओं की समानता की गणना। Php में, यह एल्गोरिथ्म समान_टेक्स्ट फ़ंक्शन द्वारा दर्शाया गया है। फ़ंक्शन के पहले दो पैरामीटर इनपुट लाइनों को स्वीकार करते हैं जिनकी तुलना करने की आवश्यकता है। स्ट्रिंग की तुलना का क्रम महत्वपूर्ण है, क्योंकि फ़ंक्शन उस क्रम के आधार पर अलग-अलग मान देता है जिसमें फ़ंक्शन को लाइनें दी जाती हैं। तीसरे पैरामीटर को चर पारित किया जाना चाहिए जिसमें तुलना का परिणाम रखा गया है। यह 0 से 100 तक की संख्या होगी, जिसका अर्थ दोनों रेखाओं के बीच समानता का प्रतिशत है। गणना के बाद, परिणाम समानता के अवरोही क्रम में क्रमबद्ध किए जाते हैं, फिर सर्वोत्तम मूल्यों वाले विकल्पों का चयन किया जाता है।

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

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

फजी सर्च एल्गोरिथ्म

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

क्वेरी को अलग-अलग शब्दों में तोड़ें;
कनवर्टर के माध्यम से प्रत्येक शब्द को पास करें (इसके बारे में आगे);
प्रत्येक शब्द के लिए, एक अलग लेआउट पर अपना रूप बनाएं;
प्रतिलेखन लिखें;
डिमरेउ-लेवेन्शेटिन दूरी के माध्यम से प्रत्येक प्रविष्टि की तुलना करते हुए, शब्दकोश तालिका में एक खोज क्वेरी बनाएं;
केवल दो या उससे कम दूरी के साथ रिकॉर्ड छोड़ दें;
ओलिवर एल्गोरिथ्म के माध्यम से, केवल 70% से अधिक की समानता प्रतिशत वाले शब्दों को छोड़ दें

योजनाबद्ध रूप से, यह एल्गोरिथ्म इस प्रकार है:

शब्द रूपांतरण और फ़िल्टरिंग कार्यक्षमता

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

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

बहुत बार, उपयोगकर्ता वॉल्यूम या मात्रा को इंगित करने के लिए नंबर दर्ज करते हैं। इस मामले में, इस तरह के अनुरोध को सही करना गलत होगा। उदाहरण के लिए, एक उपयोगकर्ता ने "पानी 1.1 लीटर" क्वेरी दर्ज की। यदि हम उसके अनुरोध को 1.5 या 1.0 से ठीक करते हैं, तो यह गलत होगा। ऐसे मामलों में, हमने एक नंबर के साथ शब्दों को छोड़ने का फैसला किया। वे, हमारे एल्गोरिथ्म को दरकिनार करते हुए, पूर्ण-पाठ स्फिंक्स खोज में स्थानांतरित हो जाते हैं।

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

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

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

शब्द 2 वर्णों से अधिक लंबा होना चाहिए
शब्द में केवल अक्षर, एक अवधि वर्ण और एक हाइफ़न (डैश) होना चाहिए
यदि डॉट शब्द के बीच में है, तो इसके बाद एक स्पेस जोड़ा जाता है
यदि यह एक संक्षिप्त नाम है, तो अंक काट दिए जाते हैं और अक्षरों को एक साथ चिपका दिया जाता है
यदि इसमें कोई संख्या है तो शब्द का अनुमान लगाने की कोशिश न करें
यदि शब्द में एक हाइफ़न (डैश) है, तो इसे कई में तोड़ दें, अलग से खोजें और अंत में गोंद करें

शब्दकोश संकलन

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

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

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

क्षेत्र का नाम	फ़ील्ड प्रकार
शब्द	तार
प्रतिलिपि	तार
मैन्युअल रूप से जोड़ा गया	bool
उपयोग न करें	bool

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

बिट्रिक्स इंटीग्रेशन

न्यूनतम आवश्यक कार्यक्षमता को लागू करने के लिए, तीन वर्ग बनाए गए:

DictionaryTable - एक शब्दकोश के साथ काम करने के लिए Bitrix ORM सिस्टम
शब्दकोश - शब्दकोश पीढ़ी वर्ग
खोज - खोज कार्यान्वयन वर्ग

बिट्रिक्स में एकीकरण के लिए, 2 घटकों में परिवर्तन करना आवश्यक था:

bitrix: search.page
bitrix.search.title

अनुरोध निष्पादित करने से पहले, त्रुटियों का पता लगाने और उचित विकल्पों का चयन करने के लिए प्रसंस्करण विधि को कहा जाता है:

एक शब्दकोष को संकलित करने के लिए, खोज मॉड्यूल द्वारा माल के साथ सूचना ब्लॉक के तत्वों को सूचीबद्ध करने के लिए एक घटना दर्ज की गई थी (खोज: इससे पहले)।

भविष्य की योजना

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

निष्कर्ष

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

हमारे कार्यान्वयन का कोड रिपॉजिटरी में देखा जा सकता है: github.com/qsoft-dev/damlev-bitrix

आपकी खोज वापस लौटी: फ़ज़ी सर्च कार्यान्वयन