ASR笔记：几大常见搜索算法的优劣对比

ASR 搜索算法对比：Viterbi, Greedy, Beam Search

在 ASR 解码时，模型每一步都会给出一堆候选词的概率。搜索算法的任务就是：在这些概率组合成的“迷宫”里（WFST），找到那条总概率最大的路径。

1. Greedy Search (贪心搜索)

核心思想： 活在当下。每一步都只选当前概率最大的那个词，一直到最后。

• 优点：极快。计算量最小，复杂度 $O(L)$。
• 缺点：容易翻车。因为每一步只看局部最优，很可能错过全局最优。
• 适用场景：模型本身非常强，或者对速度要求极高、对精度要求不那么严苛的实时场景。

2. Viterbi Search (维特比搜索)

核心思想： 追求完美。利用动态规划，在每一步都记录到达每个状态的最佳路径。

• 优点：全局最优。它能保证找到概率最大的那条路径，绝不漏掉。
• 缺点：太慢了。如果词汇表 $V$ 很大，每一步都要计算所有状态的组合，复杂度 $O(L \cdot V^2)$。
• 适用场景：状态空间很小的情况（比如传统的 HMM 音素识别），或者需要绝对精确解的离线任务。

3. Beam Search (集束搜索)

核心思想： 实用主义。它是 Greedy 和 Viterbi 的折衷。每一步保留概率最高的 $B$ 个候选（Beam Width），把剩下的剪掉。

• 优点：性价比最高。通过调整 $B$，可以自由控制速度和精度的平衡。$B=1$ 就是 Greedy，$B=V$ 就是 Viterbi。
• 缺点：非全局最优。虽然比 Greedy 好得多，但还是有概率在早期把“潜力股”剪掉。
• 适用场景：工业界 ASR 的事实标准。无论是端到端模型还是传统模型，解码基本都用它。

综合对比表

特性	Greedy Search	Viterbi Search	Beam Search
搜索范围	局部最优	全局最优	启发式局部最优
计算速度	极快	极慢	中等（可控）
内存消耗	极低	极高	中等（取决于 $B$）
结果质量	一般	最好	较好
复杂度	$O(L)$	$O(L \cdot V^2)$	$O(L \cdot B \cdot V)$
ASR 地位	快速基线	理论标杆（少用）	绝对主流