Results 1 to 6 of 6

Thread: Fast Huffman implementation

  1. #1
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 1 Time in 1 Post

    Fast Huffman implementation

    I am looking for fast C++ implementation of static/adaptive Huffman coder. What is a state of art implementation, now?
    Enjoy coding, enjoy life!

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    you can start by reading one in tornado (since it should be easier to decipher), but i believe that the best one is in 7-zip sources. it also has less restrictive license

  3. #3
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    How do they compare to FastHF

  4. #4
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    FastHF has bit-by-bit decoding and heap sort, so it's pretty slow

  5. #5
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    No idea how well it compares, but try: http://entropyware.info/shcodec/index.html.

    Good luck!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  6. #6
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    437
    Thanks
    137
    Thanked 152 Times in 100 Posts
    I have some aging code in libstaden-read (aka io_lib): http://staden.svn.sourceforge.net/vi...30&view=markup

    I won't claim it's super and it's a bit of a mess as it's mixed up with all sorts of other bits and bobs, but it's BSD licence so feel free to experiment and slice/dice if you wish. It implements an interlaced version of deflate, but minus the LZ bit (as for that particular purpose it didn't help at all). The decoder is reasonably fast once it gets going, but has some decoding setup time so it's not great on very small blocks. I decode a nibble at a time for speed, using a lookup table to work out how many symbol to emit (if any) and which new state to jump to for the next lookup table.

    From what I recall it was slightly faster than zlib at decoding and slightly slower at encoding, but I may have got that back to front - it's been a few years.

    James

    PS. The interlacing is basically an efficient way to handle data reordering without needing to copy it to separate buffers. I was using this for packing multi-dimensional arrays of N x 4 x 16-bit quantaties. It turns out that you can get a long way with just treating it as 8 separate streams, eg producing a buffer for byte 0, 8, 16, 24, ..., another for 1, 9, 17, 24, etc. However instead I just fed the one buffer into this code with a step/stride of 8 and let it interlace as it goes. Not an optimal strategy, but fast and not miles off optimal given the specific nature of that data.

Similar Threads

  1. Huffman on GPU
    By Bulat Ziganshin in forum Data Compression
    Replies: 9
    Last Post: 23rd December 2017, 05:30
  2. Huffman code generator
    By Shelwien in forum Data Compression
    Replies: 2
    Last Post: 24th May 2011, 02:50
  3. I'm looking for the best free implementation of deflate
    By caveman in forum Data Compression
    Replies: 2
    Last Post: 22nd November 2010, 09:27
  4. Move-to-Front Implementation
    By Cyan in forum Data Compression
    Replies: 34
    Last Post: 8th August 2010, 01:11
  5. huffman's Coding
    By swapy in forum Data Compression
    Replies: 5
    Last Post: 12th August 2009, 22:51

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •