Tradeoff Between Speed and Memory Requirements for Decoding of Prefix-Free Codes

For the decoding of prefix-free codes such as Huffman code, we present a tradeoff between the decoding speed and memory requirements that results in an adapted decoding algorithm. Our decoding experiments on different codes demonstrate that the Pareto front of non-dominated solutions from different parameters comprises known solutions and solutions from our adapted algorithm. Each Pareto front comprises five solutions from our adapted algorithm next to five known solutions with a single table and one known solution with all possible tables. Compared to the fastest known solution with all possible tables, our adapted algorithm can achieve only 3.8% runtime overhead with only 66% of the memory requirements. Compared to a known solution with only one table, our adapted algorithm achieves up to 10% runtime improvement with three tables instead of one table. We conclude that our algorithm gives developers more and better choices to balance decoding speed and memory requirements.