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