Anders Roy Christiansen

collaborators

5 papers

cs.DS2017

Compressed Indexing with Signature Grammars

Anders Roy Christiansen, Mikko Berggren Ettienne

The compressed indexing problem is to preprocess a string $S$ of length $n$ into a compressed representation that supports pattern matching queries. That is, given a string $P$ of…

cs.DS2017

Fast Dynamic Arrays

Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne +1

We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of $n$ elements supporting access in time $O (1)$ and insertion and delet…

cs.DS2017

Succinct Partial Sums and Fenwick Trees

Philip Bille, Anders Roy Christiansen, Nicola Prezza +1

We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be ef…

cs.DS2015

Finger Search in Grammar-Compressed Strings

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording +1

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…

cs.DS2015

Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3

Given a static reference string $R$ and a source string $S$ , a relative compression of $S$ with respect to $R$ is an encoding of $S$ as a sequence of references to substrings of $R…