Enhanced Direct Access to Huffman Encoded Files

摘要

Given a file T, and the Huffman encoding of its elements, we present a data structure that enables direct access to the i-th element of T by reordering the bits of the compressed file and using some additional space. When compared to a Wavelet tree for Huffman Codes, our different reordering of the bits requires less additional storage overhead by reducing the need for auxiliary rank structures, while improving processing time for extracting the ith element of T.