लेवेनशेटिन के समान एक अच्छा एल्गोरिदम लेकिन क्वर्टी कीबोर्ड के लिए भारित?

Question

मैं स्ट्रिंग मिलान, जो मुझे एक पुरानी समस्या का समाधान मैं करना चाहते हैं की याद दिला दी पर यहाँ कुछ पदों देखा। क्या किसी के पास Levenshtein-जैसे एल्गोरिदम है जो क्वर्टी कीबोर्ड की ओर भारित है?

मैं दो तार की तुलना करें और और गलत वर्तनी की अनुमति देना चाहते हैं। लेवेनशेटिन ठीक है, लेकिन मैं क्वर्टी कीबोर्ड पर चाबियों के बीच भौतिक दूरी के आधार पर वर्तनी त्रुटियों को भी स्वीकार करना चाहता हूं। दूसरे शब्दों में, एल्गोरिथ्म के बाद से "y" कुंजी सबसे कीबोर्ड पर "Z" कुंजी करने के लिए की तुलना में "टी" कुंजी के नजदीक स्थित है "yelephone" से "zelephone" को प्राथमिकता देनी चाहिए।

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

Answer 1

जैव सूचना विज्ञान में जब आप डीएनए के दो दृश्यों संरेखित आप एक मॉडल है, तो प्रतिस्थापन एक संक्रमण या एक transversion है एक अलग आधार पर लागत है कि हो सकता है। यह वही है जो आप चाहते हैं लेकिन 4x4 मैट्रिक्स के बजाय, आप 40x40 मैट्रिक्स या कुछ चाहते हैं, मैं दूरी समारोह कहने की हिम्मत करता हूं? इसलिए प्रतिस्थापन की लागत मैट्रिक्स/फ़ंक्शन से स्थिर नहीं है।

कैवेट: सुनिश्चित करें कि हटाने और सम्मिलन ठीक से भारित हैं, इसलिए उन्हें न्यूनतम के रूप में स्वीकार नहीं किया जाता है। आप सम्मिलन/विलोपन/कोई-परिवर्तन-प्रतिस्थापन वर्णों की एक स्ट्रिंग के साथ समाप्त हो जाएंगे।

नए कार्य को आप कम करने के लिए कोशिश कर रहे हैं होगा:

d[i, j] := minimum(
    d[i-1, j] + del_cost, 
    d[i, j-1] + ins_cost, 
    d[i-1, j-1] + keyboard_distance(s[i], t[j]) 
)