A Compression Method With Random Access Abilities

With the rapid development of computer,the whole society can no longer live without information.Massive amount of information means we need to handle massive amount of data.How to deal with huge amount of data is a serious problem.Data compression is becoming a mature and fruitful research field now.However,in previous studies,most people concern with the coding rate and compression rate.In fact,most information is updated very fast in nowadays,so random accessing in compressed files is also a very important issue.Random access is a property that any data element can be accessed from a set of addressable elements efficiently.Though there had some research results in this field.All schemes had been present need auxiliary data to solve the problem.That is,they caused extra cost of space.In this thesis,a compression scheme for prefix coding,especially for Huffman coding,is presented,such that the compressed file supports a level of random access ability.In particular,the proposed approach does not require additional space to store the auxiliary information,and the compressed file generated by the proposed approach has the same size with the file generated by the conventional prefix coding.To our knowledge,this is the first compression method to possess the random access ability on the compressed file without increasing the storage space.For a source sequence,we store the code-word of symbols with blocks of fixed size.We use t denote the size of a block.In this thesis,a preprocessing algorithm is presented to calculate the size allocated to each block when t is not an integer.In the simulation,when the Huffman coding is chosen,it has to access around 200 bits of the compressed file to retrieve a symbol in average while the compression rate is 0.57.The average cost of retrieving of our scheme is equal to the size of uncompressed file by 4.5 x 10-5 times,and also is 104 times less than the average cost of retrieving of Huffman coding.The simulation proved that the compression scheme has good perfor-mance in real world.