Fast prefix code processing

As large main memory becomes more and more available at reasonable prices, processing speed of large data sets becomes more important than reducing main memory usage of internal data structures which are small compared to the available main memory capacity. In this paper we describe the use of a finite state machine for fast processing of prefix codes that significantly improves decoding performance in practice, and that is easy to implement. We present an intuitive explanation of this method, an extension to discover symbol boundaries in compressed data, implementation details, and we also provide experimental performance results.