Memory and Time Improvements in a Dynamic Programming Algorithm for Matching Speech Patterns

Recently, dynamic programming has been found useful for performing nonlinear time warping in speech recognition. Although considerably faster than exhaustive search procedures, the dynamic programming procedure nevertheless requires substantial computation. Also, considerable storage is normally required for reference prototypes necessary in the matching process. This paper is concerned with methods for reducing this storage and computation. Empirical results indicate that one method yields 50 to 60 percent storage reduction and a factor of 4 to 6 in computational savings relative to conventional dynamic programming procedures without degradation in recognition accuracy. © 1978 IEEE