Title :
PRAM algorithms for static dictionary compression
Author :
Stauffer, L.M. ; Hirschberg, D.S.
Author_Institution :
Dept. of Inf. & Comput. Sci., California Univ., Irvine, CA, USA
Abstract :
Parallel algorithms for lossless data compression via dictionary compression using the longest fragment first (LFF) and greedy parsing strategies are described. Dictionary compression removes redundancy by replacing substrings of the input by references to strings stored in a dictionary. Given a static dictionary stored as a suffix tree, we present PRAM CREW algorithms for LFF compression which run in O(log2 n) time with O(n/log n) processors where it is assumed that the maximum dictionary entry is of length O(log n). We also describe a logarithmic time and linear processor algorithm for greedy parsing
Keywords :
computational complexity; data compression; grammars; parallel algorithms; shared memory systems; trees (mathematics); LFF; PRAM CREW algorithms; PRAM algorithms; concurrent read exclusive write; greedy parsing; greedy parsing strategies; inear processor algorithm; longest fragment first; lossless data compression; maximum dictionary entry; parallel algorithms; parallel random access memory; static dictionary compression; substrings; suffix tree; Computational modeling; Computer science; Concurrent computing; Data compression; Dictionaries; Parallel algorithms; Phase change random access memory; Polynomials; Random access memory; Read-write memory;
Conference_Titel :
Parallel Processing Symposium, 1994. Proceedings., Eighth International
Conference_Location :
Cancun
Print_ISBN :
0-8186-5602-6
DOI :
10.1109/IPPS.1994.288279
