tag:blogger.com,1999:blog-834134852788085492.post8686401236236479944..comments2024-03-02T07:59:30.808+01:00Comments on RealTime Data Compression: Huffman revisited - Part 3 - Depth limited treeCyanhttp://www.blogger.com/profile/02905407922640810117noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-834134852788085492.post-83150298962403603532015-08-02T00:20:40.255+02:002015-08-02T00:20:40.255+02:00That's a really good question. Unfortunately, ...That's a really good question. Unfortunately, I did made such measurement : it would have required to create a dummy "trivial heuristic" algorithm just to be compared to.<br /><br />I therefore approached the problem from another angle :<br />the proposed method above can only provide a better final compression than "naive flattening", although in most circumstances, the gain is going to be very small. So what matters is that the above technique should cost very little CPU time.<br /><br />I therefore compared the timing of creating a length-limited tree with just creating an "unbound" tree, i.e. without the function HUF_setMaxHeight(). I could measure that the cost of HUF_setMaxHeight() was approximately 5% of the total cost of HUF_buildCTable(). Consider that HUF_buildCTable() contribution to the total compression cost is approximately 3% when associated with block sizes of 32 KB. It makes the total contribution of HUF_setMaxHeight() about 0.15%, hence insignificant.<br /><br />This was enough for my liking.<br />Note that even a "trivial heuristic" would have a cost > 0, so in a comparison exercise, the difference would be even smaller.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-18044630005279263862015-07-30T22:22:05.157+02:002015-07-30T22:22:05.157+02:00You said that the final compression ratio is unaff...You said that the final compression ratio is unaffected compared to the unconstrained-depth version, but how does it compare to the naive heuristic? Does the finer-grained heuristic actually make a difference?gaschehttps://www.blogger.com/profile/08857543004921424187noreply@blogger.com