线性时间内的Viterbi算法

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的工作。