एक सापेक्ष लेवेनशेटिन दूरी की गणना - समझ में आता है?

Question

मैं डेच-मोकोटॉफ ध्वनि और डैमरौ-लेवेनशेटिन दोनों का उपयोग कर रहा हूं यह पता लगाने के लिए कि क्या कोई उपयोगकर्ता प्रविष्टि और एप्लिकेशन में कोई मान "समान" है।

क्या लेवेनशेटिन दूरी को पूर्ण मूल्य के रूप में उपयोग किया जाना चाहिए? अगर मेरे पास 20 अक्षर का शब्द है, तो 4 की दूरी इतनी खराब नहीं है। यदि शब्द में 4 अक्षर हैं ...

अब मैं जो कर रहा हूं वह दूरी प्राप्त करने के लिए दूरी/लंबाई ले रहा है जो बेहतर ढंग से दर्शाता है कि शब्द का प्रतिशत किस प्रकार बदला गया है।

क्या यह एक वैध/सिद्ध दृष्टिकोण है? या यह सादा बेवकूफ है?

Answer 1

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

ऐसा लगता है कि यह आपकी आवश्यकताओं पर निर्भर करेगा। (स्पष्टीकरण के लिए: Levenshtein दूरी एक पूर्ण मूल्य है, लेकिन जैसा कि ओपी ने बताया है, कच्चे मान किसी दिए गए एप्लिकेशन के लिए उतना उपयोगी नहीं हो सकता है जितना कि शब्द की लंबाई को ध्यान में रखता है। ऐसा इसलिए है क्योंकि हम वास्तव में अधिक दूरी से प्रति से समानता में रुचि रखते हैं।)

मैं उपयोग कर रहा हूँ दोनों Daitch-Mokotoff soundexing और को Damerau-Levenshtein पता लगाना यदि कोई उपयोगकर्ता प्रवेश और आवेदन में एक मूल्य "कर रहे हैं एक ही "।

आप यह निर्धारित करने के लिए उपयोगकर्ता इरादा उनकी प्रविष्टि किसी दिए गए डेटा मूल्य के बराबर हो जाए कि क्या कोशिश कर रहे हैं की तरह लगता है?

क्या आप वर्तनी-जांच कर रहे हैं? या मूल्यों के एक ज्ञात सेट में अमान्य इनपुट अनुरूप? आपकी प्राथमिकताओं क्या हैं?

• कम से कम झूठे सकारात्मक (सुनिश्चित करें कि सभी सुझाए गए शब्दों बहुत "समान" हैं बनाने के लिए प्रयास करें, और सुझावों की सूची छोटा है)
• कम से कम मिथ्या नकारात्मक (सुनिश्चित करें कि स्ट्रिंग उपयोगकर्ता का इरादा है बनाने की कोशिश सुझावों की सूची, भले ही वह लंबी सूची)
• अधिकतम औसत मिलान सटीकता बनाता

आप हो सकता है एक तरह से Levenshtein दूरी का उपयोग निर्धारित करने के लिए एक शब्द भी एक सुझाव सूची में की पेशकश की जानी चाहिए अंत; और सुझाव सूची को ऑर्डर करने का तरीका निर्धारित करने का एक और तरीका है।

ऐसा लगता है, अगर मैंने आपके उद्देश्य को सही तरीके से अनुमानित किया है, तो मूल चीज जिसे आप मापना चाहते हैं समानता दो तारों के बीच अंतर के बजाय है।

दिए गए दो तार एस 1 और एस 2 की Jaro दूरी dj

(m/|s1| + m/|s2| + (m - t)/m)/3 

है: इस तरह के रूप में, आप Jaro or Jaro-Winkler distance, जिसके खाते में तार की लंबाई और आम में वर्णों की संख्या लेता इस्तेमाल कर सकते हैं

जहां:

• मीटर मिलान वर्णों की संख्या है
• टी प्रतिस्थापन की संख्या है

Jaro-विंकलर दूरी एक उपसर्ग पैमाने पी जो तार कि से मेल खाते हैं एक सेट उपसर्ग लंबाई एल के लिए शुरू करने के लिए और अधिक अनुकूल रेटिंग देता है उपयोग करता है।

Answer 2

लेवेनशेटिन दूरी दो शब्दों के बीच एक सापेक्ष मूल्य है। > गोबर = 1 (75% समान ??)

अंतर - - लंबाई में एलडी तुलना प्रासंगिक जैसे

बिल्ली नहीं है> मतभेद = 1 (90% समान ??)

इन दोनों शब्दों में 1 की लेव दूरी होती है यानी वे एक चरित्र से अलग होते हैं, लेकिन जब उनकी लंबाई की तुलना में दूसरा सेट 'अधिक' जैसा प्रतीत होता है।

मैं soundexing का उपयोग शब्द है कि एक ही लेव दूरी जैसे

cat और fat दोनों 1 kat के सापेक्ष के एलडी है रैंक करने के लिए है, लेकिन शब्द जब soundex का उपयोग कर वसा की तुलना में कैट होने की अधिक संभावना है (यह मानते हुए शब्द गलत वर्तनी है, गलत टाइप नहीं किया गया है!)

तो संक्षिप्त उत्तर केवल समानता निर्धारित करने के लिए लेव दूरी का उपयोग करता है।