| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 116.36 KB | Adobe PDF |
Advisor(s)
Abstract(s)
The Lempel-Ziv 77 (LZ77) and LZ-Storer-Szymanski (LZSS) text compression algorithms use a sliding window over the sequence of symbols, with two sub-windows: the dictionary (symbols already encoded) and the look-ahead-buffer (LAB) (symbols not yet encoded). Binary search trees and suffix trees (ST) have been used to speedup the search of the LAB over the dictionary, at the expense of high memory usage [1]. A suffix array (SA) is a simpler, more compact data structure which uses (much) less memory [2,3] to hold the same information. The SA for a length m string is an array of integers ([1], ...[k], ...a[m]) that stores the lexicographic order of suffix k of the string; sub-string searching, as used in LZ77/LZSS, is done by searching the SA.
Description
Keywords
Lempel-Ziv 77 (LZ77) LZ-Storer-Szymanski (LZSS)
Citation
Ferreira A., Oliveira, A., Figueiredo, M. – On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression. In 2009 Data Compression Conference. Snowbird, UT, USA: IEEE, 2009. ISBN 978-0-7695-3592-0. Pp. 1-1. Doi: 10.1109/DCC.2009.50
Publisher
IEEE