Second International Conference on Spoken Language Processing (ICSLP'92)

Banff, Alberta, Canada
October 13-16, 1992

A Modification of the Viterbi Algorithm for Stochastic Phonographic Transduction

Robert W. P. Luk, Robert I. Damper

Department of Electronics and Computer Science, University of Southampton, Southampton, UK

This paper describes a modification and a fast implementation of the Viterbi algorithm as used in stochastic phonographic transduction. The Viterbi algorithm has a linear time-complexity with respect to the length of the letter string and cubic complexity if we consider the number of letter-phoneme correspondences to be a variable of the problem size. Since the number of correspondences can be large, processing time is long. If the correspondences are pre-compiled to a finite state automaton to simplify the matching process, then the time complexity is reduced by a large multiplicative factor which is determined empirically. The space complexity is increased linearly with respect to the number of states in the automaton.

Full Paper

Bibliographic reference.  Luk, Robert W. P. / Damper, Robert I. (1992): "A modification of the viterbi algorithm for stochastic phonographic transduction", In ICSLP-1992, 855-858.