Data Compression Rearch Based On The Markov Decision Process

Data-Compression is a changing process that change data-stream from input data-stream (source or initial stream) to another kind of less data-stream (export stream or compress stream), the stream is a file or a buffer memory in the memory. At present, most existing data-compression algorithms are used to deal with the data in special field or the file of witch the redundant degree is bigger. Their compression ratios are inconspicuous when the input data-stream are the binary files or the small redundant files.In order to raise the data-compression ratio of the small redundant files, through studying the existing data-compression algorithm, I have proposed a new kind of algorithm, it based on DMC (Dynamic Markov Chain) and Deflate algorithm. The algorithm falls into two parts. At first, it is to use LZ77 algorithm, Then it get final compression code by arithmetic algorithm and the control on state space of Markov decision processes. The final compression code is through calculation the transformation probability on the currently state.Markov decision processes are used to control the Markov state aggregate in this algorithm, the purpose is to obtain reward as much as possible by some kinds of optimization strategies. According to the different length of data-cell, Markov decision processes have different effect. If the lengths of data-cell are bigger, the decision processes are more complicated too, the compression-ratio are higher.What I choice is to deal with 2 bit data each time in the project. In this way, each state includes four pieces of outputted transformation probability in the state space of Markov, symbols that can be input in the state space are 00,01,10,11, the state will have four transferring optional route of the next state. The structure diversification of the state spaces, will bring bigger pieces of application spaces for the Markov decision processes, improve compression ratio, at the same time it make the decision processes changed complicated.Markov decision processes includes deciding,seeking optimal strategies and obtaining the largest rewards. In this project, the most important decision is to judge whether the current state needs to clone and to choice the clone method, there are two parameters in the decision processes, one is transformation probability of the current state (in the project, it is parameter count), another is mapping in the inner of the state (in the project, it is parameter mapping); one kind of simple seeking optimal strategies is dynamic adjust all kinds of counts of the current state, what is dynamic adjusted are some parameters that be used to be a kind of standard and rank values that be used to record the space in adaptive arithmetic coding phase; In order to obtain reward as much as possible, this project realize by call the adaptive arithmetic algorithm produce final compression-code.In the last part of the paper, I designed some testing example and analyzed the testing result for the project, and educe conclusion in the studying process. The compression ratio of the new algorithm have more improved than the Zip algorithm when the small redundant objects were compressed such as *.jpg,*.mp3.