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

Question

前： 如果我有字符串“asdf”和字符串集（“qwer”，“ASWR”，“ASDV”）。该集合与弦之间的汉明距离为1，因为“ASDV”和“ASDF”具有汉明距离。

这很容易蛮力，如这种

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

.

我认为这有一个（n * k），其中n= len（string）和k= len（set）。但是，具有n ^ 2的最大集大小缩放，这意味着我们基本上处理O（n ^ 3）。集合相当静态，所以如果预处理会有所帮助，这绝对是一个选择。

最后，我应该提及这里的应用程序是确定哪个集合最接近有问题的字符串，但我降低了问题，因为字符串长度是比集数量更加限制因素。 。如果通过查看整个空间而不是各自的子集来实现这一方法，而不是我将全部耳朵。当我第一次采取这种方法时，它似乎是空间复杂性的时候会变得完全荒谬。

Answer 1

首先，字符串之间的汉明距离是指标。因此，您正在尝试在公制空间中找到k离邻居（其中k= 1）。

因此，您可能希望考虑类似于M树数据结构的树:(参见 http://en.wikipedia.org/wiki/m-tree 和 http ：//www.vldb.org/conf/1997/p426.pdf ）。该树旨在减少需要执行以查找“最近邻居”的数字距离比较。

亲自，我无法在线找到一个在线实现我对我满意的（看我的封闭线程寻找成熟的M树实现）所以我自己滚动了。

我的实现在这里： https：//github.com/jon1van/mtreeemaprepo

我可以找到的唯一实现是这个： https：//github.com/erdavila/m -tree 我不喜欢这个实现，因为它没有删除功能（以及其他几个问题）（但它是免费的......这很好）。

您可能需要考虑使用LevenSthtein距离度量（ http://en.wikipedia.org/wiki/levenshtein_distance ）。找到完全实现的Levenshtein距离度量标准在线应该非常容易... / p>

附加levenstein距离功能** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distans/levensteindistance.java?r= 181