रिवर्स लेवेनशेटिन दूरी

Question

लेवेनशेटिन दूरी में आप इन दो तारों को देखते हुए प्रश्न पूछते हैं, उनकी लेवेनशेटिन दूरी क्या है। आप स्ट्रिंग और लेवेनशेटिन दूरी लेने और उस लेवेनशेटिन दूरी के भीतर सभी तारों को उत्पन्न करने के बारे में कैसे जाएंगे। (यह एक चरित्र सेट में भी ले जाएगा)। तो अगर मैं एक स्ट्रिंग एक्स और दूरी डी में गुजरता हूं। तो यह मुझे उस संपादन दूरी के भीतर सभी तारों को दे देगा, जिसमें डी -1 और डी -2 शामिल हैं .... डी-एन; (एन < डी)।

अपेक्षित कार्यक्षमता:

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

कृपया ध्यान दें कि कार्यक्रम के रूप में अंतरिक्ष अक्षर समूह में शामिल किया गया है app le उत्पादन करने में सक्षम है।

Answer 1

एक डेटा संरचना है जिसे इसे Levenshtein automaton कहा जाता है। आप इसे तारों के सेट (जिसमें केवल एक सदस्य हो सकता है) और एक निश्चित दूरी के से बनाते हैं, और फिर आप इसे संग्रहीत तारों में से किसी भी के पर दूरी के साथ सभी तारों के लिए क्वेरी कर सकते हैं। एक पायथन कार्यान्वयन पर चर्चा की गई है here।

वैकल्पिक रूप से, आप इस तरह के तारों के लिए बैकट्रैकिंग के साथ गहराई से सीमित खोज कर सकते हैं।