पाठ और शब्दकोश में अस्पष्ट खोज

परिचय

फ़ज़ी सर्च एल्गोरिदम (जिसे समानता खोज या फ़ज़ी स्ट्रिंग खोज के रूप में भी जाना जाता है) वर्तनी जाँच प्रणालियों और Google या Yandex जैसे पूर्ण-खोज इंजनों का आधार है। उदाहरण के लिए, इस तरह के एल्गोरिदम का उपयोग उसी खोज इंजन में "शायद आपका मतलब है ..." जैसे कार्यों के लिए किया जाता है।

इस समीक्षा लेख में, मैं निम्नलिखित अवधारणाओं, विधियों और एल्गोरिदम पर विचार करूंगा:

• लेवेंसहिन दूरी
• दूरी दमरेउ-लेवेंसाइटिन
• वू और मम्बर से संशोधनों के साथ बिटैप एल्गोरिदम
• नमूनाकरण विस्तार एल्गोरिथ्म
• एन-ग्राम विधि
• सिग्नेचर हैशिंग
• बीके के पेड़

मैं एल्गोरिदम की गुणवत्ता और प्रदर्शन का तुलनात्मक परीक्षण भी करूंगा।

इसलिए ...

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

फ़ज़ी खोज समस्या को निम्नानुसार तैयार किया जा सकता है:
"किसी दिए गए शब्द के लिए, इस शब्द से मेल खाते आकार (या इस शब्द से शुरू होने वाले) के सभी शब्दों को ध्यान में रखते हुए किसी पाठ या शब्दकोश में खोजें।"

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

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



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

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

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

लेवेंसहिन दूरी

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



यदि आप एल्गोरिथ्म की प्रक्रिया को देखते हैं, तो यह नोटिस करना आसान है कि प्रत्येक चरण में केवल मैट्रिक्स की अंतिम दो पंक्तियों का उपयोग किया जाता है, इसलिए, मेमोरी की खपत को घटाकर O (न्यूनतम (m, n)) किया जा सकता है ।



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

उपसर्ग दूरी

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

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

दूरी दमरेउ-लेवेंसाइटिन

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



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

ऊपर चर्चा करने वालों के अलावा, कई अन्य दूरियां हैं जिन्हें कभी-कभी व्यवहार में लाया जाता है, जैसे कि यारो -विंकलर मीट्रिक , जिनमें से कई सिमेट्रिक्स और सेकंडस्ट्रिंग लाइब्रेरी में उपलब्ध हैं।

अनुक्रमण (ऑनलाइन) के बिना फजी खोज एल्गोरिदम

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

रैखिक खोज

दिए गए मीट्रिक का सरल अनुक्रमिक अनुप्रयोग (उदाहरण के लिए, लेवेंसहाइट मीट्रिक) इनपुट पाठ से शब्दों तक। प्रतिबंध के साथ मीट्रिक का उपयोग करते समय, यह विधि आपको इष्टतम गति प्राप्त करने की अनुमति देती है। लेकिन, एक ही समय में, बड़ा k , जितना अधिक ऑपरेटिंग समय बढ़ता है। स्पर्शोन्मुख समय अनुमान O (kn) है ।

बिटप (शिफ्ट-या याएजा-येट्स-गोननेट के रूप में भी जाना जाता है, और वू-मैनर से इसका संशोधन)

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

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

ऑपरेशन बिटशफ्ट



आवेषण

निष्कासन

प्रतिस्थापन

परिणामी मूल्य


जहाँ k त्रुटियों की संख्या है, j प्रतीक चिह्न है, s _x प्रतीक मुखौटा है (मुखौटा में, इकाई बिट्स अनुरोध में इस प्रतीक के पदों के अनुरूप पदों पर स्थित हैं)।
क्वेरी का मेल या बेमेल परिणामी वेक्टर आर के सबसे हाल के बिट द्वारा निर्धारित किया जाता है।

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

इस तथ्य के बावजूद कि इस एल्गोरिथ्म O (kn) का स्पर्शोन्मुखी रनिंग रैखिक विधि के साथ मेल खाता है, यह लंबे प्रश्नों के साथ बहुत तेज है और त्रुटियों की संख्या 2 से अधिक है।

परीक्षण

परीक्षण 3.2 मिलियन शब्दों के पाठ पर किया गया था, औसत शब्द की लंबाई 10 है।

सटीक खोज

खोज का समय: 3562 मि

