1

例如：如果我有字符串“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(string) 和 k = len(set)。但是，最大集合大小随 n^2 缩放，这意味着我们本质上是在处理 O(n^3)。这些集合相当静态，因此如果预处理会有所帮助，那绝对是一种选择。

最后，我应该提到这里的应用程序是确定哪些集合最接近所讨论的字符串，但我已经减少了这个问题，因为字符串长度是比集合数量更多的限制因素。如果有另一种方法可以通过将空间视为一个整体而不是单个子集来解决这个问题，我会全神贯注。当我第一次采用这种方法时，似乎空间复杂性会变得非常荒谬。

4

1 回答 1

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 距离度量应该很容易

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

于 2014-01-09T17:35:47.567 回答