Parallel Parsing Algorithms for Static Dictionary Compression

AbstractÐThe data compression based on dictionary techniques works by replacing phrases in the input string with indexes into some dictionary. The dictionary can be static or dynamic. In static dictionary compression, the dictionary contains a predetermined fixed set of entries. In dynamic dictionary compression, the dictionary changes its entries during compression. We present parallel algorithms for two parsing strategies for static dictionary compression. One is the optimal parsing strategy with dictionaries that have the prefix property, for which our algorithm requires O\u85L logn time and O\u85n processors, where n is the number of symbols in the input string, and L is the maximum length of the dictionary entries, while previous results run in O\u85L logn time using O\u85n2 processors or in O\u85L log2 n time using O\u85n processors. The other is the longest fragment first (LFF) parsing strategy, for which our algorithm requires O\u85L logn time and O\u85n logL processors, while a previous result obtained an O\u85L logn time performance on O\u85n = logn processors. For both strategies, we derive our parallel algorithms by modifying the on-line algorithms using a pointer doubling technique