Change search
ReferencesLink to record
Permanent link

Direct link
Sub-linear decoding of Huffman codes almost in-place
Luleå tekniska universitet.
1998 (English)In: Preprint, IMFM , 1998Conference paper (Refereed)
Abstract [en]

We present a succinct data structure storing the Huffman encoding that permits sublinear decoding in the number of transmitted bits. The size of the extra storage except for the storage of the symbols in the alphabet for the new data structure is O(l log N) bits, where l is the longest Huffman code and N is the number of symbols in the alphabet. We present a solution that typically decodes texts of sizes ranging from a few hundreds up to 68 000 with only one third to one fifth of the number of memory accesses of that of regular Huffman implementations. In our solution, the overhead structure where we do all but one memory access to, is never more than 342 bytes. This will with a very high probability reside in cache, which means that the actual decoding time compares even better

Place, publisher, year, edition, pages
IMFM , 1998.
, Technical Report IMFM, 36/600
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-40201Local ID: f3b3d300-11ee-11dd-ada4-000ea68e967bOAI: diva2:1013724
DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches : 05/10/1998 - 07/10/1998
Godkänd; 1998; 20080424 (cira)Available from: 2016-10-03 Created: 2016-10-03Bibliographically approved

Open Access in DiVA

fulltext(236 kB)6 downloads
File information
File name FULLTEXT01.pdfFile size 236 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Search in DiVA

By author/editor
Brodnik, Andrej

Search outside of DiVA

GoogleGoogle Scholar
Total: 6 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link