快速计算大字符串之间距离的 C# 代码或算法？

Question

您好，感谢您的浏览！

背景

我有一个包含 1900 个节点的 XML 文件，这些节点本身包含一串大约 3400 个字符的编码数据。

作为我正在开发的应用程序用例的一部分，我需要能够在运行时获取“基准”字符串，并从 XML 文件中找到最接近匹配。

请注意，XML 与应用程序没有密切关系，我可能会继续使用 SQL，但今天，我只需要一个简单的地方来存储数据并证明这个概念。

我正在使用 .NET 4.0、C#、表单应用程序、LINQ 等。

问题

如何找到最接近的匹配项？汉明？编辑？网上有很多代码示例，但大多数都是针对小字符串比较（“ant”与“aunt”）或精确匹配。我很少有完全匹配；我只需要最接近匹配。

提前致谢！

马特

Answer 1

您提到使用 Levenhstein 的编辑距离，并且您的字符串长度约为 3400 个字符。

我做了一个快速尝试，并使用 Levenhstein 的编辑距离的动态编程版本，它似乎相当快并且没有引起任何问题。

我这样做了：

        final StringBuilder sb1 = new StringBuilder();
        final StringBuilder sb2 = new StringBuilder();
        final Random r = new Random(42);
        final int n = 3400;
        for (int i = 0; i < n; i++) {
            sb1.append( (char) ('a' + r.nextInt(26)) );
            sb2.append( (char) ('a' + r.nextInt(26)) );
        }
        final long t0 = System.currentTimeMillis();
        System.out.println("LED: " + getLevenshteinDistance(sb1.toString(), sb2.toString()) );
        final long te = System.currentTimeMillis() - t0;
        System.out.println("Took: " + te + " ms");

它在 2006 年左右的 Core 2 Duo 上以 215 毫秒的时间计算出距离。

这对你有用吗？

（顺便说一句，我不确定是否可以粘贴我这里的 DP LED 实现的代码，因此您可能应该在 Internet 上搜索一个 Java 实现）