## 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.