11

问题：

我有 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

但初步结果似乎很差。散列字符串以使更多相似的字符串更接近可能是另一种选择，但我对这将提供一个多么好的解决方案或它将如何扩展到这种大小的数据知之甚少。

4

2 回答 2

2

即使你认为这个问题类似于旅行商问题（TSP），我相信汉明距离将遵循三角不等式（汉明（A，B）+汉明（B，C）≤汉明（A，C）），所以你只真正处理 ΔTSP（度量旅行商问题），有许多算法可以在理想结果下提供良好的近似值。特别是，Christofides 算法将始终为您提供最多 1.5 倍最小可能长度的路径。

于 2012-01-05T07:19:06.297 回答
1

是的，这是一个旅行推销员问题，但我不知道 TSP 源代码库下的十几个程序中是否有任何一个 可以直接做到 1M 点，并带有插件度量。

一种可能的两阶段方法：

1) 用最近邻搜索将 1M 点分成 50 个簇 。对 50 个集群中心进行 TSP。

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

K-means 可以聚类 1M 点，但我也不知道有插件度量的快速实现。但是请参见 scikit-learn 聚类

要找到 N 个点的质心，一个最小化 |centre - all others| 的质心，您可以仅通过获取最好的随机样本，例如 sqrt(N) 来击败 O(N^2) - 应该足够好。（或谷歌/问一个关于快速近似质心的单独问题）。

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

于 2012-01-05T09:53:31.213 回答