SIEVE: A Space-Efficient Algorithm for Viterbi Decoding

Can we get speech recognition tools to work on limited-memory devices? The Viterbi algorithm is a classic dynamic programming (DP) solution used to find the most likely sequence of hidden states in a Hidden Markov Model (HMM). While the algorithm finds universal application ranging from communication systems to speech recognition to bioinformatics, its scalability has been scarcely addressed, stranding it to a space complexity that grows with the number of observations. In this paper, we propose SIEVE (pace Efficient Viterbi), a reformulation of the Viterbi algorithm that eliminates its space-complexity dependence on the number of observations to be explained. SIEVE discards and recomputes parts of the DP solution for the sake of space efficiency, in divide-and-conquer fashion, without incurring a time-complexity overhead. Our thorough experimental evaluation shows that SIEVE is highly effective in reducing the memory usage compared to the classic Viterbi algorithm, while avoiding the runtime overhead of a naive space-efficient solution.

Automated summary

This paper presents an algorithm called SIEVE, which is an improvement on the Viterbi algorithm to address the issue of its space complexity growing with the number of observations. SIEVE improves space efficiency by discarding and recomputing parts of the DP solution, without incurring a time complexity overhead.