Prague Stringology Conference 2018
Shmuel Tomi Klein, Elina Opalinsky and Dana Shapira
Synchronizing Dynamic Huffman Codes
| Abstract: |
| Traditional dynamic Huffman algorithms update the frequencies adaptively after every character, according to the assumption that better compression can be achieved when all previous characters are taken into account, justifying the slow processing time. This, however, turns the encoded file into an extremely vulnerable one in the case of even a single bit error. Since the above mentioned assumption is not necessarily true, we explore blockwise dynamic Huffman variants, where the Huffman tree is periodically, rather than constantly, updated. Experiments show that avoiding the updates at every character and choosing larger blocks does not hurt the compression performance, and may even improve it at times. Moreover, the new scheme seems to be more robust against single errors introduced in the encoded file. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |