ele*_*ora 9 string algorithm hamming-distance
如果您有n二进制字符串,每个长度m,是否有更快的方法来确定任何一对之间的最小汉明距离,而不是比较所有O(n^2)对和每个以计算其汉明距离？
那可以在不到一定的
O(n^2m)时间内完成吗？
除了其他任何东西,如下所述,汉明距离是一个适当的距离函数,因此满足三角不等式,这让我觉得应该有一个更快的解决方案.
考虑使用Locality Sensitive Hashing,这是一种可应用于某些距离指标(包括汉明距离)的通用技术.维基百科摘录:
LSH散列输入项目,以便类似项目以高概率映射到相同的"桶"(桶的数量远小于可能的输入项的范围).
简而言之,您可以使用LSH获取每个桶内的桶,蛮力汉明距离,并输出找到的最小距离.为了以更高的概率获得正确的答案,您可以调整LSH算法的参数和/或多次运行LSH(以便将不同的项目分配到存储桶).我相信你可以任意接近正确的(最佳)答案,失败率在运行时呈指数下降.(如果您的汉明距离非常接近,您可能必须对LSH参数进行二分搜索,但您仍然可以避免计算n^2汉明距离.)
算法和分析非常复杂,所以我不认为我现在可以在这里写一个完整的摘要(这是一个大约2-3小时的讲座材料).我建议在这里,这里和这里看一下讲义/幻灯片; 它们都覆盖了LSH(不同程度的细节),并提到了汉明距离.