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

嗨,谢谢你的期待!

背景

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

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

请注意,XML与应用程序没有密切关系,我可能会继续使用SQL,但就今天而言,我只需要一个容易存储数据并certificate概念的地方。

我使用的是.NET 4.0,C#,表单app,LINQ等。

我如何找到最接近的匹配? 海明? 莱文斯坦? 网上有很多代码样本,但大多数是针对小字符串比较(“ant”与“阿姨”)或完全匹配。 我很少有完全匹配; 我只需要最接近的比赛。

提前致谢!

马特

你提到使用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实现)