An Advancement in Huffman Coding With a Potential for Parallel Decoding

ABSTRACT With examples we provide a minimum theory framework to understand data compression of text files—using Huffman coding—that will also provide a framework in designing experiments involving encoding/decoding. We propose a parallelizable heuristic for the naïve Huffman encoding and decoding which addresses the difficulty in parallelizing the inherently sequential Huffman decoding. While the proposal is amenable to a design of an efficient parallel algorithm for Huffman decoding, it also achieves a better compression ratio in the sense that the fraction of inputs for it works is over 0.83. The results of simulations of the parallel algorithm on a 64‐core machine show that the proposed parallel modified Huffman encoding and decoding results in a faster algorithm when compared to the naïve Huffman scheme and the sequential version of the heuristic proposed. Further, the parallel implementation of the proposed encoding and decoding schemes resulted in a mean speed‐up of and respectively over the naïve Huffman encoding and decoding when processing an input of size on a multi‐core processor with cores.