Levenshtein मीट्रिक का उपयोग करके खोजें

K = 2 : 5728 एमएस में खोज समय
K = 5 : 8385 एमएस में खोज समय

वू-मैनबर संशोधनों के साथ बिटप एल्गोरिथ्म का उपयोग करके खोजें

K = 2 : 5499 ms पर खोज समय
K = 5 : 5928 एमएस में खोज समय

जाहिर है, बिटमैप एल्गोरिदम के विपरीत, मैट्रिक्स का उपयोग करते हुए एक सरल खोज, त्रुटियों की संख्या पर अत्यधिक निर्भर है k ।

फिर भी, यदि अपरिवर्तित ग्रंथों की बड़ी मात्रा में खोज करने की बात आती है, तो ऐसे पाठ को पूर्व-प्रसंस्करण द्वारा खोज समय को काफी कम किया जा सकता है, साथ ही अनुक्रमण भी।

अनुक्रमण (ऑफ़लाइन) के साथ फ़ज़ी खोज एल्गोरिदम

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

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

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

यह माना जाता है कि शब्दकोश की तरह सूचकांक पूरी तरह से स्मृति में लोड होता है।

शब्दकोश की प्रदर्शन विशेषताएं:

• स्रोत पाठ मोशकोव लाइब्रेरी ( lib.ru ), 680 मिलियन शब्दों से 8.2 गीगाबाइट सामग्री है;
• शब्दकोश का आकार 65 मेगाबाइट है;
• शब्दों की संख्या - 3.2 मिलियन;
• औसत शब्द की लंबाई 9.5 वर्ण है;
• मूल माध्य वर्ग शब्द लंबाई (कुछ एल्गोरिदम का मूल्यांकन करने में उपयोगी हो सकता है) 10.0 वर्ण है;
• वर्णमाला - कैपिटल अक्षर ए से जेड, ई के बिना (कुछ संचालन को सरल बनाने के लिए)। गैर-वर्णमाला वर्ण वाले शब्द शब्दकोश में शामिल नहीं हैं।

पाठ की मात्रा पर शब्दकोश के आकार की निर्भरता सख्ती से रैखिक नहीं है - एक निश्चित मात्रा तक, शब्दों का एक मूल फ्रेम बनता है, 15% से लेकर 500 हजार शब्द से 5 मिलियन तक 5% तक होता है, और फिर निर्भरता रैखिक में पहुंच जाती है, धीरे-धीरे कम हो रही है और 680 तक 0.5% तक पहुंच जाती है मिलियन शब्द। दुर्लभ शब्दों के कारण अधिकांश भाग के लिए विकास का संरक्षण सुनिश्चित किया जाता है।

नमूनाकरण विस्तार एल्गोरिथ्म

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

प्रारंभिक क्वेरी से बहुत सारे "गलत" शब्द बनाए गए हैं, जिनमें से प्रत्येक के लिए शब्दकोश में सटीक खोज की जाती है।



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


उदाहरण के लिए, के = 1 और लंबाई के शब्दों के साथ 7 (उदाहरण के लिए, "क्रोकोडाइल") रूसी वर्णमाला में, बहुत सारे गलत शब्द लगभग 450 आकार के होंगे, अर्थात, शब्दकोश में 450 प्रश्न आवश्यक होंगे, जो काफी स्वीकार्य है।
लेकिन यहां तक ​​कि k = 2 के साथ, इस तरह के सेट का आकार 115 हजार से अधिक विकल्प होंगे, जो हमारे मामले में एक छोटे से शब्दकोश, या 1/27 की पूरी खोज से मेल खाता है, और इसलिए, ऑपरेटिंग समय काफी बड़ा होगा। उसी समय, किसी को यह नहीं भूलना चाहिए कि इनमें से प्रत्येक शब्द के लिए शब्दकोश में सटीक मिलान के लिए खोज करना आवश्यक है।

विशेषताएं:

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

संभावित सुधार:

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

एन-ग्राम विधि

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



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

विशेषताएं:

