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.
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