DocumentCode :
2707482
Title :
Of Lempel-Ziv-Welch parses with refillable gaps
Author :
Apostolico, Alberto
Author_Institution :
Padova Univ., Italy
fYear :
2005
fDate :
29-31 March 2005
Firstpage :
338
Lastpage :
347
Abstract :
We consider gapped variants of classical data compression paradigms (Ziv, J. and Lempel, A.,1977, 1978; Welch, T.A., 1984). In the original algorithm, phrases are identified and stored in a dictionary on-the-fly as the text-file is scanned. The entries in the dictionary are then matched against the incoming string, thereby determining the next codeword, and this gives the method an inherently linear-time implementation. In our variants, the phrases used in compression are selected among suitably chosen strings of intermittently solid and wild characters produced by the autocorrelation of the source-string, in a way that still preserves linearity of time. At the receiver, gaps can be filled back exactly, interpolated, or left blank, so that lossless, as well as lossy, implementations are possible. However, the focus of the paper is on lossy variants.
Keywords :
correlation methods; data compression; dictionaries; interpolation; text analysis; codeword; data compression; dictionary; linear-time implementation; phrases; source-string autocorrelation; text-file; Arithmetic; Autocorrelation; Data compression; Dictionaries; Encoding; Humans; Linearity; Solids; Source coding; USA Councils;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Compression Conference, 2005. Proceedings. DCC 2005
ISSN :
1068-0314
Print_ISBN :
0-7695-2309-9
Type :
conf
DOI :
10.1109/DCC.2005.58
Filename :
1402195
Link To Document :
بازگشت