Title :
YK data compression algorithms: complexity, implementation, and experimental results
Author :
Yang, En-Hui ; Jia, Yunwei
Author_Institution :
Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont., Canada
Abstract :
We present an efficient implementation of the YK data compression algorithms of Yang and Kieffer (see IEEE Trans. Inform. Theory, vol.46, p.755-7, 2000), and show that they have essentially linear computation and storage complexities. Experimental results show that: (1) on standard data sets, these algorithms achieve compression performance comparable to that of PPM algorithms; (2) on data that are frequently encountered in real-time communications (such as HTML files), the YK algorithms achieve better compression performance than that of PPM algorithms
Keywords :
computational complexity; data compression; data structures; hypermedia markup languages; HTML files; PPM algorithms; YK data compression algorithms; algorithm complexity; algorithm implementation; compression performance; efficient implementation; experimental results; grammar-based data compression algorithms; linear computation complexity; linear storage complexity; lossless data compression algorithms; real-time communications; standard data sets; Algorithm design and analysis; Arithmetic; Communication standards; Councils; Data compression; Data structures; Entropy; H infinity control; HTML; Production;
Conference_Titel :
Information Theory, 2001. Proceedings. 2001 IEEE International Symposium on
Conference_Location :
Washington, DC
Print_ISBN :
0-7803-7123-2
DOI :
10.1109/ISIT.2001.935940
