Prague Stringology Conference 2015

Shmuel Tomi Klein and Dana Shapira

Enhanced Extraction from Huffman Encoded Files

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

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation