फ़ज़ी मिलान संख्या

Question

मैं स्ट्रिंग तुलना के लिए डबल मेटाफोन और कैवरफ़ोन 2 के साथ काम कर रहा हूं और वे नाम, पते इत्यादि जैसी चीजों पर अच्छा काम करते हैं (Caverphone2 मेरे लिए सबसे अच्छा काम कर रहा है)। हालांकि, जब आप संख्यात्मक मान प्राप्त करते हैं, जैसे फोन नंबर, आईपी पते, क्रेडिट कार्ड नंबर इत्यादि।

तो मैंने Luhn और Verhoeff एल्गोरिदम पर देखा है और वे अनिवार्य रूप से वर्णन करते हैं मैं चाहता हूँ, लेकिन काफी नहीं। वे सत्यापन पर अच्छा लगते हैं, लेकिन अस्पष्ट मिलान के लिए नहीं दिखते हैं। क्या कोई ऐसी चीज है जो लुहान और वेरहॉफ की तरह व्यवहार करती है, जो एन्कोडिंग और तुलनात्मक उद्देश्यों के लिए अस्पष्ट स्ट्रिंग एल्गोरिदम के समान एकल अंकों की त्रुटियों और पारदर्शी त्रुटियों को पहचान सकती है?

मैं एक संख्या एन्कोड करना चाहता हूं, फिर बारीकी से समान मिलान खोजने के लिए इसे 100,000 अन्य नंबरों की तुलना करें। तो 7041234 की तरह कुछ 7041324 के खिलाफ संभावित ट्रांसक्रिप्शन त्रुटि के रूप में मेल खाता है, लेकिन 4213704 की तरह कुछ नहीं होगा।

Answer 1

Levenshteinandfriends विशिष्ट तारों या संख्याओं के बीच की दूरी को खोजने के लिए अच्छा हो सकता है। हालांकि यदि आप एक वर्तनी सुधारक बनाना चाहते हैं तो आप प्रत्येक क्वेरी पर अपने पूरे शब्द डेटाबेस से भागना नहीं चाहते हैं।

पीटर नॉर्विग ने Google वर्तनी सुझावों के पीछे कुछ तकनीक के आधार पर एक साधारण "अस्पष्ट मिलान" वर्तनी सुधारक पर a very nice article लिखा था।

अपने शब्दकोश, N प्रविष्टियां हैं और औसत शब्द लंबाई L है, "ब्रूट बल Levenshtein" दृष्टिकोण समय O(N*L^3) ले जाएगा। पीटर नॉर्विग का दृष्टिकोण इनपुट से एक निश्चित संपादन दूरी के भीतर सभी शब्दों को उत्पन्न करता है, और उन्हें शब्दकोश में दिखता है। इसलिए यह O(L^k) प्राप्त करता है, जहां के सबसे दूर संपादित दूरी माना जाता है।