ZIP: A dynamic programming algorithm for time-aligning two indefinitely long utterances

In automatic speech recognition (ASR) using whole-word templates, dynamic programming (DP) is frequently used to determine the similarity of two patterns (derived from spoken words) using the optimal way of aligning their timescales. In ASR the actual timescale alignment is of secondary interest to the degree of similarity and is not normally computed. We present ZIP, a modified DP algorithm designed to compute the time alignment of two utterances of the same text of any length. By using a window and partial traceback the amount of computation and storage is kept to a modest level, although the optimality of the final path is no longer absolutely guaranteed. Uses of ZIP are given.