DocumentCode :
3054048
Title :
Complexity of preprocessor in MPM data compression system
Author :
Kieffer, John ; Yang, En-Hui ; Park, Trevor ; Yakowitz, Sidney
Author_Institution :
Elec. & Comput. Eng. Dept., Univ. of Minnesota Twin Cities, MN, USA
fYear :
1998
fDate :
30 Mar-1 Apr 1998
Firstpage :
554
Abstract :
Summary form only given. The multilevel pattern matching data compression system is one of a class of compression algorithms introduced by Kieffer and Yang (see ERA Amer. Math. Soc., vol.3, p.11-16, 1997). The MPM system is currently of interest because of its good redundancy performance in losslessly compressing data strings of arbitrary length over a finite alphabet. An MPM system consists of a preprocessor, encoder/decoder, and a reconstruction engine. The preprocessor detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The preprocessor operates at several levels sequentially, with the number of levels selected by the user. The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The preprocessor represents information about matching patterns at each level as a string of tokens which is passed to the encoder of the MPM system. The decoder of the MPM system recovers these token strings, from which the reconstruction engine rebuilds the input data string. The preprocessor is the most complex component of the MPM system. We exhibit an implementation of the preprocessor of linear complexity in terms of execution time and space requirements; the number of levels satisfies O(log2log2n) for input data strings of length n
Keywords :
computational complexity; data compression; decoding; image coding; image reconstruction; pattern matching; MPM data compression system; compression algorithms; encoder/decoder; execution time; finite alphabet; input data string; linear complexity; lossless data strings compression; multilevel pattern matching; preprocessor; reconstruction engine; redundancy performance; substrings; token strings; Cities and towns; Compression algorithms; Data compression; Data preprocessing; Decoding; Engines; Pattern matching; Performance loss; Source coding; Space technology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Compression Conference, 1998. DCC '98. Proceedings
Conference_Location :
Snowbird, UT
ISSN :
1068-0314
Print_ISBN :
0-8186-8406-2
Type :
conf
DOI :
10.1109/DCC.1998.672292
Filename :
672292
Link To Document :
بازگشت