Second International Conference on Spoken Language Processing (ICSLP'92)
Banff, Alberta, Canada
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.
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.