A fast on-line adaptive code
Boris Ya. Ryabko · IEEE Transactions on Information Theory · 1992
There are two classes of data compression algorithms. One class has redundancy log log n+O(1), where n is the alphabet size, and an encoding time O(log/sup 2/ n), n to infinity . The other has redundancy O(1) and an encoding time O(n). A code is presented combining advantages of both classes of compression methods: its redundancy is O(1) and the encoding and decoding time is O(log/sup 2/ n) per letter, which is close to the lower bound O(log n).>