Parallel algorithms for the static dictionary compression Conference Paper uri icon

abstract

  • We study parallel algorithms for two static dictionary compression strategies. One is the optimal dictionary compression with dictionaries that have the prefix property, for which our algorithm requires O(L+log n) time and O(n) processors where L is the maximum allowable length of the dictionary entries, while previous results run in O(L+log n) time using O(n2) processors, or in O(L+log2 n) time using O(n) processors. The other is the longest fragment first (LFF) dictionary compression, for which our algorithm requires O(L+log n) time and O(nL) processors, while previous result has O(L log n) time performance on O(n/log n) processors. We also show that the sequential LFF dictionary compression can be computed on-line with the lookahead of length O(L2).

published proceedings

  • Data Compression Conference Proceedings

author list (cited authors)

  • Nagumo, H., Lu, M., & Watson, K.

complete list of authors

  • Nagumo, H||Lu, M||Watson, K

publication date

  • January 1995