Bounded size dictionary compression: SCk-completeness and NC algorithms

AbstractWe study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(logkn), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(logkn) space (that is, SCk). We also introduce a variation of this heuristic that turns out to be an SCk-complete problem (the original heuristic belongs to SCk+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given