我已经为我观察到的基于hmm的信号实现了一个朴素的viterbi算法。解码器的执行时间似乎太慢，无法满足我的要求。我现在想知道如何加快执行速度当我要确定算法的计算复杂度时，我看到它被称为具有复杂性的t * s^2，其中T是观测的数目，S是状态的数目。我大概有3500个州，100个观察点每个州有729个排放概率。
我也看到在这篇文章中提到，维特比译码是指数的（2^k，其中k是约束长度）我不太明白这个解释。但是，我相信如果维特比是关于状态的指数，那么算法肯定会非常慢，即使我把它并行化。
我的问题是：
维特比算法/解码的复杂性是什么？在这两种情况下它们是相同的吗？
如何修改Viterbi算法以加快速度？
编辑：我在C++中实现它，希望将来能对它进行修改和并行化。
最佳答案
回答第一个问题：
如果你有观测值，S状态，每个状态都具有发射概率，那么网格将具有t*s节点，并且评估每个节点将花费E操作，所以天真实现的总体复杂性将是O(t*s*e)。
维特比译码可用于比特序列的译码。如果观测值依赖于先前的k个二进制位，则k个位的不同序列的数目为2^k。这表示需要进行流解码的状态的数目（每个状态表示先前位的一个配置）。不过，这与你无关。
您链接到的文章描述了一种减少需要扩展的节点数的方法这不会改善最坏情况的复杂性，但根据具体问题的性质，可以很好地改善典型使用。
关于algorithm - 加快维特比执行速度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30741167/