搜索算法概览

解码器的任务是找到与输入音频 ($O$) 最匹配的单个词序列 ($W$)。它通过结合声学模型得分 $P(O|W)$ 和语言模型得分 $P(W)$ 来完成此任务。难题在于可能的词序列数量庞大到难以想象。一段十秒长的音频片段可能对应数百万甚至数十亿个潜在句子。

检查每一种可能性（这种方法被称为“暴力搜索”）在计算上是不可行的。如果你的词汇量是 20,000 个词，那么可能的五词句子的数量将是 $20,000^5$，这个数字非常大，以至于最快的计算机也无法在合理的时间内检查所有这些组合。解码器需要一种效率高得多的策略。

将搜索问题视为寻路任务

处理这个问题的更好方法是将其重新定义为寻路问题。设想一个大型图，其中每个点代表一个可能跟在前一个词后面的词。解码器的任务是找到通过这个图从起点到终点“成本最低”或“最有可能”的路径。

图中的每条路径都代表一个独特的句子，或者一个“假设”。路径上的每一步都有相关的成本，这个成本根据声学和语言模型概率计算得出。声学模型得分低（意味着声音匹配不佳）或语言模型得分低（意味着词序列不太可能）的路径将很快变得非常“昂贵”。

一个简化的搜索图。解码器检查不同的路径（假设），例如“recognize speech”和“wreck a nice beach”。红色路径表示声学模型和语言模型组合得分最高的路径。

剪除不太可能的假设

搜索算法不盲目地考察所有路径，而是使用一种智能技术，称为剪枝。当解码器逐词构建句子假设时，它会记录这些假设的得分。如果某条路径的可能程度显著低于目前已知的最佳路径，算法就会放弃它。

这是一种“束搜索”的形式，解码器在每一步只保留少数（或“束”）最有希望的假设，并丢弃其余的。通过及早剪除大部分不佳路径，解码器可以将计算资源集中在那些实际有可能正确的假设上。

这个过程使得现代语音识别成为可能。如果没有高效的搜索算法来处理庞大的可能性空间，即使是最好的声学和语言模型也将毫无用处。在下一节中，你将学习维特比算法，这是一种经典且有效的算法，是许多解码器的主要方法。