  We improve the runtime of the linear compression scheme for hidden Markov
sources presented in a 2018 paper of Guruswami, Nakkiran, and Sudan. Under the
previous scheme, compressing a message of length $n$ takes $O(n \log n)$
runtime, and decompressing takes $O(n^{1 + \delta})$ runtime for any fixed
$\delta > 0.$ We present how to improve the runtime of the decoding scheme to
$O(n \log n)$ by caching intermediate results to avoid repeating computation.
