2 grudnia 2015 13:49
Seminarium ZZOiAA: Paweł Gawrychowski o "Approximating LZ77 via Small-Space Multiple-Pattern Matching".
Na seminarium ZZOiAA w dniu 29.X.2015 o godz. 12:15 Paweł Gawrychowski opowie o wspólnej pracy z Johannesem Fischerem, Travisem Gagie oraz Tomaszem Kociumaką (http://arxiv.org/abs/1504.06647).
Streszczenie:
We generalize the well-known Karp-Rabin string matching to handle multiple patterns in O(nlogn+m) time and O(s) space, where n is the length of the text and m is the total length of the s patterns, returning correct answers with high probability. As a prime application of our algorithm, we show how to approximate the LZ77 parse of a string of length n. If the optimal parse consists of z phrases, using only O(z) working space we can return a parse consisting of at most (1+ε)z phrases in O(1/ε n logn) time, for any ε∈(0,1].