Call for Papers
About the Journal
Editorial Board
Publication Ethics
Instructions for Authors
Current Issue
Back Issues
Search for Articles

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


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:   98 Downloads, 3346 View

ⓒ Copyright 2010 KIISE – All Rights Reserved.    
Korean Institute of Information Scientists and Engineers (KIISE)   #401 Meorijae Bldg., 984-1 Bangbae 3-dong, Seo-cho-gu, Seoul 137-849, Korea
Phone: +82-2-588-9240    Fax: +82-2-521-1352    Homepage:    Email: