Sorry, you need to enable JavaScript to visit this website.

Given a string S over an alphabet of size σ, we consider practical implementations of extended compressed RAM on S, which supports access, replace, insert, and delete operations on S while maintaining S in compressed form. In this paper, we proposed two implementations where each of them is based on the compressed RAM of Jansson et al. [ICALP 2012], and Grossi et al. [ICALP 2013], respectively. Experimental results show that our implementations support the operations efficiently while keeping the space proportional to the entropy of the input during the updates.

In this paper we consider the problem of storing sequences of symbols in
a compressed format, while supporting random access to the symbols without
decompression. Although this is a well-studied problem when the data is
textual, the kind of sequences we look at are not textual, and we argue
that traditional compression methods used in the text algorithms community
(such as compressors targeting $k$-th order empirical entropy) do not
perform as well on these sequential data, and simpler methods such

We consider the problem of compact representation of graphs with small bandwidth as well as graphs with small treedepth. These parameters capture structural properties of graphs that come in useful in certain applications.

Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ, a keyword dictionary is a data structure built on K that provides locate, prefix search, and update operations on K. Under the assumption that α = w / lg σ characters fit into a single machine word w, we propose a keyword dictionary that represents K in n lg σ + O(k lg n) bits of space, supporting all operations in O(m / α + lg α) expected time on an input string of length m in the word RAM model.