与字母混乱矩阵匹配的近似字符串？

Question

我正在尝试建模语音识别器，该语音识别器必须将单词（电话字符串）的实例隔离在每个单词之间没有差距的长流中。手机流可能已经被众所周知，并有字母替换/插入/删除，因此我必须进行近似的字符串匹配。

但是，我希望匹配能够进行语音动机，例如“ M”和“ N”在语音上相似，因此“ M”的替换成本应该很小，与说“ M”和“ K” ”。因此，如果我要搜索[mein]“ main”，它将与字母序列[meim]“ maim”与0.1匹配，而它会匹配字母序列[meik]“ make”“ make'with，say， ，费用为0.7。同样，插入或删除每个字母的成本不同。我可以提供一个混淆矩阵，对于每个字母对（x，y），它给出用y代替x的成本，其中x和y是任何字母或空字符串。

我知道有一些可用的工具可以进行近似匹配，例如 agrep, ，但据我所知，它们不会将混乱矩阵作为输入。也就是说，成本 任何 插入/替换/删除=1。我的问题是，是否有任何可以使用混乱矩阵近似匹配的开源工具，如果没有，我可以实现什么好算法？

编辑：要清楚，我正在尝试将一个单词（例如[mein]）隔离为较长的字符串，例如[aiamemeinlimeiking ...]。理想情况下，算法/工具应报告实例，例如[Mein]，成本为0.0（精确匹配），[MEIK]，成本为0.7（接近匹配）等，所有近似字符串匹配，其成本低于给定的阈值。

Answer 1

我不知道有任何使用混乱矩阵的语音识别器。我知道 Soundex, ， 和 比赛等级.

我认为 k-nearest邻居算法 对于您感兴趣的近似值可能很有用。

Answer 2

彼得·克莱维格（Peter Kleiweg's） 地毯/L04 （对于计算方言学）包括实施Levenshtein距离，该距离使您可以指定非均匀的插入，删除和替换成本。