<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">On 12/29/2013 11:12 PM, chen wrote:<br>
</div>
<blockquote
cite="mid:2d9cdbf9.cf8d.14341b3dd52.Coremail.chenm003@163.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div
style="line-height:1.7;color:#000000;font-size:14px;font-family:arial">
<div>The idea seems like Range Coder.</div>
</div>
</blockquote>
It can encode large alphabets like Range Coding, but is a few times
faster - single decoding step is for example just:<br>
<br>
nbBits = decodeTable[state].nbBits;<br>
symbol = decodeTable[state].symbol;<br>
state = decodeTable[state].newState | (bitStream &
mask[nbBits]);<br>
bitStream = bitStream >> nbBits;<br>
<br>
where mask[nbBits]=(1<<nbBits)-1<br>
so there is no branching, no multiplication - just pure stream
decoding: a single table use and a few binary operations per symbol.<br>
Probabilities of symbols are approximated by newState/oldState - by
rational numbers, very close to the expected probabilities - we get
rates like in arithmetic.<br>
<br>
The cost is that for every probability distribution (context), we
need to store such coding table - let say 1-16kB for 256 size
alphabet.<br>
So for image/video coding, I thought about grouping a few positions
in the matrix of quantized DCT coefficients: e.g. if in 1st position
there are 10 possibilities, 5 in 2nd and 3rd, we group these 3
choices into 250 size alphabet: (c1,c2,c3) choice corresponds to
25*c1+5*c2+c3 symbol. <br>
We fix ANS table for each of such grouping for some optimized
probability distribution - for free it can additionally contain
correlations between these positions.<br>
<br>
If the total number of such cases (different ANS tables we could use
for fixed coder parameters) is smaller than let say a thousand, all
of them could fit into 1MB (cache).<br>
</body>
</html>