基于给定的汉明距离折叠字符串集

Question

给定一组字符串（第一列）和计数（第二列），例如：

aaaa 10
aaab 5
abbb 3
cbbb 2
dbbb 1
cccc 8

是否有任何算法甚至实现（理想情况下是作为Unix执行程序、R或python）根据给定的hamming距离将这个集合折叠成一个新的集合。你知道吗

• 折叠意味着添加计数
• 计数较低的字符串将折叠为计数较高的字符串。你知道吗

例如，对于汉明距离1，上面的集合将把第二个字符串aaab折叠成aaaa，因为它们相隔1个汉明距离，aaaa具有更高的计数。 折叠的条目将具有组合计数，在这里aaaa 15

因此，对于这个集合，我们将得到以下折叠的集合：

aaaa 15
abbb 6
cccc 8

理想情况下，实现应该是有效的，因此即使是不能保证最优解决方案的启发式算法也会受到赞赏。你知道吗

进一步的背景和动机

大多数编程语言都实现了计算两个字符串（一对）之间的汉明距离。暴力解决方案将计算所有对之间的距离。也许没办法。然而，我认为一个有效的解决方案可以避免计算所有对的距离等。也许有一些聪明的方法可以节省一些基于度量理论的计算（因为汉明距离是一个度量），例如，如果x和z之间的汉明距离是3，x和y是3，我可以避免计算y和z之间的距离。也许有一个聪明的方法k-mer方法，或者可能是某个恒定距离的有效解（比如d=1）。你知道吗

即使只有一个暴力解决方案，我也会好奇这是否已经实现了，以及如何使用它（理想情况下，我不必自己实现它）。你知道吗

Answer 1

我想到了以下几点：

这将报告得分最高的项及其得分与邻近项的得分之和。一旦使用了邻居，就不会单独报告。你知道吗

我建议使用有利点树作为度量指标。你知道吗

算法如下所示：

1. 从字符串及其分数构造度量索引
2. 从字符串及其分数构造最大堆
3. 对于最大堆中得分最高的字符串：
4. 使用度量索引查找邻近字符串
5. 打印字符串及其分数和相邻字符串的总和
6. 从度量索引中删除字符串和每个near-by字符串
7. 从max堆中移除字符串和每个near-by字符串
8. 重复3-7，直到最大堆为空

也许这可以通过使用一个旧表而不是删除任何内容来简化。度量空间索引不需要高效删除，max堆也不需要支持按值删除。但如果社区规模大且经常重叠，这将是一个缓慢的过程。因此，有效的删除可能是一个必要的困难。你知道吗

1. 从字符串及其分数构造度量索引
2. 从字符串及其分数构造最大堆
3. 从空集构造已用表
4. 对于最大堆中得分最高的字符串：
5. 如果这个字符串在used表中：从下一个字符串开始
6. 使用度量索引查找邻近字符串
7. 删除已用表中的任何邻近字符串
8. 打印字符串及其分数和相邻字符串的总和
9. 将near-by字符串添加到used表中
10. 重复4-9直到最大堆为空

我无法提供复杂性分析。你知道吗

我在考虑第二种算法。我觉得比较慢的部分是把邻居和用过的桌子核对一下。这是不需要的，因为从有利点树删除可以在线性时间内完成。搜索邻居时，记住他们是在哪里找到的，然后使用这些位置删除他们。如果某个邻居被用作有利位置，则将其标记为已移除，以便搜索不会返回它，而是将其留在别处。我认为这使它恢复到二次以下。否则的话，它的数量会是邻里面积的几倍。你知道吗

---

回应评论。问题是“计数较低的字符串会被折叠成计数较高的字符串”，因此这会计算出这个值。这不是一个贪婪的近似，可能会导致非最佳的结果，因为没有什么可以最大化或最小化。这是一个精确的算法。它返回得分最高的项与其邻域的得分之和。你知道吗

这可以看作是给每个邻里分配一个领导，这样每个项目最多有一个领导，而这个领导的总分是迄今为止最大的。这可以看作是一个有向图。你知道吗

该规范不适用于动态规划或优化问题。为此，你会要求与最高的总得分最高的邻居得分最高的项目。也可以用类似的方法解决这个问题，方法是将排序函数字符串从它的分数改为它的分数和它的邻域的和，以及它的分数。你知道吗

这确实意味着它不能用分数上的最大堆来解决，因为删除项目会影响邻域的邻居，在再次找到总分数最高的邻域之前，必须重新计算他们的邻域分数。你知道吗