नियमित अभिव्यक्ति में लेवेनशेटिन दूरी

Question

क्या नियमित अभिव्यक्ति क्वेरी में लेवेनशेटिन दूरी को शामिल करने की संभावना है?

क्रमपरिवर्तन के बीच संघ बनाने के अलावा। एलडी के साथ "हैलो" खोजना पसंद है। 1

.ello | h.llo | he.lo | hel.o | hell. 

यह बड़ी संख्या में एलडी के लिए बहुत बेवकूफ और उपयोग नहीं है।

Answer 1

क्या संभावित अभिव्यक्ति क्वेरी में लेवेनशेटिन दूरी को शामिल करने की संभावना है?

नहीं, एक सौहार्दपूर्ण तरीके से नहीं। कार्यान्वित करना - या मौजूदा का उपयोग करना - लेवेनशेटिन दूरी एल्गोरिदम जाने का तरीका है।

Answer 2

आप रेगेक्स प्रोग्रामेटिक रूप से उत्पन्न कर सकते हैं। मुझे लगता है कि छोड़ देंगे पाठक के लिए एक व्यायाम के रूप है, लेकिन इस काल्पनिक फ़ंक्शन के परिणाम के लिए ("शब्द" के इनपुट दिया) आप इस स्ट्रिंग की तरह कुछ हैं:

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$" 

अंग्रेजी में, पहले तुम जैसा बनाने का प्रयास शब्द पर, फिर प्रत्येक संभावित एकल पारदर्शिता पर, फिर प्रत्येक संभावित एकल सम्मिलन पर, फिर प्रत्येक संभावित एकल चूक या प्रतिस्थापन पर (एक साथ किया जा सकता है)।

उस स्ट्रिंग की लंबाई, लंबाई एन के शब्द को देखते हुए, एन के साथ रैखिक (और विशेष रूप से घातीय नहीं) है।

जो उचित है, मुझे लगता है।

आप इसे अपने रेगेक्स जेनरेटर (जैसे रूबी में यह Regexp.new (str)) और बाम को पास करते हैं, आपको किसी दिए गए शब्द से 1 की डैमरौ-लेवेनशेटिन दूरी के साथ किसी भी शब्द के लिए एक मैचर मिला है।

(2 के Damerau-Levenshtein दूरी में कहीं अधिक जटिल हैं।)

(> गैर backtracing निर्माण जो व्यक्ति के आदेश का मतलब है की

नोट उपयोग |?। 'कि उत्पादन मामले में घ भाव

मैं एक तरह से करने के लिए "कॉम्पैक्ट" है कि अभिव्यक्ति के बारे में सोच सकता है नहीं

संपादित करें:। मैं यह काम करने के लिए, कम से कम अमृत में मिला https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

मैं जरूरी इस यद्यपि (शैक्षिक के अलावा सिफारिश नहीं होता! पु rposes) क्योंकि यह केवल आपको 1 की दूरी पर ले जाएगा; एक कानूनी डीएल लाइब्रेरी आपको दूरी की गणना करने देगी> 1. यद्यपि यह रेगेक्स है, हालांकि यह संभवतः एक बार निर्माण के बाद बहुत तेज काम करेगा (ध्यान दें कि आपको "संकलित" रेगेक्स को कहीं सेव करना चाहिए क्योंकि इस कोड में वर्तमान में प्रत्येक तुलना में इसे पुनर्निर्मित किया गया है!)