python - 根据给定的汉明距离折叠字符串集

Question

给定一组字符串(第一列)和计数(第二列)，例如:

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

是否有任何算法甚至实现(最好是 Unix 执行程序、R 或 python)可以根据给定的汉明距离将此集合折叠成一个新集合。

• 折叠意味着添加计数
• 计数较低的字符串会折叠为计数较高的字符串。

例如，对于汉明距离 1，上述设置会将第二个字符串 aaab 折叠为 aaaa，因为它们相距 1 个汉明距离，并且 aaaa code> 的计数较高。 折叠的条目将具有组合计数，此处 aaaa 15

对于这个集合，我们将得到以下折叠集合:

aaaa 15
abbb 6
cccc 8

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

更多背景和动机

大多数编程语言都实现了计算 2 个字符串(一对)之间的汉明距离。强力解决方案将计算所有对之间的距离。也许没有办法解决这个问题。然而例如我想一个有效的解决方案将避免计算所有对等的距离。也许有一些聪明的方法可以保存一些基于度量理论的计算(因为汉明距离是一个度量)，例如如果x和z之间的汉明距离是3，并且x和y是3，我可以避免在y和z之间进行计算。也许有一种聪明的 k-mer 方法，或者可能有一些针对恒定距离的有效解决方案(例如 d=1)。

即使只有一个蛮力解决方案，我也很好奇以前是否已经实现过以及如何使用它(理想情况下我不必自己实现)。

Answer 1

我想到了以下内容:

这将报告得分最高的项目及其得分与其附近邻居得分的总和。一旦使用了邻居，就不会单独报告。

我建议使用 Vantage-point 树作为指标索引。

算法如下所示:

1. 根据字符串及其分数构建指标索引
2. 根据字符串及其分数构造最大堆
3. 对于最大堆中得分最高的字符串:
4. 使用指标索引查找附近的字符串
5. 打印字符串，以及它的分数和它附近的字符串的总和
6. 从指标索引中删除该字符串以及每个附近的字符串
7. 从最大堆中删除该字符串以及每个附近的字符串
8. 重复3-7，直到最大堆为空

也许可以通过使用使用过的表而不是删除任何内容来简化此操作。度量空间索引不需要高效删除，最大堆也不需要支持按值删除。但如果邻域很大并且经常重叠，那么速度会更慢。所以高效删除可能是一个必然的难点。

1. 根据字符串及其分数构建指标索引
2. 根据字符串及其分数构造最大堆
3. 从空集构造使用的表
4. 对于最大堆中得分最高的字符串:
5. 如果该字符串在使用的表中:从下一个字符串开始
6. 使用指标索引查找附近的字符串
7. 删除所用表中任何附近的字符串
8. 打印字符串，以及它的分数和它附近的字符串的总和
9. 将附近的字符串添加到使用的表中
10. 重复4-9，直到最大堆为空

我无法提供复杂性分析。

我正在考虑第二种算法。我认为缓慢的部分是根据已用表检查邻居。这是不需要的，因为从有利点树中删除可以在线性时间内完成。搜索邻居时，请记住找到它们的位置，然后使用这些位置将其删除。如果邻居被用作有利位置，请将其标记为已删除，以便搜索不会返回它，否则不要理会它。我认为这将其恢复到二次以下。否则，它将类似于项目数量乘以邻域大小。

<小时/>

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

这可以看作是为每个邻域分配一个领导者，使得每个项目最多有一个领导者，并且该领导者迄今为止具有最大的总得分。这可以看作是有向图。

该规范不适用于动态规划或优化问题。为此，您会要求在总得分最高的邻域中得分最高的项目。也可以通过类似的方式解决这个问题，将排名函数字符串从其得分更改为其得分与其邻域之和及其得分的对。

这确实意味着无法使用分数上的最大堆来解决它，因为删除项目会影响邻域的邻居，并且在再次找到总得分邻域最高的项目之前必须重新计算其邻域分数。