Improved Ziv-Lempel Type Data Compression Method
Original Publication Date: 1985-Aug-01
Included in the Prior Art Database: 2005-Feb-19
This invention relates to a method for adaptive compression of finite binary strings using a modified Ziv-Lempel weighted parsing tree algorithm. In the prior art, a universal model for data compression was defined by Ziv and Lempel in "Compression of Individual Sequences Via Variable-rate Encoding," IEEE Transactions on Information Theory, IT- 24, 5, 530-536 (1978). The Ziv-Lempel incremental parsing algorithm reaches asymptotically the optimum compression for strings generated by stationary sources. In this model, the number of parameters grows with the string. In the method of this invention, excessive parameters are eliminated by using the Ziv-Lempel data gathering tree in a different way.