regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because huffman coding is also optimal in this case).
Streaming ANS lets us avoid the need to use a BigInteger or other expensive operation for a little compression loss. trying to understand it, I wrote a simple encoder:
const FREQ: &[u64] = &[1, 1, 2]; //frequency of each symbol
const T: u64 = 1; //encoding precision, increasing increases compression but decreases performance
pub const CUMUL: [u64; FREQ.len() + 1] = { //cumulative sums of previous frequencies
let mut r = [0; FREQ.len() + 1];
let mut i = 1;
while i < r.len() {
r[i] = r[i-1] + FREQ[i-1];
i += 1;
}
r
};
pub const M: u64 = CUMUL[CUMUL.len() - 1];
#[derive(Debug)]
pub struct RansState {
value: u64,
bitstream: Vec<bool>,
}
impl RansState {
pub fn new() -> Self {
RansState {
value: M * T,
bitstream: Vec::new(),
}
}
pub fn encode(&mut self, symbol: usize) {
self.stream_out(symbol);
let block_id = self.value / FREQ[symbol];
let slot = self.value % FREQ[symbol] + CUMUL[symbol];
self.value = block_id * M + slot;
}
pub fn decode(&mut self) -> usize {
let block_id = self.value / M;
let slot = self.value % M;
let symbol = CUMUL.iter().position(|x| slot < *x).unwrap() - 1;
self.value = block_id * FREQ[symbol] + slot - CUMUL[symbol];
self.stream_in();
symbol
}
pub fn finish(mut self) -> Vec<bool> { //write the current state into the bitstream and output it
assert!(self.value >= M * T); //this assertion holding means it's possible to elide one bit, but how could you elide all of them?
while self.value > 0 {
self.bitstream.push((self.value & 1) != 0);
self.value >>= 1;
}
self.bitstream
}
pub fn start(bitstream: Vec<bool>) -> Self { //extract the initial state from the bitstream
let mut r = Self { value: 0, bitstream, };
while r.value < M * T {
r.value <<= 1;
r.value += r.bitstream.pop().unwrap_or(false) as u64;
}
r
}
fn stream_out(&mut self, symbol: usize) {
while self.value >= FREQ[symbol] * 2 * T {
self.bitstream.push((self.value & 1) != 0);
self.value >>= 1;
}
}
fn stream_in(&mut self) {
while self.value < M * T {
self.value <<= 1;
self.value += self.bitstream.pop().unwrap_or(false) as u64;
}
}
}
It seems to work, and it approaches optimal compression for large streams (provided T is also sufficiently large). But I couldn't figure out how to get around the need to encode the final state of the encoder (which is the initial state of the decoder).
I noticed it's possible to elide one bit from the encoding because we know that M * T <= value < M * T * 2, but I can't see how all bits could be elided.
I looked around at some other implementations and they all seem to do a similar thing. But this seems to contradict ANS having strictly better compression than huffman, if we have symbol frequencies that are powers of two, the ANS encoding is always a few bits larger than the huffman encoding.
