SUFFIX ARRAYS - A Competitive Choice for Fast Lempel-Ziv Compressions
See where this sits in the topic map →Abstract
Keywords: Lempel-Ziv, Lossless Data Compression, Suffix Arrays, Suffix Tre es, String Matching.Abstract: Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used in a variety of applications.The LZ encoder and decoder exhibit a high asymmetry, regarding time and memory requirements, with theformer being much more demanding. Several techniques have been used to speed up the encoding process;among them is the use of suffix trees. In this paper, we explore the use of a simple data structure, namedsuffix array , to hold the dictionary of the LZ encoder, and propose an algorithm to search the dictionary.A comparison with the suffix tree based LZ encoder is carried out, showin g that the compression ratios areroughly the same. The ammount of memory required by the suffix arra y is fixed, being much lower than thevariable memory requirements of the suffix tree encoder, which depen ds on the text to encode. We concludethat suffix arrays are a very interesting option regarding the tradeoff b etween time, memory, and compressionratio, when compared with suffix trees, that make them preferable in som e compression scenarios.