Center for Advanced Intelligence Project

Title: Dynamic compressed string representations supporting random access

Abstract:
In this talk I will present a scheme for storing a dynamic string S in compressed form, while permitting following operations directly on the compressed representation of S: (a) access a substring of S; (b) replace, insert or delete a symbol in S; (c) count how many occurrences of a given symbol appear in any given prefix of S (called rank operation); and (d) locate the position of the i-th occurrence of a symbol inside S (called select operation). An important application of this result is in Compressed Random Access Memory (CRAM), where one can represent the memory of a computer in compressed form while being able to support random access efficiently (without decompressing).

These results extend or improve the bounds of previous work by Ferragina and Venturini [TCS, 2007], Jansson et al. [ICALP, 2012], and Nekrich and Navarro [SODA, 2013].