Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sub-linear decoding of Huffman codes almost in-place
Luleå tekniska universitet.
1998 (English)In: Preprint, IMFM , 1998Conference paper, Published 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.
Series
Technical Report IMFM, 36/600
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-40201Local ID: f3b3d300-11ee-11dd-ada4-000ea68e967bOAI: oai:DiVA.org:ltu-40201DiVA: diva2:1013724
Conference
DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches : 05/10/1998 - 07/10/1998
Note
Godkänd; 1998; 20080424 (cira)Available from: 2016-10-03 Created: 2016-10-03Bibliographically approved

Open Access in DiVA

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

Other links

http://dimacs.rutgers.edu/Workshops/Codes/

Search in DiVA

By author/editor
Brodnik, Andrej
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 13 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

Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf