2018/11/2 18:07

要旨

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

詳細情報

日時 2018/11/28(水) 09:30 - 10:30
URL https://c5dc59ed978213830355fc8978.doorkeeper.jp/events/82672

場所

〒103-0027 東京都中央区日本橋1-4-1 日本橋一丁目三井ビルディング 15階