Arithmetic encoding is usually more space-efficient than Huffman encoding, but it's not used frequently because it has much higher computational complexity for

Arithmetic encoding is usually more space-efficient than Huffman encoding, but it's not used frequently because it has much higher computational complexity for very small gain. However, if you are looking for the most space-efficient representation, it's worth taking a look at. http://en.wikipedia.org/wiki/Arithmetic_encoding http://en.wikipedia.org/wiki/Arithmetic_encoding Arithmetic compression differs from Huffman encoding because it encodes the entire dataset as a whole, rather than symbol-by-symbol. At worst, it will provide the same encoding that Huffman does, and it has far better performance on degenerate cases (such as 1 symbol having 75% chance). I think the commonly cited statistic is about 5% better on average, for some definition of 'average.' For the curious: Arithmetic encoding works by taking all possible sequences, and taking the closed interval from 0 to 1 and chopping it into pieces, where the size of each piece is the probability of the corresponding sequence. Then the encoding of a sequence is the decimal (well, binary) expansion of any number that falls within the corresponding interval.