将字符串排序，使相邻字符串的汉明距离较低

Question

问题：

我有 N (~100k-1m) 个字符串，每个字符串长度为 D（例如2000），并且只由低字母表（例如3个可能的字符）组成。我希望对这些字符串进行排序，以便相邻字符串之间的差异最小（例如哈明距离较低）。解决方案不必是最佳的，但越接近越好。

示例

N=4
D=5
//initial strings
1. aaacb
2. bacba
3. acacb
4. cbcba

//sorted so that hamming distance between adjacent strings is low
1. aaacb
3. acacb (Hamming distance 1->3 = 1)
4. cbcba (Hamming distance 3->4 = 4)
2. bacba (Hamming distance 4->2 = 2)

对问题的思考

我觉得这是一个非常棘手的问题。如果我们将每个字符串看作一个节点，将到其他字符串的距离看作边，则需要解决旅行推销员问题。由于字符串数量很大，预先计算所有两两之间的距离可能是不可行的，因此我认为可以将其转化为类似于加拿大旅游者问题。

目前，我的解决方案是使用VP树来找到贪心的最近邻居解决方案。

curr_string = a randomly chosen string from full set
while(tree not empty)
    found_string = find nearest string in tree
    tree.remove(found_string)
    sorted_list.add(curr_string)
    curr_string = found_string

但是最初的结果似乎很差。将字符串哈希化以使相似度更高的字符串更接近可能是另一种选择，但我对它提供的解决方案质量以及在这种数据规模下的扩展性了解甚少。

- bwgoudey

Answer 1

即使您认为这个问题与旅行商问题（TSP）类似，我相信汉明距离将遵循三角不等式（Hamming（A，B）+ Hamming（B，C）≤ Hamming（A，C）），因此您只需要处理∆TSP（度量旅行商问题），对于这个问题，有许多算法可以给出理想结果的良好近似值。特别是，Christofides算法总会给出一条长度最多为最小可能长度的1.5倍的路径。请注意保留HTML标签。

- user149341

Answer 2

是的，这是一个旅行商问题， 但我不知道在 TSP源代码库 下的十几个程序中是否有能够直接处理1M点和插件度量的。

可能的两个阶段方法：

1）使用最近邻搜索将1M点分成50个簇。 对50个聚簇中心执行TSP。

2）将所有1M-50点放置在两个最近中心之间； 对每个1M / 50字符串执行TSP。 这里“50”可以是100或1000，如果1000太大，则递归：将1000分成约30个大小为30的簇。

K-means可以集群1M点， 但同样我不知道是否有带插件度量的快速实现。 但请参见scikit-learn clustering。

要找到N个点的质心， 其中最小化|中心-所有其他点|, 你可以通过从sqrt(N)的随机样本中选择最佳结果， afaik可以击败O(N^2)——应该足够好了。(或者在快速近似质心上进行谷歌/提问单独的问题)。

首先紧密地打包数据以节省整个流程中的内存访问。 在这种情况下，将a b c编码为00 01 10 (每对之间的海明距离=1)： 2000 x 2位=500字节。 顺便说一下，在我的mac ppc上找到min Hammingdist(4k位，10k x 4k)需要大约40毫秒。

- denis