Logowanie

Języki

  • Polski
  • English

Seminarium ZZOiA: 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].

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS