Levenshteins को संशोधित करने के लिए कैसे संपादित करें "आसन्न पत्र एक्सचेंज" को 1 संपादित करें

Question

मैं Levenshteins Edit Distance algorithm के साथ खेल रहा हूं, और मैं इसे विस्तारित करने के लिए विस्तारित करना चाहता हूं - यानी, आसन्न अक्षरों के आदान-प्रदान - 1 संपादन के रूप में । अनमोडिफाइड एल्गोरिदम दूसरे से एक निश्चित स्ट्रिंग तक पहुंचने के लिए आवश्यक सम्मिलन, हटाना या प्रतिस्थापन की गणना करता है। उदाहरण के लिए, "बिल्ली का बच्चा" से संपादित दूरी के "बैठे" 3. यहाँ विकिपीडिया से व्याख्या दी गई है:

1. बिल्ली का बच्चा → Sitten
2. Sitten → बैठे ('एस' के साथ 'k' का प्रतिस्थापन) ('i' के साथ 'ई' का प्रतिस्थापन)
3. सिट्टिन → बैठे (अंत में 'g' डालें)।

एक ही विधि के बाद, "chiar" से संपादित दूरी के "कुर्सी" 2:

1. chiar → CHAR
2. CHAR → चेयर (('मैं' को हटाना) 'मैं डालने ')

मैं इसे "1 संपादन" के रूप में गिनना चाहता हूं, क्योंकि मैं केवल दो आसन्न अक्षरों का आदान-प्रदान करता हूं। मैं ऐसा करने के लिए कैसे जाउंगा?

Answer 1

आप विकिपीडिया से एल्गोरिथ्म में एक और मामले की जरूरत है:

if s[i] = t[j] then 
    d[i, j] := d[i-1, j-1] 
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then 
    d[i, j] := minimum 
      (
       d[i-2, j-2] + 1 // transpose 
       d[i-1, j] + 1, // deletion 
       d[i, j-1] + 1, // insertion 
       d[i-1, j-1] + 1 // substitution 
      ) 
else 
    d[i, j] := minimum 
      (
       d[i-1, j] + 1, // deletion 
       d[i, j-1] + 1, // insertion 
       d[i-1, j-1] + 1 // substitution 
      ) 

Answer 2

आप कैसे आप गतिशील प्रोग्रामिंग तालिका अद्यतन संशोधित करने के लिए किया है। मूल एल्गोरिदम में दो शब्दों के पूंछ (या सिर) को मानते हैं जो लंबाई में सबसे अधिक भिन्न होते हैं। अद्यतन ऐसी सभी संभावनाओं में से न्यूनतम है।

यदि आप एल्गोरिदम को संशोधित करना चाहते हैं जैसे कि दो आसन्न स्थानों में परिवर्तन एक के रूप में गिना जाता है, तो ऊपर दिए गए न्यूनतम को पूंछ (या सिर) पर गणना की जानी चाहिए जो कि अधिकतम दो से भिन्न होती है। आप इसे बड़े पड़ोस में बढ़ा सकते हैं लेकिन जटिलता उस पड़ोस के आकार में तेजी से बढ़ेगी।

आप आगे सामान्यीकृत कर सकते हैं और उन लागतों को असाइन कर सकते हैं जो हटाए गए, डाले गए या प्रतिस्थापित किए गए चरित्र (ओं) पर निर्भर करते हैं, लेकिन आपको यह सुनिश्चित करना होगा कि जोड़ी आप एक जोड़ी-संपादन को आवंटित करते हैं, वह दो एकल संपादन से कम है, अन्यथा दो एकल संपादन हमेशा जीतेंगे।

शब्द w1 होने दो और W2

dist(i,j) = min(
       dist(i-2,j-2) && w1(i-1,i) == w2(j-1,j) else 
       dist(i-1,j-1) && w1(i) == w2(j) else 
       dist(i,j-1) + cost(w2(j)), 
       dist(i-1,j) + cost(w1(i)), 
       dist(i-1,j-1) + cost(w1(i), w2(j)), 
       dist(i, j-2) + cost(w2(j-1,j)), 
       dist(i-2, j) + cost(w1(i-1,i)), 
       dist(i-2,j-2) + cost(w1(i-1,i), w2(j-1,j)) 
       ) 

क्या मैं && मतलब उन पंक्तियों की स्थिति से संतुष्ट हैं केवल तभी विचार किया जाना चाहिए कि है।

Answer 3

अन्य उत्तर इष्टतम स्ट्रिंग संरेखण एल्गोरिदम लागू कर रहे हैं, Damerau Levenshtein जो मुझे लगता है कि आप जो वर्णन कर रहे हैं वह है।

मैं कुछ अनुकूलन यहाँ के साथ ओएसए की एक जावा कार्यान्वयन है: https://gist.github.com/steveash/5426191