News for hackers. Stuff that matters.
Re:Programming Algorithms in Lisp: Data Structures by zshrdlu on Wednesday August 07, 2019 @03:05AM (#20632543)
I'm enjoying this series. A while back I was playing around with binary arithmetic coding and statistical modelling. For the modelling I was using a simple Markov model, and I hit performance issues. I explored all kinds of trees but eventually settled on Hash tables. Eventually I had to use my own specialized bit vectors and hash tables, but it was my first brush with a problem-space where data structures and algorithms are critical.

The algorithm worked amazingly well for small strings, outperforming the PAQ versions I tried, but it lost compression power as the input got longer. I didn't have the mathematical expertise to figure out why that was the case.

Still didn't get it to the kind of performance I liked, but maybe someone with greater insight could take a look at it: https://github.com/shrdlu68/ac-experiment

There are no comments on this comment yet.