J. I. Munro

activity

20152017

collaborators

3 papers

cs.DS2017

Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich

We introduce a compressed suffix array representation that, on a text $T$ of length $n$ over an alphabet of size $σ$ , can be built in $O (n)$ deterministic time, within $O (n lo g σ)$ …

cs.DS2016

Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich

We show that the compressed suffix array and the compressed suffix tree of a string $T$ can be built in $O (n)$ deterministic time using $O (n lo g σ)$ bits of space, where $n$ is the…

cs.DS2015

Compressed Data Structures for Dynamic Sequences

J. Ian Munro, Yakov Nekrich

We consider the problem of storing a dynamic string $S$ over an alphabet $Σ = {1, \dots, σ}$ in compressed form. Our representation supports insertions and deletions of symbols…