{"history":[],"article":{"id":"0bbaf8d2-5d2f-4568-bd07-2cfb1b5703ad","title":"Range coding","slug":"range-coding","content":":::summary\n:::\n\n# \n**Range coding** (or **range encoding**) is an [entropy coding](https://bliptext.com/articles/entropy-coding) method defined by G. Nigel N. Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976.\nGiven a stream of symbols and their probabilities, a range coder produces a space-efficient stream of bits to represent these symbols and, given the stream and the probabilities, a range decoder reverses the process.\nRange coding is very similar to [arithmetic coding](https://bliptext.com/articles/arithmetic-coding), except that coding is done with digits in any base, instead of with bits, and so it is faster when using larger bases (e.g. a [byte](https://bliptext.com/articles/byte)) at small cost in compression efficiency.\nAfter the expiration of the first (1978) arithmetic coding patent, range coding appeared to clearly be free of patent encumbrances.\nThis particularly drove interest in the technique in the [open source](https://bliptext.com/articles/open-source) community.\nSince that time, patents on various well-known arithmetic coding techniques have also expired.\n\n# How range coding works\nRange coding conceptually encodes all the symbols of the message into one number, unlike [Huffman coding](https://bliptext.com/articles/huffman-coding) which assigns each symbol a bit-pattern and concatenates all the bit-patterns together.\nThus range coding can achieve greater compression ratios than the one-bit-per-symbol lower bound on Huffman coding and it does not suffer the inefficiencies that Huffman does when dealing with probabilities that are not an exact [power of two](https://bliptext.com/articles/power-of-two).\nThe central concept behind range coding is this: given a large-enough range of [integers](https://bliptext.com/articles/integer), 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.\nEach 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.\nThe 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.\nWhen 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).\nA 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.\n# [Graphical representation of the coding process. The message being encoded here is \"AABA\" | upload.wikimedia.org/wikipedia/commons/2/2b/Range///encoding.jpg]\n\n## Example\nSuppose we want to encode the message \"AABA\", where is the end-of-message symbol.\nFor this example it is assumed that the decoder knows that we intend to encode exactly five symbols in the [base 10 number system](https://bliptext.com/articles/decimal) (allowing for 105 different combinations of symbols with the range [0, 100000) ) using the [probability distribution](https://bliptext.com/articles/probability-distribution) {A: .60; B: .20; : .20}. The encoder breaks down the range [0, 100000) into three subranges:\nA: [ 0, 60000) B: [ 60000, 80000)\n: [ 80000, 100000)\nSince our first symbol is an A, it reduces our initial range down to [0, 60000) . The second symbol choice leaves us with three sub-ranges of this range. We show them following the already-encoded 'A':\nAA: [ 0, 36000) AB: [ 36000, 48000)\nA: [ 48000, 60000)\nWith two symbols encoded, our range is now [0, 36000) and our third symbol leads to the following choices:\nAAA: [ 0, 21600) AAB: [ 21600, 28800)\nAA: [ 28800, 36000)\nThis time it is the second of our three choices that represent the message we want to encode, and our range becomes [21600, 28800) . It may look harder to determine our sub-ranges in this case, but it is actually not: we can merely subtract the lower bound from the upper bound to determine that there are 7200 numbers in our range; that the first 4320 of them represent 0.60 of the total, the next 1440 represent the next 0.20, and the remaining 1440 represent the remaining 0.20 of the total. Adding back the lower bound gives us our ranges:\nAABA: [21600, 25920) AABB: [25920, 27360)\nAAB: [27360, 28800)\nFinally, with our range narrowed down to [21600, 25920), we have just one more symbol to encode. Using the same technique as before for dividing up the range between the lower and upper bound, we find the three sub-ranges are:\nAABAA: [21600, 24192) AABAB: [24192, 25056)\nAABA: [25056, 25920)\nAnd since is our final symbol, our final range is [25056, 25920) . Because all five-digit integers starting with \"251\" fall within our final range, it is one of the three-digit prefixes we could transmit that would unambiguously convey our original message. (The fact that there are actually eight such prefixes in all implies we still have inefficiencies.\nThey have been introduced by our use of [base 10](https://bliptext.com/articles/decimal) rather than [base 2](https://bliptext.com/articles/binary-numeral-system).)\nThe central problem may appear to be selecting an initial range large enough that no matter how many symbols we have to encode, we will always have a current range large enough to divide into non-zero sub-ranges.\nIn practice, however, this is not a problem, because instead of starting with a very large range and gradually narrowing it down, the encoder works with a smaller range of numbers at any given time.\nAfter some number of digits have been encoded, the leftmost digits will not change.\nIn the example after coding just three symbols, we already knew that our final result would start with \"2\".\nMore digits are shifted in on the right as digits on the left are sent off.\nThis is illustrated in the following code:\nTo finish off we may need to emit a few extra digits.\nThe top digit of is probably too small so we need to increment it, but we have to make sure we don't increment it past.\nSo first we need to make sure is large enough.\nOne problem that can occur with the function above is that might become very small but and still have differing first digits.\nThis could result in the interval having insufficient precision to distinguish between all of the symbols in the alphabet.\nWhen this happens we need to fudge a little, output the first couple of digits even though we might be off by one, and re-adjust the range to give us as much room as possible.\nFor example, imagine the input stream has led the encoder to the right-open interval [****59****888, 60188), that is, and . The trick is to narrow down the interval to [****59****888, 60000) = [****59****888, ****59****999], which allows the encoder to emit two of the left-most digits of , and readjust the interval to [88800, 99999] = [88800, 100000), that is, and.\nThe decoder will be following the same steps so it will know when it needs to do this to keep in sync.\nBase 10 was used in this example, but a real implementation would just use binary, with the full range of the native integer data type.\nInstead of and you would likely use hexadecimal constants such as and.\nInstead of emitting a digit at a time you would emit a byte at a time and use a byte-shift operation instead of multiplying by 10.\nDecoding uses exactly the same algorithm with the addition of keeping track of the current value consisting of the digits read from the compressor.\nInstead of emitting the top digit of you just throw it away, but you also shift out the top digit of and shift in a new digit read from the compressor.\nUse below instead of.\nIn order to determine which probability intervals to apply, the decoder needs to look at the current value of within the interval [low, low+range) and decide which symbol this represents.\nFor the AABA example above, this would return a value in the range 0 to 9.\nValues 0 through 5 would represent A, 6 and 7 would represent B, and 8 and 9 would represent .\n\n# Relationship with arithmetic coding\n[Arithmetic coding](https://bliptext.com/articles/arithmetic-coding) is the same as range coding, but with the integers taken as being the numerators of [fractions](https://bliptext.com/articles/fraction-mathematics).\nThese fractions have an implicit, common denominator, such that all the fractions fall in the range [0,1) . Accordingly, the resulting arithmetic code is interpreted as beginning with an implicit \"0\". As these are just different interpretations of the same coding methods, and as the resulting arithmetic and range codes are identical, each arithmetic coder is its corresponding range encoder, and vice versa. In other words, arithmetic coding and range coding are just two, slightly different ways of understanding the same thing.\nIn practice, though, so-called range encoders tend to be implemented pretty much as described in Martin's paper, while arithmetic coders more generally tend not to be called range encoders.\nAn often noted feature of such range encoders is the tendency to perform renormalization a byte at a time, rather than one bit at a time (as is usually the case).\nIn other words, range encoders tend to use bytes as coding digits, rather than bits.\nWhile this does reduce the amount of compression that can be achieved by a very small amount, it is faster than when performing renormalization for each bit.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:35:24.738Z","updated_at":"2025-01-25T17:35:24.738Z","search_vector":"'code':2 'rang':1","search_content":" \n \n\n# \n**Range coding** (or **range encoding**) is an [entropy coding](https://bliptext.com/articles/entropy-coding) method defined by G. Nigel N. Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976.\nGiven a stream of symbols and their probabilities, a range coder produces a space-efficient stream of bits to represent these symbols and, given the stream and the probabilities, a range decoder reverses the process.\nRange coding is very similar to [arithmetic coding](https://bliptext.com/articles/arithmetic-coding), except that coding is done with digits in any base, instead of with bits, and so it is faster when using larger bases (e.g. a [byte](https://bliptext.com/articles/byte)) at small cost in compression efficiency.\nAfter the expiration of the first (1978) arithmetic coding patent, range coding appeared to clearly be free of patent encumbrances.\nThis particularly drove interest in the technique in the [open source](https://bliptext.com/articles/open-source) community.\nSince that time, patents on various well-known arithmetic coding techniques have also expired.\n\n# How range coding works\nRange coding conceptually encodes all the symbols of the message into one number, unlike [Huffman coding](https://bliptext.com/articles/huffman-coding) which assigns each symbol a bit-pattern and concatenates all the bit-patterns together.\nThus range coding can achieve greater compression ratios than the one-bit-per-symbol lower bound on Huffman coding and it does not suffer the inefficiencies that Huffman does when dealing with probabilities that are not an exact [power of two](https://bliptext.com/articles/power-of-two).\nThe central concept behind range coding is this: given a large-enough range of [integers](https://bliptext.com/articles/integer), 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.\nEach 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.\nThe 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.\nWhen 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).\nA 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.\n# [Graphical representation of the coding process. The message being encoded here is \"AABA \" | upload.wikimedia.org/wikipedia/commons/2/2b/Range///encoding.jpg]\n\n## Example\nSuppose we want to encode the message \"AABA \", where is the end-of-message symbol.\nFor this example it is assumed that the decoder knows that we intend to encode exactly five symbols in the [base 10 number system](https://bliptext.com/articles/decimal) (allowing for 105 different combinations of symbols with the range [0, 100000) ) using the [probability distribution](https://bliptext.com/articles/probability-distribution) {A: .60; B: .20; : .20}. The encoder breaks down the range [0, 100000) into three subranges:\nA: [ 0, 60000) B: [ 60000, 80000)\n : [ 80000, 100000)\nSince our first symbol is an A, it reduces our initial range down to [0, 60000) . The second symbol choice leaves us with three sub-ranges of this range. We show them following the already-encoded 'A':\nAA: [ 0, 36000) AB: [ 36000, 48000)\nA : [ 48000, 60000)\nWith two symbols encoded, our range is now [0, 36000) and our third symbol leads to the following choices:\nAAA: [ 0, 21600) AAB: [ 21600, 28800)\nAA : [ 28800, 36000)\nThis time it is the second of our three choices that represent the message we want to encode, and our range becomes [21600, 28800) . It may look harder to determine our sub-ranges in this case, but it is actually not: we can merely subtract the lower bound from the upper bound to determine that there are 7200 numbers in our range; that the first 4320 of them represent 0.60 of the total, the next 1440 represent the next 0.20, and the remaining 1440 represent the remaining 0.20 of the total. Adding back the lower bound gives us our ranges:\nAABA: [21600, 25920) AABB: [25920, 27360)\nAAB : [27360, 28800)\nFinally, with our range narrowed down to [21600, 25920), we have just one more symbol to encode. Using the same technique as before for dividing up the range between the lower and upper bound, we find the three sub-ranges are:\nAABAA: [21600, 24192) AABAB: [24192, 25056)\nAABA : [25056, 25920)\nAnd since is our final symbol, our final range is [25056, 25920) . Because all five-digit integers starting with \"251\" fall within our final range, it is one of the three-digit prefixes we could transmit that would unambiguously convey our original message. (The fact that there are actually eight such prefixes in all implies we still have inefficiencies.\nThey have been introduced by our use of [base 10](https://bliptext.com/articles/decimal) rather than [base 2](https://bliptext.com/articles/binary-numeral-system).)\nThe central problem may appear to be selecting an initial range large enough that no matter how many symbols we have to encode, we will always have a current range large enough to divide into non-zero sub-ranges.\nIn practice, however, this is not a problem, because instead of starting with a very large range and gradually narrowing it down, the encoder works with a smaller range of numbers at any given time.\nAfter some number of digits have been encoded, the leftmost digits will not change.\nIn the example after coding just three symbols, we already knew that our final result would start with \"2\".\nMore digits are shifted in on the right as digits on the left are sent off.\nThis is illustrated in the following code:\nTo finish off we may need to emit a few extra digits.\nThe top digit of is probably too small so we need to increment it, but we have to make sure we don't increment it past.\nSo first we need to make sure is large enough.\nOne problem that can occur with the function above is that might become very small but and still have differing first digits.\nThis could result in the interval having insufficient precision to distinguish between all of the symbols in the alphabet.\nWhen this happens we need to fudge a little, output the first couple of digits even though we might be off by one, and re-adjust the range to give us as much room as possible.\nFor example, imagine the input stream has led the encoder to the right-open interval [****59****888, 60188), that is, and . The trick is to narrow down the interval to [****59****888, 60000) = [****59****888, ****59****999], which allows the encoder to emit two of the left-most digits of , and readjust the interval to [88800, 99999] = [88800, 100000), that is, and.\nThe decoder will be following the same steps so it will know when it needs to do this to keep in sync.\nBase 10 was used in this example, but a real implementation would just use binary, with the full range of the native integer data type.\nInstead of and you would likely use hexadecimal constants such as and.\nInstead of emitting a digit at a time you would emit a byte at a time and use a byte-shift operation instead of multiplying by 10.\nDecoding uses exactly the same algorithm with the addition of keeping track of the current value consisting of the digits read from the compressor.\nInstead of emitting the top digit of you just throw it away, but you also shift out the top digit of and shift in a new digit read from the compressor.\nUse below instead of.\nIn order to determine which probability intervals to apply, the decoder needs to look at the current value of within the interval [low, low+range) and decide which symbol this represents.\nFor the AABA example above, this would return a value in the range 0 to 9.\nValues 0 through 5 would represent A, 6 and 7 would represent B, and 8 and 9 would represent .\n\n# Relationship with arithmetic coding\n[Arithmetic coding](https://bliptext.com/articles/arithmetic-coding) is the same as range coding, but with the integers taken as being the numerators of [fractions](https://bliptext.com/articles/fraction-mathematics).\nThese fractions have an implicit, common denominator, such that all the fractions fall in the range [0,1) . Accordingly, the resulting arithmetic code is interpreted as beginning with an implicit \"0\". As these are just different interpretations of the same coding methods, and as the resulting arithmetic and range codes are identical, each arithmetic coder is its corresponding range encoder, and vice versa. In other words, arithmetic coding and range coding are just two, slightly different ways of understanding the same thing.\nIn practice, though, so-called range encoders tend to be implemented pretty much as described in Martin's paper, while arithmetic coders more generally tend not to be called range encoders.\nAn often noted feature of such range encoders is the tendency to perform renormalization a byte at a time, rather than one bit at a time (as is usually the case).\nIn other words, range encoders tend to use bytes as coding digits, rather than bits.\nWhile this does reduce the amount of compression that can be achieved by a very small amount, it is faster than when performing renormalization for each bit.","revisionCount":0},"hasMore":false,"nextCursor":null}

History