计算字符串和字符串之间的最小汉明距离

Question

例如： 如果我有字符串“asdf”和字符串集（“qwer”，“aswr”，“asdv”）。集合和字符串之间的汉明距离为1，因为“asdv”和“asdf”的汉明距离为1。

很容易蛮力像这样的东西

def hamming_distance(string, set): 
    min = len(string) 
    for element in set: 
     element_distance = sum(ch1 != ch2 for ch1, ch2 in zip(string, element)) 
     if min > element_distance: 
      min = element_distance 
     if min == 0: 
      break 
    return min 

我觉得这为O（n * K），其中n = LEN（字符串）和k = LEN（套）。然而，最大集大小与n^2成比例，这意味着我们基本上处理O（n^3）。该集相当静态，所以如果预处理将有助于这绝对是一种选择。

最后，我应该提及的是，这里的应用程序是要确定哪个集合最接近问题的字符串，但我减少了这个问题，因为字符串长度是一个更多的限制因素集。如果还有另外一种方法来看待整个空间而不是单个子集，我会全神贯注。当我第一次采取这种方法时，似乎空间复杂性将会变得完全荒谬。

Answer 1

首先，字符串之间的海明距离是一个度量标准。因此，您试图在度量空间（其中k = 1）中找到k-最近邻。因此，您可能需要考虑类似于M-Tree数据结构的树（请参见http://en.wikipedia.org/wiki/M-tree和http://www.vldb.org/conf/1997/P426.PDF）。该树旨在减少需要执行的查找“最近邻居”数量的距离比较。个人而言，我无法在网上找到一个我满意的M-Tree的实现（查看我的已关闭线程寻找一个成熟的M-Tree实现），所以我推出了自己的。

我的实现是在这里：https://github.com/jon1van/MTreeMapRepo

唯一的其他实现我能找到的是这样一条：https://github.com/erdavila/M-Tree我不喜欢这个实现，因为它没有删除功能（以及其他一些问题），（但它是免费的，所以...那很好）。

您可能想要考虑使用我的代码（它解决了通用度量空间中的kNN搜索）和Levensthtein距离度量（http://en.wikipedia.org/wiki/Levenshtein_distance）。找到一个完全实现Levenshtein距离度量在线应该是很容易

添加编辑距离函数** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/LevensteinDistance.java?r=181