Rapid encoding of run lengths and pyramid cubic lattices
R.E. Krichevskiy, Vladimir N. Potapov · IEEE Transactions on Information Theory · 1999
We can encode rare events with an overhead of about 1.56 bits/event. The contribution of the overhead to the total length of the code is negligible. The encoding and decoding time counted in operations over bits per bit of the code does not depend on the number of appearances of the events. We also present algorithms of the same speed which enumerate the pyramid cubic lattices with an overhead of about 1.56 bits/dimension. The overhead is the price for reaching the ultimate (to within a constant factor) encoding and decoding speed.