我已经为一个基于隐马尔可夫模型（HMM）的信号实现了一个简单的维特比算法。解码器的执行时间似乎对于我的需求来说太慢了。我现在正在尝试理解如何加速执行。当我试图确定算法的计算复杂度时，我看到它被提到具有t * s^2的复杂度，其中t是观测次数，s是状态数。我大约有3500个状态和100个观测。每个状态有729个发射概率。
我还看到在这篇论文中提到，维特比解码在这个论文中是指数级的（2^k，其中k是约束长度）。我对这个解释不太理解。但是，我认为如果维特比算法对于状态是指数级的，那么即使我将其并行化，算法也会非常慢。
我的问题是：
- 维特比算法/解码的复杂度是什么？在两种情况下它们相同吗？
- 我如何修改维特比算法来加速它？
编辑：我正在用C++实现它，希望将来能修改并并行化它。
回答：
回答第一个问题：
如果你有t个观测，s个状态，每个状态有e个发射概率，那么网格图将有t*s个节点，评估每个节点将花费e次操作，因此一个简单实现的总体复杂度将是O(t*s*e)。
维特比解码可以用来解码比特序列。如果观测依赖于前k个二进制比特，那么k个比特的不同序列数是2^k。这代表了你需要进行流解码的状态数（每个状态代表前比特的一种配置）。然而，这不太可能与你相关。
你链接的论文描述了一种减少需要扩展的节点数量的方法。这不会改善最坏情况下的复杂度，但根据你具体问题的性质，可能会在典型使用中带来显著的改进。
