Results 1 to 4 of 4

Thread: Tree-less Huffman

  1. #1
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    154
    Thanks
    20
    Thanked 66 Times in 37 Posts

    Tree-less Huffman

    http://robertsouthee.github.io/c++/a...hout-tree.html

    I came across this earlier and haven't heard of anything like this before. There's included source code to test it out.

  2. #2
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    856
    Thanks
    447
    Thanked 254 Times in 103 Posts
    The title is a bit misleading.
    The fact that the tree is stored into a table does not make it a non-tree.
    It's just a more efficient way to store it.

    Also, this method is well known, I'm using it to build Huffman trees since, forever.
    (you can check the open source code of huff0 on github).
    Bulat's tornado does the same, and likely most high-speed huffman implementations out there.

    Good point : the article describes the process pretty well, it's a good read for whoever wants to code its own huffman codec.

  3. #3
    Member
    Join Date
    Mar 2015
    Location
    Germany
    Posts
    57
    Thanks
    34
    Thanked 38 Times in 15 Posts
    "In-Place Calculation of Minimum-RedundancyCodes" Alistair Moffat, Jyrki Katajainen
    Is this paper as well-known as I think ? It's the way I calculate my huffman trees / code length.

  4. #4
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    The code linked from the OP seems to store both leaves and internal nodes, which you don't need to do. The Moffat paper posted by Cristoph Diegelmann describes how you can calculate the codes while storing only the internal nodes explicitly (and do it all in-place). My post here refines Moffat's algorithm a bit more. (I haven't subjected that code to tremendous testing; no one else has claimed to have either broken it or used it successfully. Feedback, good or bad, is welcome.)

Similar Threads

  1. Tree alpha v0.1 download
    By Kennon Conrad in forum Data Compression
    Replies: 848
    Last Post: 7th November 2018, 01:43
  2. Suffix tree transformation?
    By Kennon Conrad in forum Data Compression
    Replies: 92
    Last Post: 11th May 2015, 10:48
  3. Huffman tree, Autumn leaves and Winter cut-back
    By caveman in forum Data Compression
    Replies: 5
    Last Post: 10th January 2014, 09:22
  4. Suffix Tree's internal representation
    By Piotr Tarsa in forum Data Compression
    Replies: 4
    Last Post: 18th December 2011, 08:37
  5. lzma's binary tree matchfinder
    By Shelwien in forum Data Compression
    Replies: 7
    Last Post: 13th October 2011, 08:38

Posting Permissions

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