एन-ग्राम एल्गोरिथ्म में त्रुटियों के साथ सभी संभव शब्द नहीं मिलते हैं। यदि हम, उदाहरण के लिए, VOTKA शब्द को लेते हैं, और इसे ट्रिगर्स में विघटित करते हैं: TOT → TOTTKTA, आप देख सकते हैं कि उन सभी में एक त्रुटि T है। इस प्रकार, "VODKA" शब्द नहीं मिलेगा, क्योंकि इसमें इनमें से कोई भी ट्रिगर्स नहीं है, और यह उनकी संबंधित सूचियों में नहीं आता है। इस प्रकार, शब्द की लंबाई और उसमें जितनी अधिक त्रुटियां होंगी, उतने अधिक अवसर होंगे कि वह अनुरोध के एन-ग्राम के अनुरूप सूचियों में नहीं गिरेगा, और परिणाम के रूप में मौजूद नहीं होगा।

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

संभावित सुधार:

आप एन-ग्राम के हैश टेबल को शब्दों की लंबाई और शब्द में एन-ग्राम की स्थिति से विभाजित कर सकते हैं (संशोधन 1)। जिस तरह खोजे गए शब्द और क्वेरी की लंबाई k से अधिक भिन्न नहीं हो सकती, उसी प्रकार शब्द में N-gram की स्थिति k से अधिक नहीं भिन्न हो सकती है। इस प्रकार, शब्द में इस एन-ग्राम की स्थिति के अनुरूप केवल तालिका की जांच करना आवश्यक होगा, साथ ही बाईं ओर के टेबल और दाईं ओर के टेबल, अर्थात्। केवल 2k + 1 पड़ोसी टेबल।



आप शब्द की लंबाई से तालिकाओं को तोड़कर थोड़ा और देखने के लिए आवश्यक सेट के आकार को कम कर सकते हैं और इसी तरह आसन्न 2k + 1 तालिकाओं (संशोधन 2) को देख सकते हैं।

सिग्नेचर हैशिंग

यह एल्गोरिथ्म एल बॉयत्सोव के लेख में वर्णित है "हस्ताक्षर से घृणा।" यह बिट बिट्स के रूप में "संरचना" शब्द के काफी स्पष्ट प्रतिनिधित्व पर आधारित है, जिसका उपयोग हैश तालिका में हैश (हस्ताक्षर) के रूप में किया जाता है।

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

हैश गणना प्रक्रिया - हैश के प्रत्येक बिट वर्णमाला के वर्णों के समूह के साथ जुड़ा हुआ है। हैश में स्थिति 1 पर बिट 1 का अर्थ है कि मूल शब्द में वर्णमाला के i-वें समूह से एक चरित्र है। किसी शब्द में अक्षरों के क्रम का कोई अर्थ नहीं है।



एक वर्ण को हटाने से या तो हैश मान नहीं बदलेगा (यदि शब्द में समान वर्ण समूह से अभी भी वर्ण हैं), या इस समूह के अनुरूप बिट 0. में बदल जाएगा, जब डाला जाएगा, उसी तरह, या तो एक बिट 1 में जाएगा या कोई बदलाव नहीं होगा। वर्णों को प्रतिस्थापित करते समय, सब कुछ थोड़ा अधिक जटिल होता है - हैश या तो बिल्कुल अपरिवर्तित रह सकता है, या यह 1 या 2 पदों में बदल सकता है। जब पुनर्व्यवस्थित किया जाता है, तो कोई भी बदलाव नहीं होता है, क्योंकि हैश के निर्माण में पात्रों का क्रम, जैसा कि पहले उल्लेख किया गया था, को ध्यान में नहीं रखा गया है। इस प्रकार, कश्मीर त्रुटियों को पूरी तरह से कवर करने के लिए, हैश में कम से कम 2k बिट्स को बदलना होगा।



ऑपरेटिंग समय, औसतन, k "अपूर्ण" (प्रविष्टि, विलोपन और ट्रांसपोज़ेशन के साथ-साथ प्रतिस्थापन का एक छोटा सा हिस्सा) त्रुटियों के साथ:

विशेषताएं:

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

बीके के पेड़

बुर्कहार्ड-केलर के पेड़ मीट्रिक पेड़ हैं, ऐसे पेड़ों के निर्माण के लिए एल्गोरिदम त्रिकोण असमानता के अनुरूप करने के लिए मीट्रिक की संपत्ति पर आधारित हैं:



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

सुधार:

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

परीक्षण

Intel Core Duo T2500 (2GHz / 667MHz FSB / 2MB), 2Gb RAM, OS - Ubuntu 10.10 Desktop i686, JRE - OpenJDK 6 अपडेट 20 के साथ एक लैपटॉप पर परीक्षण किया गया।



