Universal compression algorithms based on approximate string matching

Two practical universal source coding schemes based on approximate string matching are proposed. One is an approximate fixed-length string matching data compression, and the other is an LZ-type quasi parsing method by approximate string matching. It is shown that in the former algorithm the compression rate converges to the theoretical bound of R(D) for ergodic and stationary processes as the average string length tends to infinity. A similar result holds for the latter algorithm in the limit of the infinite database produced by the former algorithm. The main advantages of the proposed methods are the asymptotic behavior of the encoder implementation and the simplicity of the decoder. Practical results of image and voice compression will be presented