기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
Dynamic Compressed Representation of Texts with Rank/Select
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • Dynamic Compressed Representation of Texts with Rank/Select
  • Dynamic Compressed Representation of Texts with Rank/Select
저자명
Lee. Sun-Ho,Park. Kun-Soo
간행물명
Journal of computing science and engineering
권/호정보
2009년|3권 1호|pp.15-26 (12 pages)
발행정보
한국정보과학회
파일정보
정기간행물|ENG|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

Given an n-length text T over a $sigma$-size alphabet, we present a compressed representation of T which 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 bound nH(T) bits for any algorithm to compress T of n log $sigma$ bits. Our representation takes this entropy bound of T, i.e., nH(T) $leq$ n log $sigma$ bits, and an additional bits less than the text size, i.e., o(n log $sigma$) + O(n) bits. In compressed space of nH(T) + o(n log $sigma$) + O(n) bits, our representation supports O(log n) time queries for a log n-size alphabet and its extension provides O(($1+frac{{log};{sigma}}{{log};{log};n}$) log n) time queries for a $sigma$-size alphabet.