दमेराऊ-लेवेंसाइटिन दूरी और त्रुटियों की संख्या = 2 का उपयोग करके परीक्षण किया गया था। सूचकांक का आकार शब्दकोश (65 एमबी) के साथ इंगित किया गया है।

नमूना विस्तार

सूचकांक का आकार: 65 एमबी
खोज समय: 320 एमएस / 330 एमएस
परिणामों की पूर्णता: 100%

एन-ग्राम (मूल)

सूचकांक का आकार: 170 एमबी
सूचकांक निर्माण समय: 32 एस
खोज समय: 71 एमएस / 110 एमएस
परिणामों की पूर्णता: 65%

एन-ग्राम (संशोधन 1)

सूचकांक का आकार: १ :० एमबी
सूचकांक निर्माण समय: ३२ एस
खोज समय: ३ ९ एमएस / ४६ एमएस
परिणाम की पूर्णता: ६३%

एन-ग्राम (संशोधन 2)

सूचकांक का आकार: १ :० एमबी
सूचकांक निर्माण समय: ३२ एस
खोज समय: ३ 45 एमएस / ४५ एमएस
परिणाम की पूर्णता: ६२%

सिग्नेचर हैशिंग

सूचकांक का आकार: 85 एमबी
सूचकांक निर्माण समय: 0.6 s
खोज समय: 55 एमएस
परिणाम की पूर्णता: 56.5%

बीके के पेड़

सूचकांक का आकार: १५० एमबी
सूचकांक निर्माण समय: १२०
समय खोज समय: ५४० एमएस
परिणाम की पूर्णता: ६३%

कुल मिलाकर

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

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

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

आप http://code.google.com/p/fuzzy-search-tools पर मेरे जावा कार्यान्वयन पा सकते हैं:

• लेवेनशीन दूरी (कतरन और उपसर्ग विकल्प के साथ);
• दमरेउ-लेवेंसाइटिन दूरी (कतरन और उपसर्ग विकल्प के साथ);
• Bitap एल्गोरिथम (Shift-OR / Shift-AND और वू-मैनबर संशोधनों के साथ);
• नमूनाकरण विस्तार एल्गोरिथ्म;
• एन-ग्राम विधि (मूल और संशोधनों के साथ);
• हस्ताक्षर हैशिंग विधि;
• बीके के पेड़।

मैं कोड को समझना आसान बनाना चाहता था, और फिर भी व्यावहारिक उपयोग के लिए पर्याप्त प्रभावी था। जेवीएम से आखिरी रस निचोड़ना मेरा काम नहीं था। का आनंद लें।

यह ध्यान देने योग्य है कि इस विषय का अध्ययन करने की प्रक्रिया में मेरे अपने कुछ घटनाक्रम थे जो मुझे सूचकांक के आकार में मामूली वृद्धि और मैट्रिक्स की पसंद की स्वतंत्रता पर कुछ प्रतिबंध के कारण खोज समय को कम करने की अनुमति देते हैं। लेकिन यह पूरी तरह से अलग कहानी है।

संदर्भ:

1. जावा में लेख के लिए स्रोत कोड। http://code.google.com/p/fuzzy-search-tools
2. लेवेंसाइटिन दूरी। http://ru.wikipedia.org/wiki/_
3. दूरी दमरेउ-लेवेंसाइटिन। http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance
4. हालांकि, जर्मन में वू-मैनबर के संशोधनों के साथ शिफ्ट-या का एक अच्छा विवरण। http://de.wikipedia.org/wiki/Baeza-Yates-Gonnet-Algorithmus
5. एन-ग्राम विधि। http://www.cs.helsinki.fi/u/ukkonen/TCS92.pdf
6. . http://itman.narod.ru/articles/rtf/confart.zip
7. , . http://itman.narod.ru/
8. Shift-Or . http://johannburkard.de/software/stringsearch/
9. Fast Text Searching with Agrep (Wu & Manber). http://www.at.php.net/utils/admin-tools/agrep/agrep.ps.1
10. Damn Cool Algorithms — , BK-, - . http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
11. BK- Java. http://code.google.com/p/java-bk-tree/
12. -. http://yury.name/internet/09ia-seminar.ppt
13. सिमेट्रिक्स मेट्रिक्स लाइब्रेरी। http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html
14. सेकंडस्ट्रिंग मेट्रिक्स लाइब्रेरी। http://sourceforge.net/projects/secondstring/

रूसी संस्करण: फजी स्ट्रिंग खोज