Skip to main content ↑ ↓

Notice

Please note that most of the software linked on this forum is likely to be safe to use. If you are unsure, feel free to ask in the relevant topics, or send a private message to an administrator or moderator. To help curb the problems of false positives, or in the event that you do find actual malware, you can contribute through the article linked here.
Topic: LBE possible replacement for Huffman encoding? (Read 3113 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

LBE possible replacement for Huffman encoding?

Just wondering if this has been tried in AV compression and if it has any practical application for current projects.  The main and obvious advantage of LBE is the sheer speed. LBE can immediately generate the codes for characters without being given the file to be compressed. This is in sharp contrast with Huffman in which a binary tree has to be constructed every time a new file is to be compressed:

LBE

LBE possible replacement for Huffman encoding?

Reply #1 –
Almost all huffman based compressors use dynamic-huffman algorithms which modify the tree as characters are encoutered, so that's not really an issue. Huffman is also well understood and close to optimal.

The optimal statistical compressors use variations on "arithmetic encoding" but that algorithm is slow and patent-encumbered.
 

LBE possible replacement for Huffman encoding?

Reply #2 –
Adaptive huffman can be close to optimal for stationary signals (as long as probabilities dont get get too large). For non stationary signals you are better off with Golomb-Rice codes, which is a set of very easy to encode Huffman codes, if your distribution is close to a geometric/exponential distribution (usually the case with predictive coders). They can adapt far faster than an adaptive huffman based approach (because they can make a guess at the global distribution based on a small set of samples, whereas adaptive huffman can only determine the individual probabilities of symbols based on their individual frequencies ... which will need a far larger history to be accurate).


LBE is a little like the Golomb-Rice codes, in that it is only optimal for certain distributions (after reordering according to frequency in the case of LBE). Unlike Golomb-Rice coding it only has speed as it's single upside though, it always compresses worse than huffman codes. The small speed advantage in encoding compared to huffman isnt worth the loss of optimality IMO.