Arithmetic coding demo

[cyntsh]

In this demo, recursive interval subdivision for arithmetic coding is reformulated using fold. Side note: I also found the types very nice to reason with, esp. Interval, which reduces the algorithm to manipulating intervals.

[j-towns]

@cyntsh are you familiar with asymmetric numeral systems (ANS)? This is a more recent and nowadays more widely used alternative to arithmetic coding, and on a high level the only difference is that AC is 'queue-like', or first-in-first-out, whereas ANS is 'stack-like', or last-in-first-out.

The power of ANS is roughly equivalent to that of AC, but it is significantly easier to implement (I'm talking here about an 'exact' implementation in terms of integer arithmetic). In case you're interested, I've written a short (< 50 lines), pure functional, pure Python (no imports) ANS implementation which I imagine would not be too difficult to port into Dex: https://github.com/j-towns/ans-notes/blob/master/rans.py.

[cyntsh]

Thanks for the suggestion, @j-towns ! Your ANS implementation looks incredibly compact - I'll have a read and give it a try sometime this week.

[j-towns]

@cyntsh how come you can't use the Word types and bit-wise operations defined in the Prelude? (these ones)

[cyntsh]

@j-towns good point, that does improve the compression accuracy, but still not quite at the level of your python implementation. I suspect that it has to do with comparators (<, >) when the Word64-type integers get large enough. After writing a Word64 instance for Ord, here’s what I get:

w: Word64 = (one .<<. 63)
:p w
> 0x8000000000000000
:p w > zero
> False