3

您好，感谢您的关注！

背景

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

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

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

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

问题

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

提前致谢！

马特

4

1 回答 1

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 毫秒的距离。

这对你有用吗？

(btw I'm not sure I can paste the code for the DP LED implementation I've got here so you probably should search the Internet for one Java implementation)

于 2012-01-08T19:15:02.717 回答