6

下午好，

有谁知道 .NET 中的 Levenshtein DFA（确定性有限自动机）的“开箱即用”实现（或易于翻译）？我有一个非常大的字典，其中包含超过 160000 个不同的单词，并且我想给定一个初始单词w ，以有效的方式在 Levenshtein 距离最多 2 个w找到所有已知单词。

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

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

非常感谢你。

4

6 回答 6

2

我们为 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 automaton 包的修改形式，其中转换表示为 unicode 代码点范围。

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

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

于 2010-10-26T15:40:12.027 回答
1

干得好。

/// <summary>
/// Levenshtein Distance Calculator
/// </summary>
public static int DistanceFrom(this string s, string t)
{
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    // Step 1
    if (n == 0)
        return m;

    if (m == 0)
        return n;

    // Step 2
    for(int i = 0; i <= n; d[i, 0] = i++) ;
    for(int j = 0; j <= m; d[0, j] = j++) ;

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
            // Step 5
            int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

            // Step 6
            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
}
于 2010-10-20T11:29:09.620 回答
1

我按照 Robert Muir 的建议将相关的 Lucene Java 代码移植到了 C#。就问题和“开箱即用”而言：这是一项正在进行的工作，但代码似乎¹可以工作，并且可能可以进一步优化²，尽管它确实表现得非常好。

你可以在这里找到它：https ://github.com/mjvh80/LevenshteinDFA/ 。

更新：看起来 Lucene.NET 实际上还没有死（还没有？），我注意到他们现在也有这个代码的移植版本。因此，我建议在此处查看（https://github.com/apache/lucenenet/blob/master/src/Lucene.Net.Core/Util/Automaton/LevenshteinAutomata.cs）以实现此功能。

¹ 代码需要更多测试
² 因为它可能是Java 移植到C# 并且因为我编写了一些类的天真替换（例如bitset）。

于 2014-09-04T06:44:39.827 回答
0

我知道您想在一本大字典中找到相近的匹配项。这是我的做法。关联。

从我对 DFA 的了解来看，我看不出它在皮肤下有什么更好，甚至实际上有什么不同。NFA 可能更快，但那是因为它们不存在。也许我错了。

于 2010-10-20T21:44:24.473 回答
0

Nick Johnson 有一篇非常详细的博客文章，介绍了用 Python 构建 Levenshtein 自动机，代码在这里。这是一本很好的读物，我使用了稍微修改过的代码版本，我发现它很有效。

Mike Dunlavey 的回答也很好。我想知道在这种情况下什么是最有效的，是 trie 搜索还是 Levenshtein DFA？

于 2014-07-08T23:13:14.893 回答
0

我只想指出，到目前为止，Lucene 和 Lucene.Net 中的 Levenshtein Automaton 实现都使用了包含参数状态表（描述自动机中具体状态的抽象状态表）的文件，这些文件是使用Moman创建的。

如果您想要一个能够在内存中从头开始构建此类表的解决方案，您可能想看看LevenshteinAutomaton。它是用 Java 编写的，但结构良好、易于理解且注释广泛，因此应该比当前的 Lucene 实现更容易移植到 C#。它也由moi维护。

* 有趣的事实：我提交 LevenshteinAutomaton 作为替代品，或作为替代品的参考，用于 Lucene 中当前的 Levenshthein Automaton 实现...... 3 年前。

于 2016-07-02T02:13:32.983 回答