计算字符串和设置字符串之间的最小汉明距离
-
21-12-2019 - |
题
前: 如果我有字符串“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)。集合相当静态,所以如果预处理会有所帮助,这绝对是一个选择。
最后,我应该提及这里的应用程序是确定哪个集合最接近有问题的字符串,但我降低了问题,因为字符串长度是比集数量更加限制因素。 。如果通过查看整个空间而不是各自的子集来实现这一方法,而不是我将全部耳朵。当我第一次采取这种方法时,它似乎是空间复杂性的时候会变得完全荒谬。
解决方案
首先,字符串之间的汉明距离是指标。因此,您正在尝试在公制空间中找到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