An Improved LZW Algorithm for Large Data Size and Low Bitwidth per Code
Yi-Lin Tsai, Jian–Jiun Ding · TENCON 2021 - 2021 IEEE Region 10 Conference (TENCON) · 2021
The Lempel-Ziv-Welch (LZW) algorithm achieves outstanding performance and is widely used in text encoding. However, when the bit-width for each code is limited and the amount of data to be encoded is huge, the dictionary will be prematurely full. As a result, the new string cannot be added to the dictionary in the later encoding process and thus the performance is compromised. In this paper, an improved LZW algorithm is proposed to address this problem. In the proposed algorithm, the string is added to the dictionary only if the frequency of the string reaches the threshold. In this way, the dictionary is left only for the common strings. The experiments on the test patterns consisting of 300,000 characters show that the proposed algorithm further enhances the compression rates and is efficient for data compression. For example, the compression rate of the proposed algorithm is 6.0% larger than that of the LZW algorithm when each codeword contains 12 bits.