IMPROVED VARIATIONS RELATING THE ZIV-LEMPEL AND WELCH-TYPE ALGORITHMS FOR SEQUENTIAL DATA-COMPRESSION

Several data compression algorithms relating existing important source coding algorithms, including Ziv-Lempel codes, Rissanen's Context, and Welch's LZW method, are presented. First, an intermediate algorithm between the two Ziv-Lempel methods for universal data compression is proposed, which has the same asymptotic optimality as the well-known method based on the incremental parsing. The proposed algorithm is then compared with the context gathering algorithm Context in terms of gathering direction and gathering frequency. It is shown that while the proposed algorithm and Context have the same gathering frequency, they have opposite directions of context gathering. Practical variations are also considered. By combining the proposed algorithm with Welch's device, two practical data compression methods are obtained. They, as well as Welch's LZW method, start with a small table of symbol strings and build the table during compression and decompression. tn our practical methods, higher compression efficiency can be gained by accelerating the growth of the table.