tag:blogger.com,1999:blog-5246987755651065286.post5242747831874528013..comments2022-01-05T09:06:18.603-08:00Comments on cbloom rants: 05-11-15 - ANS Minimal Flushcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-5246987755651065286.post-56567940859193391852015-05-17T15:59:59.791-07:002015-05-17T15:59:59.791-07:00Thanks Charles. It's pretty clear and does mak...Thanks Charles. It's pretty clear and does make sense now.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-10768131446303093432015-05-17T15:04:12.895-07:002015-05-17T15:04:12.895-07:00I guess it's not clear in my comment -
while ...I guess it's not clear in my comment -<br /><br />while the same theory applies to TANS , in practice there's no point in using that flush TANS.<br /><br />TANS state x varies from L to 2L (in implementation we usually ignore the +L shift). So the probability difference from the bottom to the top of the range is only a factor of *1/2 (this corresponds to the fact that a maximum of just under 1 bit can be pending in x).<br /><br />So you have to write some bits to save 1 bit, doesn't make sense.<br /><br />The difference comes not from TANS vs RANS per se, but from the base used for output; if you renorm to output bits, or bytes, or dwords. In TANS we typically choose to output bits, and in RANS we choose to output something larger.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-8858832731406008142015-05-17T14:51:22.940-07:002015-05-17T14:51:22.940-07:00In the encoder final flush (at the head of the str...In the encoder final flush (at the head of the stream), Minimal ANS does not and cannot discard any bits.<br /><br />But the state x may have many leading 0 bits. Those do not need to be sent.<br /><br />This is true for TANS and RANS.<br /><br />Basically we are using the fact that the probability distribution of x is 1/x. Higher values are less likely.<br /><br />This corresponds to the buffered information content of x being log2(x).<br /><br />Fortunately the ideal coder for 1/x is very simple - just send # of bits in x, then the value of those bits.<br /><br />For TANS this is a much smaller savings because the # of bits in state (L) is typically very small, perhaps 12. With RANS the number of bits in x is much larger (32 or 64).<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-24049498475115314322015-05-17T14:25:42.736-07:002015-05-17T14:25:42.736-07:00@cbloom
While I do understand how to make use of ...@cbloom<br /><br />While I do understand how to make use of the initial encoding state (last decoding state) to store something useful in order to minimize flush losses,<br /><br />I don't really understand the same for the last encoding state (hence first decoding state) which is described in your blog post.<br /><br />I suspect the difference is related to rANS/tANS different behaviors.<br /><br />For tANS, any bit stored is mandatory to correctly interpret the state, hence the symbol retrieved, and therefore the next symbol. Not a single bit can be missed, or guessed.<br /><br />I suspect this is because in tANS, symbols are spread, while in rANS, they lay next to each other, in a contiguous segment. So it's possible to not use all bits to guess the appropriate segment, hence appropriate symbol.<br /><br />But still, you have to make sure those "remaining" bits don't have an avalanche effect later on, to deduce some future symbol in the stream.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-86307228450817293372015-05-17T13:13:29.833-07:002015-05-17T13:13:29.833-07:00Hi Fabian
Yes, it looks similar from my earlier c...Hi Fabian<br /><br />Yes, it looks similar from my earlier comment, but short answer : it's different from an EOF symbol.<br /><br />Long answer :<br />There are 2 conditions to tell that a compressed stream is finished.<br /><br />First, the compressed stream must be entirely and strictly consumed. That means that the size of the compressed stream is known, which in my implementation is necessary, since decompression read is done backward.<br /><br />This is properly checked : the beginning of the stream is known, so it's trivial to ensure we never read beyond that limit. The stream is consumed when not a single bit remains (and there is an error if it requires 1+ more bits than available).<br /><br />But that's not enough. Since some symbols may have a probability > 50%, in such case, they can be compressed in less than a bit. So just reaching exactly the end of bitstream is not enough.<br /><br />Then, it's also necessary to check the value of "state", and ensure it reaches a pre-determined value (which is proposed to be "zero"). So if some high probability symbols are still there, they can be decoded, just from decreasing state value, up to zero.<br /><br />Such check wouldn't be necessary if the number of symbols was known beforehand.<br />So that's where the trade-off is : either provide the number of symbols to decode, or agree on a pre-determined final state value.<br /><br /><br />Alternatively, note that if no symbol is > 50%, then such additional check is unnecessary, and just following the bit stream would be enough. Still, checking the state value can still be useful as an "integrated error checker", since if it has not reached the desired final state value, it means the compressed stream is malformed.<br /><br />Hope it makes sense.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-454472416039805422015-05-15T14:38:53.208-07:002015-05-15T14:38:53.208-07:00Not sure I understand what you mean here. Do you m...Not sure I understand what you mean here. Do you mean that you reserve one state value for EOF? How is that different from including an explicit EOF symbol in your alphabet?<br /><br />Unless you stop normalizing near the end like Charles does (and for that, you need to know where the end is!), you'll be maintaining normalization the whole way through. But reserving a normalized state value to denote EOF really is just adding an EOF symbol to your alphabet. Or am I misunderstanding you?<br /><br />If it is an EOF symbol, that's a perfectly reasonable thing to do (and a common choice) but it's not a fixed cost; yes, you pay ~11 bits near the end to actually send the EOF, but you also knock out one state you could otherwise use, which has a small but nonzero tax of -log2((2^11 - 1) / 2^11) = 0.0007 bits per symbol.<br /><br />Say a block has 16384 symbols, then that adds up to about 11.54 bits overhead - plus the final expected 11 bits to send an EOF flag with probability 2^-11. Which comes out to... about 3 bytes. :) (Worse if your block has more symbols, better if it's less.)Fabian Giesenhttps://www.blogger.com/profile/02888328259787074706noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-23914444215536202592015-05-15T05:15:19.110-07:002015-05-15T05:15:19.110-07:00I initially tried to "store" something u...I initially tried to "store" something useful in the final decoded state value (the one by which encoding is started...). This way, on reaching the end of ANS decoding, there was still "something useful" to decode from the state.<br /><br />But then, I realized that to properly finish decoding, I needed to indicate the number of symbols to decode from the ANS stream. This is, in itself, a header cost.<br /><br />In contrast, by keeping the final state value at a known "zero", it embedded one way to check that the end of ANS stream is reached.<br /><br />In my case, state is 9-11 bits, while stream size is a 2-3 bytes value. Therefore, it's a bit more advantageous to use the state.<br /><br />But the difference is very minor.<br />So I'm not yet settled on the best way to proceed.<br />Let's just say that both costs are comparable, and I found no secure way to get rid of both.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-79076896802614895482015-05-11T16:17:34.421-07:002015-05-11T16:17:34.421-07:00Yup true.
The RANS approximation hurts more for s...Yup true.<br /><br />The RANS approximation hurts more for smaller x (relative to prob_bits). So it's particularly bad at x=0 !<br /><br />These are early days for ANS. I suspect in 20 years we'll have worked out standard ways of doing these details that are better. (it took ages to tweak out the details or arithmetic coding, 40 years or something? crazy)<br /><br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-30051570387550497692015-05-11T15:57:51.413-07:002015-05-11T15:57:51.413-07:00I think I mentioned this in a mail, but again for ...I think I mentioned this in a mail, but again for the record: initializing the state to 1 and letting it grow does not buy you as much as it does with a minimal-flush arithmetic coder.<br /><br />With a minimum-flush ari, you can initialize an arithmetic coder, send 7 random bits with a uniform distrib, and when you flush you'll always get a single byte, no problem.<br /><br />The rANS update is "x = ((x / freq) << prob_bits) + (x % freq) + base;". With a uniform binary distrib, one symbol will have base = (1 << prob_bits)/2, and so your x will instantly grow to prob_bits-1 bits and keep growing from there; so with a 16-bit probability resolution, a single bit can grow your output to 2 bytes.<br /><br />This is purely an artifact of the rANS "output permutation". A tANS-style interleaved permutation (or uABS-style binary coder) grows x more "smoothly".Fabian Giesenhttps://www.blogger.com/profile/02888328259787074706noreply@blogger.com