द्वारा बंद स्ट्रिंग्स को पुनर्प्राप्त करने के लिए डेटा संरचना उदाहरण के लिए, अंग्रेजी शब्दों के सेट से शुरू होने पर, एक संरचना/एल्गोरिदम है जो "प्रकाश" और "तंग" जैसे तारों की एक तेज़ी से पुनर्प्राप्ति की अनुमति देता है प्रश्न के रूप में शब्द "सही"? यानी, मैं क्वेरी स्ट्रिंग में छोटी लेवेनशेटिन दूरी के साथ तारों को पुनर्प्राप्त करना चाहता हूं।लेवेनशेटिन दूरी
मुझे लगता है कि सबसे तेज़ तरीका समानता के कैश को पूर्व-निर्माण करना होगा जिसे आप इंडेक्स और ओ (1) समय में एक्सेस कर सकते हैं। यह चाल आपके कैश में जोड़ने के लिए सामान्य गलत वर्तनी ढूंढना होगा, जो बहुत बड़ी हो सकती है।
मुझे लगता है कि Google सांख्यिकीय क्वेरी खोज डेटा की विस्तृत श्रृंखला का उपयोग करके ऐसा कुछ करेगा।
चूंकि लेवेनशेटिन दूरी की गणना O(nm) लंबाई एन और एम के तारों के लिए है, तो सभी लेवेनशेटिन दूरी L(querystring, otherstring) की गणना करने का निष्पक्ष दृष्टिकोण बहुत महंगा है।
हालांकि, यदि आप लेवेनशेटिन एल्गोरिदम को कल्पना करते हैं, तो यह मूल रूप से संपादन दूरी के साथ एक एन * एम तालिका भरता है। लेकिन उन शब्दों के लिए जो समान अक्षर (उपसर्ग) से शुरू होते हैं, लेवेनशेटिन टेबल की पहली कुछ पंक्तियां समान होंगी। (निश्चित रूप से क्वेरी स्ट्रिंग को ठीक करना।)
यह trie (also called prefix tree) का उपयोग करने का सुझाव देता है: क्वेरी स्ट्रिंग पढ़ें, फिर लेवेनशेटिन पंक्तियों का एक तिहाई बनाएं। इसके बाद, आप क्वेरी स्ट्रिंग के करीब तार ढूंढने के लिए आसानी से इसे पार कर सकते हैं।
(यह मतलब है आप एक नया क्वेरी स्ट्रिंग के लिए एक नया trie का निर्माण करना है। मुझे नहीं लगता कि सभी जोड़े दूरी के लिए एक इसी तरह पेचीदा संरचना है है।)
मैंने सोचा मैंने हाल ही में एक अच्छा पायथन कार्यान्वयन के साथ इस बारे में एक लेख देखा। यदि मैं इसे पा सकता हूं तो एक लिंक जोड़ देगा। संपादित करें:Here it is, on Steve Hanov's blog.
BK-tree डेटा संरचना यहां उचित हो सकती है। यह फ़ॉर्म के प्रश्नों का कुशलतापूर्वक समर्थन करने के लिए डिज़ाइन किया गया है "संपादन शब्द के भीतर सभी शब्द क्या हैं या क्वेरी शब्द से कम?" इसकी प्रदर्शन गारंटी उचित रूप से अच्छी है, और इसे लागू करना बहुत मुश्किल नहीं है।
आशा है कि इससे मदद मिलती है!
अच्छा दृष्टिकोण अगर यह वास्तव में वर्तनी त्रुटियों के लिए है, तो यह बहुत उपयोगी नहीं है अगर यह लेवेनशेटिन दूरी के अधिक सैद्धांतिक अनुप्रयोगों के लिए है। – us2012
आपका क्या मतलब है? अगर मैं स्मृति उपयोग की कल्पना कर रहा हूं तो यह अव्यवहारिक होगा। – MaiaVictor
@ us2012 जो उद्देश्य है। – MaiaVictor