5th International Conference on Spoken Language Processing

Sydney, Australia
November 30 - December 4, 1998

The BBN Single-Phonetic-Tree Fast-Match Algorithm

Long Nguyen, Richard Schwartz

BBN Technologies, GTE Internetworking, USA

In January 1993, BBN demonstrated for the first time a real-time, 20K-word, speaker-independent, continuous speech recognition system, implemented in software on an off-the-shelf workstation. The key to the real-time system was a novel, proprietary fast-match algorithm which had two important properties: high-accuracy recognition and run-time proportional to only the cube root of the vocabulary size. This paper describes that fast-match algorithm in detail. While a number of fast-match algorithms have been published, the BBN algorithm continues to have novel features that have not appeared in the literature. In this fast-match, the vocabulary is organized as a phonetic tree. The last phonemes of the words always locate at the leaves. Each node of the phonetic tree is assigned a set id representing a group of words which share this node. The acoustic models associated with the nodes are the composite triphones where there could be more than one right context. The language models used in this fast-match are the Pr(set_of_words|some_word) which are evaluated at every node of the words during the search. The search itself is similar to the usual beam search with one addition: To activate a node, we temporarily use some set bigrams; to leave that node, we take out that temporary bigram.

Full Paper

Bibliographic reference.  Nguyen, Long / Schwartz, Richard (1998): "The BBN single-phonetic-tree fast-match algorithm", In ICSLP-1998, paper 1028.