Optimal parallel dictionary matching and compression (extended abstract)
Martı́n Farach-Colton, Subramanian Muthukrishnan · 1995
Emerging applications in multi-media and the Human Genome Project require storage and searching of large databases of strings -a task for which parallelism seems the only hope.In this paper, we consider the parallelism in some of the fundamental problems in compressing strings and in matching large dictionaries of patterns against texts.We present the jirst work-optimal algorithms for these well-studied problems including the classical dictionary matching problem, optimal compression with a static dictionary and the universal data compression with dynamic dictionary of Lempel and Ziv.All our algorithms are randomized and they are of the Las Vegas type.Furthermore, they are fast, working in time logarithmic in the input size.Additionally, our algorithms seem suitable for a distributed implementa-