द्वारा बंद स्ट्रिंग्स को पुनर्प्राप्त करने के लिए डेटा संरचना उदाहरण के लिए, अंग्रेजी शब्दों के सेट से शुरू होने पर, एक संरचना/एल्गोरिदम है जो "प्रकाश" और "तंग" जैसे तारों की एक तेज़ी से पुनर्प्राप्ति की अनुमति देता है प्रश्न के रूप में शब्द "सही"? यानी, मैं क्वेरी स्ट्रिंग में छोटी लेवेनशेटिन दूरी के साथ तारों को पुनर्प्राप्त करना चाहता हूं।लेवेनशेटिन दूरी
उत्तर
मुझे लगता है कि सबसे तेज़ तरीका समानता के कैश को पूर्व-निर्माण करना होगा जिसे आप इंडेक्स और ओ (1) समय में एक्सेस कर सकते हैं। यह चाल आपके कैश में जोड़ने के लिए सामान्य गलत वर्तनी ढूंढना होगा, जो बहुत बड़ी हो सकती है।
मुझे लगता है कि Google सांख्यिकीय क्वेरी खोज डेटा की विस्तृत श्रृंखला का उपयोग करके ऐसा कुछ करेगा।
चूंकि लेवेनशेटिन दूरी की गणना O(nm)
लंबाई एन और एम के तारों के लिए है, तो सभी लेवेनशेटिन दूरी L(querystring, otherstring)
की गणना करने का निष्पक्ष दृष्टिकोण बहुत महंगा है।
हालांकि, यदि आप लेवेनशेटिन एल्गोरिदम को कल्पना करते हैं, तो यह मूल रूप से संपादन दूरी के साथ एक एन * एम तालिका भरता है। लेकिन उन शब्दों के लिए जो समान अक्षर (उपसर्ग) से शुरू होते हैं, लेवेनशेटिन टेबल की पहली कुछ पंक्तियां समान होंगी। (निश्चित रूप से क्वेरी स्ट्रिंग को ठीक करना।)
यह trie (also called prefix tree) का उपयोग करने का सुझाव देता है: क्वेरी स्ट्रिंग पढ़ें, फिर लेवेनशेटिन पंक्तियों का एक तिहाई बनाएं। इसके बाद, आप क्वेरी स्ट्रिंग के करीब तार ढूंढने के लिए आसानी से इसे पार कर सकते हैं।
(यह मतलब है आप एक नया क्वेरी स्ट्रिंग के लिए एक नया trie का निर्माण करना है। मुझे नहीं लगता कि सभी जोड़े दूरी के लिए एक इसी तरह पेचीदा संरचना है है।)
मैंने सोचा मैंने हाल ही में एक अच्छा पायथन कार्यान्वयन के साथ इस बारे में एक लेख देखा। यदि मैं इसे पा सकता हूं तो एक लिंक जोड़ देगा। संपादित करें:Here it is, on Steve Hanov's blog.
BK-tree डेटा संरचना यहां उचित हो सकती है। यह फ़ॉर्म के प्रश्नों का कुशलतापूर्वक समर्थन करने के लिए डिज़ाइन किया गया है "संपादन शब्द के भीतर सभी शब्द क्या हैं या क्वेरी शब्द से कम?" इसकी प्रदर्शन गारंटी उचित रूप से अच्छी है, और इसे लागू करना बहुत मुश्किल नहीं है।
आशा है कि इससे मदद मिलती है!
- 1. लेवेनशेटिन दूरी सममित?
- 2. लेवेनशेटिन दूरी मिलान
- 3. आर में फास्ट लेवेनशेटिन दूरी?
- 4. स्ट्रिंग समानता -> लेवेनशेटिन दूरी
- 5. नियमित अभिव्यक्ति में लेवेनशेटिन दूरी
- 6. मिलान खोज शब्द सटीकता संभवतः लेवेनशेटिन दूरी
- 7. mysql/fuzzy खोज के लिए लेवेनशेटिन दूरी का कार्यान्वयन?
- 8. एक वर्तनी परीक्षक में लेवेनशेटिन दूरी का उपयोग
- 9. एक सापेक्ष लेवेनशेटिन दूरी की गणना - समझ में आता है?
- 10. डेल्फी में लेवेनशेटिन दूरी को आप कैसे कार्यान्वित करते हैं?
- 11. PHP लेवेनशेटिन
- 12. डैमरौ-लेवेनशेटिन php
- 13. लेवेनशेटिन: MySQL + PHP
- 14. स्ट्रिंग लम्बाई के बजाय अधिकतम संरेखण लंबाई के लिए लेवेनशेटिन दूरी को सामान्य कैसे करें?
- 15. दूरी
- 16. स्ट्रिंग दूरी, प्रतिस्थापन केवल
- 17. विकृत अनुक्रमों के बीच दूरी मापने के लिए एल्गोरिदम
- 18. एक "असममित" जोड़ी दूरी दूरी मैट्रिक्स
- 19. गणना दूरी
- 20. UIPanGestureRecognizer दूरी
- 21. दूरी मैट्रिक्स
- 22. खोजने दूरी
- 23. यूक्लिडियन दूरी दो वैक्टरों (एकल पंक्ति मैट्रिक्स) के बीच दूरी
- 24. Scipy.cluster.hierarchy.fclusterdata + दूरी माप
- 25. कोण और दूरी
- 26. दूरी परिवर्तन .NET
- 27. दूरी (x, y)
- 28. दूरी से क्रमबद्ध करें
- 29. कम दूरी मापना
- 30. डब्ल्यूपीएफ ड्रैग दूरी थ्रेसहोल्ड
अच्छा दृष्टिकोण अगर यह वास्तव में वर्तनी त्रुटियों के लिए है, तो यह बहुत उपयोगी नहीं है अगर यह लेवेनशेटिन दूरी के अधिक सैद्धांतिक अनुप्रयोगों के लिए है। – us2012
आपका क्या मतलब है? अगर मैं स्मृति उपयोग की कल्पना कर रहा हूं तो यह अव्यवहारिक होगा। – MaiaVictor
@ us2012 जो उद्देश्य है। – MaiaVictor