JCSE, vol. 3, no. 1, pp.15-26, 2009

DOI:

Dynamic Compressed Representation of Texts with Rank/Select

Sunho Lee, Kunsoo Park
School of Computer Science and Engineering, Seoul National University, Korea

Abstract: Given an n-length text T over a σ-size alphabet, we present a compressed representation of Twhich supports retrieving queries of rank/select/access and updating queries of insert/delete.For a measure of compression, we use the empirical entropy H(T), which defines a lower boundnH(T) bits for any algorithm to compress T of nlogσ bits. Our representation takes thisentropy bound of T, i.e., nH(T)≤nlogσ bits, and an additional bits less than the text size, i.e.,o(nlogσ)+O(n) bits. In compr

Keyword: No keyword

Full Paper:   121 Downloads, 4005 View