ASR3:字典树

如果我们要计算一个单词(比如abc)分别与at,ask,ash的编辑距离,那么按照指前提到的方法要计算三次,但是这三个单词有很多相同的地方,比如三个单词第一个字母都是a,ask与ash前两个字母都是as,如果使用字典树(Lexical Tree),能大大降低时间复杂度。

字典树本质就是减少重复计算,实现起来也比较简单,只需要在做搜索时加入新的路径就可以,如图所示:

原来计算编辑距离时只能向下一个字符延伸,比如ash从a只能延伸到s,但现在用字典树a能延伸到s和t,字典树延伸了下一个字符的范围,字典树主要思想就是这样,实现也挺简单,用python的dict很容易实现:树的每个节点用dict表示,它的元素是它的子节点,也用dict表示。语音识别时间复杂度很高,所以要在各个地方尽量减少复杂度。

lufo /
Published under (CC) BY-NC-SA tagged with speech_recognition