Efficient algorithms for decode efficient prefix codes

摘要

The cost of decompressing (decoding) data can be prohibitive for certain real-time applications. In many scenarios, it is acceptable to sacrifice (to some extent) on compression in the interest of fast decoding. We study anovel problem of finding a prefix tree having the best decode time under the constraint that the code length does not exceed a certain threshold for a natural class of memory access cost functions that use blocking (also referred to as lookup tables). We present exact and approximation algorithms for this problem that are based on dynamic programming and capitalize on interesting structures of the optimal solutions. The full version of this paper is available at [1]