Get-Together for String Algorithms Researchers in Helsinki

Tapahtuman tyyppi: 
23.02.2012 - 16:15 - 18:00
Travis Gagie
Exactum B119

The program consists of a talk by Travis Gagie (Aalto University):

Title: A Faster Grammar-Based Self-Index

Authors: Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and Simon J. Puglisi

To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on straight-line programs and LZ77. In this paper we show how, given a balanced straight-line program for a string S[1..n] whose LZ77 parse consists of z phrases, we can add O(z log log z) words and obtain a compressed self-index for S such that, given a pattern P[1..m], we can list the occ occurrences of P in S in O(m^2 + (m + occ) log log n) time. All previous self-indexes are either larger or slower in the worst case.


16.02.2012 - 10:22 Leena Salmela
16.02.2012 - 10:22 Leena Salmela