.net - .NET 中的 Levenshtein DFA

Question

下午好，

有谁知道 .NET 中 Levenshtein DFA(确定性有限自动机)的“开箱即用”实现(或易于翻译)？我有一个很大的字典，里面有超过 160000 个不同的单词，我想在给定一个初始单词 w 的情况下，以一种有效的方式找到 Levenshtein 距离最多 2 个 w 的所有已知单词。

当然，有一个函数可以计算给定单词的一个编辑距离处的所有可能的编辑，并将其再次应用于这些编辑中的每一个，解决了这个问题(并且以一种非常直接的方式)。问题是效率 --- 给定一个 7 个字母的单词，这已经需要 1 秒多的时间才能完成，我需要更高效的东西 --- 如果可能的话，就像 Levenshtein DFA 一样，这是一个需要 O(| w|) 步骤。

编辑:我知道我可以通过一点点学习来构建自己的解决问题的方法，但目前我无法阅读 Schulz 和 Mihov 长达 60 页的文章。

非常感谢。

Answer 1

我们为 apache lucene java 实现了这个，也许你可以将它转换为 C# 并节省自己的时间。

主类在这里:它只是一个使用 Schulz 和 Mihov 算法从字符串中获取 Levenshtein DFA 的构建器。

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java

Lev1 和 Lev2 的参数描述(预先计算的表)在这里:
http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev1ParametricDescription.java

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev2ParametricDescription.java

你可能会注意到这些是用计算机生成的，我们用这个脚本生成了它们，使用 Jean-Phillipe Barrette 的伟大的 moman 实现(python)
http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/createLevAutomata.py

我们将参数描述生成为打包的 long[] 数组，以便它不会使我们的 jar 文件太大。

只需修改 toAutomaton(int n) 以满足您的需求/DFA 包。在我们的例子中，我们使用了 brics 自动机包的修改形式，其中转换表示为 unicode 代码点范围。

有效的单元测试对于这类事情是困难的，但这是我们提出的……它似乎很彻底，甚至在 moman 实现中发现了一个错误(作者立即修复了!)。

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/test/org/apache/lucene/util/automaton/TestLevenshteinAutomata.java