1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

That extra word is the equivalent of having an additional symbol that represents the end of file marker, or storing the size of the decoded block in a header. The "overhead" of $O(1)$ bits can also be understood as $o(1)$ bits per symbol, and is therefore is negligible for the purpose of understanding the compression rate.

This is the sense in which ANS is always better than or equal to Huffman coding.

It doesn't necessarily mean that ANS is more appropriate than Huffman coding for your specific application; sometimes, for extremely low-bandwidth applications (e.g. submarine communication), the precise number of bits in each message matters a great deal.

$\endgroup$
1
  • $\begingroup$ this makes sense, ANS has a fixed ending state of the FSM but a variable beginning state. If there was a way to fix the beginning state instead of the ending state then you could have an FSM encoding that doesn't waste this extra symbol, although I'm not sure if there's a named method for constructing that? $\endgroup$
    – terepy
    Aug 9, 2023 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.