Henry Ker-Chang Chang and Shing-Hong Chen*
Graduate School of Resources Management
National Defense Management College
Chung-Ho, Taipei, Taiwan 235, Republic of China
Army General Headquarters
Loung-Tang, Taoyuan, Republic of China
A locally adaptive data compression scheme for Chinese text files is proposed in this paper. The proposed scheme is essentially a one-pass data compression algorithm in which the compression and decompression routines can be conducted simultaneously. The proposed scheme is developed on the basis of a two-dimensional linked list and the locality of reference. An identical number of lists in the two-dimensional linked list and identical contents of each linked list are always controlled as the coding process is during operation. Each character is encoded by a positional integer prefixed by several zeros. Additionally, an integer character followed by the original BIG-5 code is used to encode a character which has appeared for the first time. The locality of reference is implemented by the move-to-front operation with which the positional integers for frequently encountered characters can be encoded on a small scale. Furthermore, several empirical tests for various types of Chinese text files are implemented, revealing that the compression ratios of the proposed scheme are greater than 50%. Results obtained from the empirical tests clearly verify the advantages of the proposed scheme over other methods.
Keywords: locally adaptive coding scheme, data compression, two-dimensional linked list, locality of reference, Huffman coding
Received June 30, 1994; revised April 15, 1995.
Communicated by Hsi-Jian Lee.