Fast multi-match Lempel-Ziv

Summary form only given. One of the most popular encoders in the literature is the LZ78, which was proposed by Ziv and Lempel (1978). We establish a recursive way to find the longest m-tuple match. We prove the following theorem that shows how to obtain a longest (m+1)-tuple match from the longest m...

Full description

Saved in:
Bibliographic Details
Main Authors: Pinho, M.S., Finamore, W.A., Pearlman, W.A.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Compression algorithms
Computational efficiency
Data compression
Dictionaries
Encoding
Numerical analysis
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Summary form only given. One of the most popular encoders in the literature is the LZ78, which was proposed by Ziv and Lempel (1978). We establish a recursive way to find the longest m-tuple match. We prove the following theorem that shows how to obtain a longest (m+1)-tuple match from the longest m-tuple match. It shows that a (m+1)-tuple match is the concatenation of the first (m-1) words of the m-tuple match with the next longest double match. Therefore, the longest (m+1)-tuple match can be found using the m-tuple match and a procedure to compute the longest double match. Our theorem is as follows. Let A be a source alphabet, let A* be the set of all finite strings of A, and D/spl sub/A*, such that if x/spl isin/D then all prefixes of x belong to D. Let u denote a one-sided infinite sequence. If b/sub 1//sup m/ is the longest m-tuple match in u, with respect to D, then there is a longest (m+1)-tuple match b/spl circ//sub 1//sup m+1/, such that b/spl circ//sub i/=b/sub i/,/spl forall/i/spl isin/{1,...m-1}. We implemented the fast mmLZ and the results show a improvement in compression of around 5% over the LZW, in the Canterbury Corpus (Arnold and Bell, 1997) with little extra computational cost.
ISSN:1068-0314
2375-0359
DOI:10.1109/DCC.1999.785702