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实现)