文字の混乱マトリックスと一致するおおよその文字列？

Question

私は、各単語の間にギャップがない携帯電話の長いストリームから単語のインスタンス（電話の文字列）を分離する必要がある音声認識者をモデル化しようとしています。携帯電話のストリームは、文字の置換/挿入/欠失により、認識が不十分である可能性があるため、概算の一致を行う必要があります。

ただし、「M」と「N」などが音声的に類似している場合、マッチングを音声的に動機付けすることを望んでいるため、「M」と「K」と比較して、「M」の「M」の代替コストは小さくする必要があります。 "。したがって、[Mein] "Main"を探している場合、文字シーケンス[Meim] "Maim"と一致します。たとえば、Cost 0.1と一致しますが、文字シーケンス[Meik]「Make」と一致します。 、コスト0.7。同様に、各文字を挿入または削除するためのコストが異なります。各文字ペア（x、y）に対して、xをyに置き換えるコストを与える混乱マトリックスを提供できます。ここで、xとyは任意の文字または空の文字列です。

私は、次のような一致を概算するツールが利用可能であることを知っています agrep, 、しかし、私が知る限り、彼らは入力として混乱マトリックスを取得しません。つまり、のコストです どれか 挿入/置換/削除= 1.私の質問は、混乱マトリックスと一致する近似を行うことができるオープンソースツールが既に利用可能であることがありますか？そうでない場合、これを達成するために実装できる良いアルゴリズムは何ですか？

編集：明確にするために、[aiammeinlimekink ...]などの長い文字列から[mein]などの単語の近似インスタンスを分離しようとしています。理想的には、アルゴリズム/ツールは、特定のしきい値を下回るコストを伴うすべてのおおよその文字列マッチについて、コスト0.0（正確な一致）、[MEIK]などのコスト0.7（近くの一致）などのインスタンスを報告する必要があります。

Answer 1

混乱マトリックスを使用する音声認識者は知りません。私は知っています soundex, 、 と 一致した評価.

私はそうだと思います k-nearest neightrアルゴリズム 興味のある近似の種類に役立つかもしれません。

Answer 2

ピーター・クレイウェグ ラグ/L04 （計算弁証法の場合）は、不均一な挿入、削除、および代替コストを指定できるLevenshtein距離の実装を含みます。