लेवेनशेटिन दूरी मिलान

Question

का उपयोग कर मिलानों का प्रतिशत रैंक मैं लेवेनशेटिन दूरी एल्गोरिदम का उपयोग करके संभावित मैचों के शब्दकोश के खिलाफ एक एकल खोज शब्द से मिलान करने का प्रयास कर रहा हूं। एल्गोरिदम खोज स्ट्रिंग को मिलान की गई स्ट्रिंग में परिवर्तित करने के लिए आवश्यक संचालन की संख्या के रूप में व्यक्त दूरी को लौटाता है। मैं परिणामों को शीर्ष "एन" (10 कहें) मैचों की रैंक प्रतिशत सूची में प्रस्तुत करना चाहता हूं।

चूंकि खोज स्ट्रिंग व्यक्तिगत शब्दकोश तारों की तुलना में लंबी या छोटी हो सकती है, इसलिए दूरी को प्रतिशत के रूप में व्यक्त करने के लिए उचित तर्क क्या होगा, जो गुणात्मक रूप से फिर से पूछेगा कि "प्रतिशत के रूप में" कितना करीब प्रश्न है स्ट्रिंग, 100% सटीक मिलान का संकेत देता है।

Q = query string 
M = matched string 
PM = Percentage Match 
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100 
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100 

विकल्प 1 नकारात्मक प्रतिशत करने की संभावना के मामले में दूरी खोज स्ट्रिंग की लंबाई, जहां मैच स्ट्रिंग लंबा है से अधिक है है:

मैं इन विकल्पों पर विचार किया। उदाहरण के लिए "एबीसी कॉर्प" से मेल खाता "एबीसी" क्वेरी परिणामस्वरूप नकारात्मक मिलान प्रतिशत होगा।

विकल्प 2 एम आई का एक सेट में एकरूप प्रतिशत देने के लिए प्रकट नहीं होता है, के रूप में प्रत्येक गणना संभवतः एक अलग भाजक का प्रयोग करेंगे और इसलिए परिणामस्वरूप प्रतिशत मान सामान्यीकृत नहीं होगा।

केवल अन्य तरीकों से मैं सोच सकता हूं कि lev_distance की तुलना स्ट्रिंग लेंस के साथ तुलना करना है, लेकिन इसके बजाय शीर्ष "एन" मैचों की तुलनात्मक दूरी को एक व्यस्त प्रतिशत रैंक (100-प्रतिशत-रैंक) के रूप में प्रस्तुत करना है।

कोई विचार? क्या बेहतर दृष्टिकोण हैं? मुझे कुछ याद आना चाहिए क्योंकि लेवेनशेटिन दूरी शायद अस्पष्ट मैचों के लिए सबसे आम एल्गोरिदम है और यह एक बहुत ही आम समस्या होनी चाहिए।

Answer 1

(1 - (levNum/Math.max(s.length,t.length))) *100 

सही

Answer 2

यह अनिवार्य रूप से विकल्प 2 मेरे सवाल में उल्लेख किया है किया जाना चाहिए। हालांकि मुझे उस दृष्टिकोण के साथ एक समस्या का प्रदर्शन करने दें।

Q = "ABC Corp" (len = 8) 
M1 = "ABC" 
M2 = "ABC Corporati" 
M3 = "ABC Corp" 

मैंने एम 1 और एम 2 चुना है जैसे कि उनके लेव दूरी समान हैं (5 प्रत्येक)। विकल्प 2 का उपयोग करना, मैच प्रतिशत

M1 = (1 - 5/8)*100 = 37.5% 
M2 = (1 - 5/13)*100 = 61.5% 
M3 = 100% 

हो आप भले ही वे ठीक उसी लेव दूरी है, तो एम 1 और एम 2 के बीच एक विशाल वरीयता श्रेणी अंतर है अगर मैं इसी क्रम में मैचों पेश देख सकते हैं, करेंगे। आप समस्या देखते हैं?

Answer 3

इस समस्या का मेरे दृष्टिकोण अधिकतम स्वीकृत संचालन की गणना है, जो है क्या Levenshtein दूरी है द्वारा किया गया। सूत्र मैं प्रयोग किया जाता है:

percent = 0.75; // at least 75% of string must match 
maxOperationsFirst = s1.length() - s1.length() * percent; 
maxOperationsSecond = s2.length() - s2.length() * percent; 
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond)); 

यह प्रत्येक स्ट्रिंग के लिए अधिकतम संचालन की गणना करता है, मुझे विश्वास है कि गणना समझने में आसान है। मैं दोनों परिणामों के न्यूनतम मूल्य का उपयोग करता हूं और इसे निकटतम पूर्ण संख्या में ले जाता हूं। आप इस भाग को छोड़ सकते हैं और स्ट्रिंग्स से अधिकतम संचालन के मूल्य का उपयोग कर सकते हैं, यह वास्तव में आपके डेटा पर निर्भर करता है।

एक बार जब आप अधिक से अधिक आपरेशन की संख्या है, तो आप Levenshtein परिणाम के साथ तुलना और तय करें कि स्ट्रिंग स्वीकार्य है सकते हैं। इस तरह से आप किसी भी बढ़ाया Levenshtein तरीकों, उदाहरण के Damerau–Levenshtein distance के लिए है, जो गिनती गलत वर्तनी, उदा उपयोग कर सकते हैंपरीक्षण ->, केवल 1 ऑपरेशन के रूप में, जो उपयोगकर्ता इनपुट की जांच करते समय काफी उपयोगी है जहां उन गलत वर्तनी अक्सर होती है।

मुझे आशा है कि इससे आपको इस समस्या को हल करने के बारे में एक विचार प्राप्त करने में मदद मिलेगी।

Answer 4

मुझे एक ही समस्या थी और इस धागे ने मुझे समाधान खोजने में मदद की। उम्मीद है कि यह दूसरों की भी मदद कर सकता है।

int levDis = Lev_distance(Q, Mi) 
int bigger = max(strlen(Q), strlen(Mi)) 
double pct = (bigger - levDis)/bigger 

यदि दोनों स्ट्रिंग बिल्कुल समान हैं और 0% यदि वे पूरी तरह अलग हैं तो 100% वापस आना चाहिए।

(खेद है कि मेरी अंग्रेजी अच्छी नहीं है)

Answer 5

क्या इस एक के बारे में:

100 - (((2*Lev_distance(Q, Mi))/(Q.length + Mi.length)) * 100) 

यह (Q, M1) पर एक ही दूरी और (Q,M2)