Levenshtein在.NET中的DFA

Question

下午好,

有没有人知道在.NET 中使用Levenshtein DFA(确定性有限自动机)的"开箱即用"实现(或者很容易翻译)？我有一个非常大的字典,有超过160000个不同的单词,我希望,给出一个内在的单词w,以高效的方式在Levenshtein距离中找到所有已知单词最多2个w.

当然,具有在编辑距离处计算所有可能编辑的功能,给定单词中的一个并将其再次应用于这些编辑中的每一个解决了该问题(并且以非常简单的方式).问题是效率刍议---给予7字母的单词,这已经可以采取超过1秒即可完成,而我需要的东西很多更有效的---如果可能的话,因为它与莱文斯坦的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 包。在我们的例子中，我们使用的是金砖四国自动机包的修改形式，其中转换表示为 unicode 代码点范围。

高效的单元测试对于这类事情来说是很困难的，但这就是我们想出的……它似乎很彻底，甚至在 moman 实现中发现了一个错误（作者立即修复了！）。

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