How Range Encoding Works
Range encoding conceptually encodes all the symbols of the message into one number, unlike Huffman coding which assigns each symbol a bit-pattern and concatenates all the bit-patterns together. Thus range encoding can achieve greater compression ratios than the one-bit-per-symbol lower bound on Huffman encoding and it does not suffer the inefficiencies that Huffman does when dealing with probabilities that are not exact powers of two.
The central concept behind range encoding is this: given a large-enough range of integers, and a probability estimation for the symbols, the initial range can easily be divided into sub-ranges whose sizes are proportional to the probability of the symbol they represent. Each symbol of the message can then be encoded in turn, by reducing the current range down to just that sub-range which corresponds to the next symbol to be encoded. The decoder must have the same probability estimation the encoder used, which can either be sent in advance, derived from already transferred data or be part of the compressor and decompressor.
When all symbols have been encoded, merely identifying the sub-range is enough to communicate the entire message (presuming of course that the decoder is somehow notified when it has extracted the entire message). A single integer is actually sufficient to identify the sub-range, and it may not even be necessary to transmit the entire integer; if there is a sequence of digits such that every integer beginning with that prefix falls within the sub-range, then the prefix alone is all that's needed to identify the sub-range and thus transmit the message.
Read more about this topic: Range Encoding
Famous quotes containing the words range and/or works:
“The Canadians of those days, at least, possessed a roving spirit of adventure which carried them further, in exposure to hardship and danger, than ever the New England colonist went, and led them, though not to clear and colonize the wilderness, yet to range over it as coureurs de bois, or runners of the woods, or, as Hontan prefers to call them, coureurs de risques, runners of risks; to say nothing of their enterprising priesthood.”
—Henry David Thoreau (1817–1862)
“Only the more uncompromising of the mystics still seek for knowledge in a silent land of absolute intuition, where the intellect finally lays down its conceptual tools, and rests from its pragmatic labors, while its works do not follow it, but are simply forgotten, and are as if they never had been.”
—Josiah Royce (1855–1916)