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

Question

嗨，感谢您的期待！

背景

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

其使用情况我开发的应用程序的一部分，我需要能够采取“基准”的字符串在运行时，能够由该XML文件中的最接近匹配。

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

我使用.NET 4.0，C＃，窗体应用程序，LINQ等等

问题

如何找到最接近的匹配？海明？莱文斯坦？网上有很多代码示例，但大多数都适用于小字符串比较（“蚂蚁”与“阿姨”）或完全匹配。我很少有确切的匹配;我只需要最接近的比赛。

在此先感谢！

马特

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实现我已经在这里了，所以你或许应该在互联网上搜索一个Java实现）