Levenshteinに似ていますが、Qwertyキーボードに重み付けされた良いアルゴリズムですか？

Question

私はここで文字列のマッチングにいくつかの記事を気付きました。これは私が解決したい古い問題を思い出させました。誰もQWERTYキーボードに重み付けされた良いLevenshteinアルゴリズムを持っていますか？

2つの文字列を比較して、誤字を許したいと思います。 Levenshteinは大丈夫ですが、Qwertyキーボードのキー間の物理的な距離に基づいてスペルミスを受け入れることをお勧めします。言い換えれば、アルゴリズムは、 "y"キーが "t"キーの近くに配置されているので、ほとんどのキーボードの "z"キーより "yelephone"から "zelephone"を優先する必要があります。

この機能は私のプロジェクトにとって中心的なものではないので、より生産性の高い何かをする必要があるときには、私はラットホールに逃げたくありません。

Answer 1

バイオインフォマティクスでは、DNAの2つの配列をアライメントすると、代入がトランジションかトランスバージョンかに基づいて異なるコストを持つモデルを持つ可能性があります。これはまさにあなたが望むものですが、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]) 
)