सबसे पहले, लेवेनशेटिन दूरी को स्ट्रिंग ए को स्ट्रिंग बी में बदलने के लिए आवश्यक संपादन की न्यूनतम संख्या के रूप में परिभाषित किया जाता है, जहां एक संपादन एक एकल वर्ण को सम्मिलित करना, या हटाना, या किसी अन्य वर्ण के साथ वर्ण का प्रतिस्थापन है। तो यह दूरी की एक निश्चित परिभाषा के लिए "दो तारों के बीच का अंतर" बहुत अधिक है। =)
ऐसा लगता है कि आप एक दूरी फ़ंक्शन एफ (ए, बी) की तलाश में हैं जो स्ट्रिंग ए और बी और थ्रेसहोल्ड एन के बीच की दूरी देता है जहां एक दूसरे से एन से कम दूरी वाले तार टाइपो के उम्मीदवार हैं। लेवेनशेटिन दूरी के अलावा आप Needleman–Wunsch पर भी विचार कर सकते हैं। . यह मूल रूप से वही बात है लेकिन यह आपको एक फ़ंक्शन प्रदान करने देता है कि किसी दिए गए वर्ण को किसी अन्य वर्ण के कितना करीब है। आप उस एल्गोरिथम का उपयोग वज़न के एक सेट के साथ कर सकते हैं जो टाइपो खोजने का एक बहुत अच्छा काम करने के लिए QWERTY कीबोर्ड पर कुंजियों की स्थिति को दर्शाता है। हालांकि इसमें अंतरराष्ट्रीय कीबोर्ड के साथ समस्याएं होंगी।
यदि आपके पास k तार हैं और आप संभावित टाइपो खोजना चाहते हैं, तो आपको जितनी तुलना करने की आवश्यकता है वह O(k^2) है। इसके अलावा, प्रत्येक तुलना ओ (लेन (ए) * लेन (बी)) है। इसलिए यदि आपके पास एक लाख तार हैं, तो यदि आप भोलेपन से काम करते हैं तो आप खुद को परेशानी में पाएंगे। चीजों को गति देने के लिए यहां कुछ सुझाव दिए गए हैं:
- क्षमा करें यदि यह स्पष्ट है, लेकिन लेवेनशेटिन दूरी सममित है, इसलिए सुनिश्चित करें कि आप F(A, B) और F(B, A) की गणना नहीं कर रहे हैं।
- abs(len(A) - len(B)) स्ट्रिंग्स A और B के बीच की दूरी पर एक निचला बाउंड है। इसलिए आप उन स्ट्रिंग्स को चेक करना छोड़ सकते हैं जिनकी लंबाई बहुत अलग है।
एक समस्या जिसका आप सामना कर सकते हैं वह है "पहला सेंट।" "फर्स्ट स्ट्रीट" से बहुत अधिक दूरी है, भले ही आप शायद उन पर विचार करना चाहते हैं। इसे संभालने का सबसे आसान तरीका शायद तुलना करने से पहले स्ट्रिंग्स को एक विहित रूप में बदलना है। तो आप सभी स्ट्रिंग्स को लोअरकेस बना सकते हैं, एक ऐसे शब्दकोश का उपयोग करें जो "पहली" से "पहली" तक मैप करता है, आदि। वह शब्दकोश बहुत बड़ा हो सकता है, लेकिन मुझे इस मुद्दे से निपटने का बेहतर तरीका नहीं पता है।
चूंकि आपने इस प्रश्न को PHP के साथ टैग किया है, मुझे लगता है कि आप इसके लिए PHP का उपयोग करना चाहते हैं। PHP में एक अंतर्निहित levenshtein() फ़ंक्शन है लेकिन दोनों स्ट्रिंग्स में 255 वर्ण या उससे कम होना चाहिए। यदि वह काफी लंबा नहीं है तो आपको अपना खुद का बनाना होगा। वैकल्पिक रूप से, आप पायथन के difflib का उपयोग करके जांच करते हैं।
