Title :
Sliding Window Update Using Suffix Arrays
Author :
Ferreira, Artur ; Oliveira, Arlindo ; Figueiredo, Mário
Author_Institution :
Inst. Super. de Eng. de Lisboa, Lisbon, Portugal
Abstract :
The sliding window (SW) Lempel-Ziv (LZ) 77 algorithms are widely used for universal lossless data compression. The LZ77 encoding component performs repeated substring search. Data structures, such as hash tables and trees have been used for fast search, at the expense of memory usage. Recently, suffix arrays (SA) have been used for dictionary representation and LZ77 decomposition, using less memory than those data structures.
Keywords :
data compression; string matching; tree searching; Lempel-Ziv 77 algorithm; dictionary representation; hash tables; sliding window update; substring search; suffix arrays; universal lossless data compression; Arrays; Binary trees; Data compression; Dictionaries; Encoding; Memory management; LZ77; Lempel-Ziv compression; Suffix Arrays; memory-efficient;
Conference_Titel :
Data Compression Conference (DCC), 2011
Conference_Location :
Snowbird, UT
Print_ISBN :
978-1-61284-279-0
DOI :
10.1109/DCC.2011.60
