0

我正在尝试使用 Viterbi min-sum 算法，该算法试图找到通过一堆节点的路径，以最小化针对某些固定输入的整体汉明距离（“异或两个数字并计算结果位”的花哨术语）。

我了解如何使用 DP 来计算整体最小距离，但我无法使用它来捕获与最小距离相对应的相应路径。

似乎在每个节点上记住路径确实会占用大量内存。是否有处理此类问题的标准方法？

编辑：

http://i.imgur.com/EugiEWG.jpg

这是我正在谈论的示例格子。一般的想法是找到通过网格的路径，该路径最接近地模拟输入位串，并且误差最小（通过最小化整体汉明距离或不匹配位的数量来测量）。

如您所见，我输入字符串的第一个块是 01，我可以在格子的第 1 列中遍历那里。下一个块是 10，我可以在第 2 列中移动到那里。下一个块是 11。到目前为止还不错。Next chunk 是 10，这是一个问题，因为我无法从现在的位置达到那个状态，所以我必须去下一个最好的东西（00），其余的可以很好地填充。

但这可能会变得更加复杂。我需要能够以某种方式获得最小汉明距离的相应路径。

（这个练习的重点是格子表示什么是实际有效的转换，而输入字符串是您通过电信收到的，可能会出现乱码并且到处都有不正确的位。这个程序试图找出输入字符串应该通过最小化错误）。

4

2 回答 2

1

您是正确的，计算路径的直接方法是空间昂贵。

这个问题经常出现在成本高昂的DNA 测序中。有很多方法可以克服它（在此处查看更多信息）：

  • 如果您愿意将执行时间加倍，则最多可以减少空间的平方根（请参阅上面链接中的 2.1.1）。

  • 使用压缩树，您可以对数减少其中一个维度（请参阅上面链接中的 2.1.2）。

于 2015-07-16T15:47:23.347 回答
1

有通常的“向后跟踪”技术，只需要值表（但需要整个值表，不要欺骗“只保留最近的部分”）。算法很简单：从最后开始，决定你来自哪条路。你可以做出这个决定，因为要么只有一种方法，如果你来自它，你会计算出与存储的值匹配的值，或者有几个结果是相同的值，你选择哪一个都没有关系。

还存储一个“反向指针”表并不占用太多空间（大约与权重表一样多，但如果这样做，您实际上可以省略大部分权重表），这样做可以让您有一个更简单的向后阶段：只需按照指针。那确实是路径，只是向后存储。

于 2015-07-16T15:31:57.427 回答