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