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

JCSE, vol. 3, no. 1, pp.15-26, March, 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:   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: http://jcse.kiise.org    Email: office@kiise.org