24

ここで文字列マッチングに関するいくつかの投稿に気付き、解決したい古い問題を思い出しました。Qwertyキーボードに重点を置いた優れたレーベンシュタインのようなアルゴリズムを持っている人はいますか?

2 つの文字列を比較して、タイプミスを許容したい。レーベンシュタインは問題ありませんが、Qwerty キーボードのキー間の物理的な距離に基づくスペルミスも受け入れたいと思います。つまり、ほとんどのキーボードでは、"y" キーが "z" キーよりも "t" キーの近くに配置されているため、アルゴリズムは "zelephone" よりも "yelephone" を優先する必要があります。

どんな助けでも素晴らしいでしょう...この機能は私のプロジェクトの中心ではないので、もっと生産的なことをしなければならないときに、ネズミの穴にはまりたくありません。

4

1 に答える 1

20

バイオインフォマティクスでは、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] )
)
于 2008-09-08T17:14:07.967 に答える