Computational complexity of a fast viterbi decoding algorithm for stochastic letter-phoneme transduction

Wing Pong Robert Luk, Robert I. Damper

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


This paper describes a modification to, and a fast implementation of, the Viterbi algorithm for use in stochastic letter-to-phoneme conversion. A straightforward (but unrealistic) implementation of the Viterbi algorithm has a linear time complexity with respect to the length of the letter string, but quadratic complexity if we additionally consider the number of letterto-phoneme correspondences to be a variable determining the problem size. Since the number of correspondences can be large, processing time is long. If the correspondences are precompiled to a deterministic finite-state automaton to simplify the process of matching to determine state survivors, execution time is reduced by a large multiplicative factor. Speed-up is inferred indirectly since the straightforward implementation of Viterbi decoding is too slow for practical comparison, and ranges between about 200 and 4000 depending upon the number of letters processed and the particular correspondences employed in the transduction. Space complexity is increased linearly with respect to the number of states of the automaton. This work has implications for fast, efficient implementation of a variety of speech and language engineering systems.
Original languageEnglish
Pages (from-to)217-225
Number of pages9
JournalIEEE Transactions on Speech and Audio Processing
Issue number3
Publication statusPublished - 1 Dec 1998


  • Finite-state automata
  • Letter-to-phoneme conversion
  • Stochastic transduction
  • Viterbi algorithm

ASJC Scopus subject areas

  • Acoustics and Ultrasonics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Computational complexity of a fast viterbi decoding algorithm for stochastic letter-phoneme transduction'. Together they form a unique fingerprint.

Cite this