A New Compression Ratio Prediction Algorithm for Hardware Implementations of LZW Data Compression

As the demand for more data storage space continues to grow at an unprecedented pace, the need for real time data compression systems becomes more prominent. One of the well-known methods among lossless data compression algorithms is LZW. In this paper, a new prediction algorithm has been introduced that is able to predict whether or not a data block is compressible with the LZW method. Furthermore, the prediction algorithm provides a reasonably good estimation of the final compression ratio, hence helping the storage system decide early on whether or not to continue with the compression. Simulation results performed on several data compression corpuses indicate that the proposed prediction method is able to reduce run time by 17.79%, in average for a flash sector size of 8 KB. This is achieved at the expense of an average 1.59% decrease in compression performance. The difference between the predicted and actual compression ratio is 11.16% in average, in terms of mean absolute error. Considering the low computational complexity of the proposed method, it can be implemented with a relatively simple hardware hence making it suitable for real time, low-cost, and low-power hardware implementations.