خوارزمية جيدة تشبه Levenshtein ولكنها مرجحة للوحات مفاتيح Qwerty؟

Question

لقد لاحظت بعض المشاركات هنا حول مطابقة السلسلة، والتي ذكّرتني بمشكلة قديمة أود حلها.هل لدى أي شخص جيدة ليفنشتاين-مثل الخوارزمية التي يتم وزنها نحو لوحات مفاتيح Qwerty؟

أريد مقارنة سلسلتين، والسماح للأخطاء المطبعية.Levenshtein على ما يرام، لكنني أفضل أيضًا قبول الأخطاء الإملائية بناءً على المسافة الفعلية بين المفاتيح على لوحة مفاتيح Qwerty.بمعنى آخر، يجب أن تفضل الخوارزمية "yelephone" على "zelephone" نظرًا لأن المفتاح "y" يقع بالقرب من المفتاح "t" بدلاً من المفتاح "z" في معظم لوحات المفاتيح.

أي مساعدة ستكون عظيمة...هذه الميزة ليست مركزية في مشروعي، لذلك لا أريد أن أنحرف إلى حفرة الجرذ عندما يجب أن أفعل شيئًا أكثر إنتاجية.

Answer 1

في المعلوماتية الحيوية، عندما تقوم بمحاذاة تسلسلين من الحمض النووي، قد يكون لديك نموذج له تكلفة مختلفة بناءً على ما إذا كان الاستبدال عبارة عن انتقال أو تحويل.هذا هو بالضبط ما تريده ولكن بدلاً من مصفوفة 4 × 4، هل تريد مصفوفة 40 × 40 أو بعضها، هل أجرؤ على قول دالة المسافة؟وبالتالي فإن تكلفة الاستبدال هي من المصفوفة/الوظيفة، وليست ثابتة.

تنبيه قضائي:تأكد من أن عمليات الحذف والإدراج قد تم ترجيحها بشكل صحيح، بحيث لا يتم قبولها بشكل مبالغ فيه كحد أدنى.سينتهي بك الأمر بسلسلة من أحرف الإدراج/الحذف/عدم التغيير والاستبدال.

الوظيفة الجديدة التي تحاول تقليلها ستكون:

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] )
)