November 2, 2018 18:07


Title: Dynamic compressed string representations supporting random access

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].

More Information

Date November 28, 2018 (Wed) 09:30 - 10:30


〒103-0027 Nihonbashi 1-chome Mitsui Building, 15th floor, 1-4-1 Nihonbashi,Chuo-ku, Tokyo