下午好,
有谁知道 .NET 中的 Levenshtein DFA(确定性有限自动机)的“开箱即用”实现(或易于翻译)?我有一个非常大的字典,其中包含超过 160000 个不同的单词,并且我想给定一个初始单词w ,以有效的方式在 Levenshtein 距离最多 2 个w找到所有已知单词。
当然,有一个函数可以计算给定单词的一个编辑距离处的所有可能的编辑,并将其再次应用于这些编辑中的每一个,可以解决问题(并且以一种非常简单的方式)。问题是效率 --- 给定一个 7 个字母的单词,这已经需要 1 秒多的时间才能完成,我需要更高效的东西---如果可能的话,就像 Levenshtein DFA 一样,一个需要 O( | w| ) 步骤。
编辑:我知道我可以通过一点学习来构建自己的解决方法,但目前我无法阅读 Schulz 和 Mihov 的 60 页长的文章。
非常感谢你。