COMPUTATIONAL-COMPLEXITY OF A FAST VITERBI DECODING ALGORITHM FOR STOCHASTIC LETTER-PHONEME TRANSDUCTION

This paper describes a modification to, and a fast implementation of, the Viterbi algorithm for use in stochastic letter-to-phoneme conversi on. A straightforward (but unrealistic) implementation of the Viterbi algorithm has a linear time complexity with respect to the length of t he letter string, but quadratic complexity if we additionally consider the number of letter-to-phoneme correspondences to be a variable dete rmining the problem size. Since the number of correspondences can be l arge, processing time is long. If the correspondences are precompiled to a deterministic finite-state automaton to simplify the process of m atching to determine state survivors, execution time is reduced by a l arge multiplicative factor. Speed-up is inferred indirectly since the straightforward implementation of Viterbi decoding is too slow for pra ctical comparison, and ranges between about 200 and 4000 depending upo n the number of letters processed and the particular correspondences e mployed in the transduction. Space complexity is increased linearly wi th respect to the number of states of the automaton. This work has imp lications for fast, efficient implementation of a variety of speech an d language engineering systems.