A Fast Implementation of Arithmetic Coding

This paper advances a new lossless data compression method utilizing reversible data hiding to reduce compression times significantly and achieve good compression rates. The core idea of the new approach is to transform a longer binary sequence into a shorter n-ary sequence, transform the n-ary sequence into two binary subsequences, and apply a lossless coding algorithm based on the assumption that a shorter sequence obviously takes less time than a longer sequence. Mathematical conditions to show when the theory proposed in this paper is attainable are provided. The proposed method keeps as good of a compression rate as arithmetic coding, but takes much less time than that. Experiments show that the proposed theory is true.