Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach

TitleRandomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach
Publication TypeTechnical Report
Year of Publication1996
AuthorsGasieniec, L., Karpinski M., Plandowski W., & Rytter W.
Other Numbers1031
Abstract

Denote by LZ(w) the coded form of a string w produced by Lempel-Ziv encoding algorithm. We consider several classical algorithmic problems for texts in the compressed setting. The first of them is the equality-testing: given LZ(w) and integers i, j, k test the equality: w[i ... i+k] = w[j ... j+k]. We give a simple and efficient randomized algorithm for this problem using the finger-printing idea. The equality testing is reduced to the equivalence of certain context-free grammars generating single strings. The equality-testing is the bottleneck in other algorithms for compressed texts. We relate the time complexity of several classical problems for texts to the complexity Eq(n) of equality-testing. Assume n = |LZ(T)|, m = |LZ(P)| and U = |T|. Then we can compute the compressed representations of the sets of occurrences of P in T, periods of T, palindromes of T, and squares of T respectively in times O(n log^2 U * Eq(m) + n^2 log U), O(n log^2 U * Eq(n) + n^2 log U), O(n log^2 U * Eq(n) + n^2 log U) and O(n^2 log^3 U * Eq(n) + n^3 log^2 U), where Eq(n) = O(n log log n). The randomization improves considerably upon the known deterministic algorithms.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-021.pdf
Bibliographic Notes

ICSI Technical Report TR-96-021

Abbreviated Authors

L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter

ICSI Publication Type

Technical Report