algorithm - 线性时间的维特比算法

Question

我有一个问题，给定一个隐马尔可夫模型和状态 S，我需要找到一个算法，该算法在时间 O(|S|) 中针对给定的序列 X 返回通过隐马尔可夫模型的最可能路径。

我正在考虑开发一个图，在其中我将在 X 中的不同位置拥有所有不同的状态，并在此图上运行最短路径算法。但是我将有 n|S|^2 条边(其中 n 是 X 中的状态数)和 n|S|顶点。

我发现的最佳算法是运行时间为 O(|E|+|V|) 的非循环最短路径，在我的例子中为 O(|S|^2)。有没有我可以开发的算法让它及时运行 O(|S|)？我只需要总体思路。

谢谢

Answer 1

我认为如果你想检索最有可能的精确序列，你不能在所有情况下都在线性时间内完成。但是，如果您的符号空间是离散的，则平均案例时间复杂度可能会降低。查看 Ukkonen 对计算编辑距离的优化及其 generalizations .另请查看 compression based techniques这也是基于 Ukkonen 的工作。