带有权重的Levenshten自动机
本文关键字：Levenshten 自动机 权重 | 更新日期: 2023-09-27 18:21:54
我正在寻找一种在字典中快速搜索模糊字符串的算法（以及它在c#上的实现）。到目前为止，我发现了一种叫做Levenstein自动机的方法（在这里描述）。它似乎与我的需求非常相似。但我想对不同的错误给出不同的权重。假设混淆s和c是很常见的，所以这样一个错误的权重会很小。此外，如果能够考虑多个字母的错误，如s->ph等等，那就太好了。有算法描述这样的事情吗？
Levenstein自动机在距离源字符串（即用于构建自动机的字符串）一定编辑距离内匹配目标字符串。这是超快的，但缺点是你无法自定义编辑成本（你可能想想象一个短字符串的Levenstein自动机，有不同的编辑成本……这会很混乱……即使是短字符串）。
也许您应该考虑一下众所周知的动态编程方法（这里），它允许您定义自定义编辑成本。