Acoustic pattern matching and beam searching

Dynamic programming (DP) has become a popular means of performing the necessary time warping in isolated word recognition. DP offers the advantage of always finding the optimal fit of a known reference pattern against an unknown input utterance. Unfortunately, DP has two major disadvantages: 1) The amount of data needed to store the known reference patterns can be very large and 2) the computation needed to do the full DP search is intensive. Because of these problems, DP has not yet become feasible for commercial low cost speaker dependent isolated word recognition systems. We present two means of reducing both the storage requirements and the computation needed for the DP search: 1) a segmentation scheme for the reduction of data (and thereby computation) which typically reduces the speech data by a factor of between 3 and 4 and 2) a modification of the Beam search used by the Harpy speech recognition system which provides a substantial speedup over conventional DP. Together, computation is reduced by an order of magnitude.