The search functionality is under construction.

The search functionality is under construction.

Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, **rank** and **select**, are commonly used. In this paper we propose two implementations supporting **rank** and **select** in constant time for non-compressed bit strings. One uses *O*(*n* log log *n* / *n*+*O*(*n* log log *n* / log *n*) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.

- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.10 pp.2025-2033

- Publication Date
- 2009/10/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.E92.D.2025

- Type of Manuscript
- PAPER

- Category
- Algorithm Theory

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Joong Chae NA, Ji Eun KIM, Kunsoo PARK, Dong Kyue KIM, "Fast Computation of Rank and Select Functions for Succinct Representation" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 10, pp. 2025-2033, October 2009, doi: 10.1587/transinf.E92.D.2025.

Abstract: Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, **rank** and **select**, are commonly used. In this paper we propose two implementations supporting **rank** and **select** in constant time for non-compressed bit strings. One uses *O*(*n* log log *n* / *n*+*O*(*n* log log *n* / log *n*) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.2025/_p

Copy

@ARTICLE{e92-d_10_2025,

author={Joong Chae NA, Ji Eun KIM, Kunsoo PARK, Dong Kyue KIM, },

journal={IEICE TRANSACTIONS on Information},

title={Fast Computation of Rank and Select Functions for Succinct Representation},

year={2009},

volume={E92-D},

number={10},

pages={2025-2033},

abstract={Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, **rank** and **select**, are commonly used. In this paper we propose two implementations supporting **rank** and **select** in constant time for non-compressed bit strings. One uses *O*(*n* log log *n* / *n*+*O*(*n* log log *n* / log *n*) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.

keywords={},

doi={10.1587/transinf.E92.D.2025},

ISSN={1745-1361},

month={October},}

Copy

TY - JOUR

TI - Fast Computation of Rank and Select Functions for Succinct Representation

T2 - IEICE TRANSACTIONS on Information

SP - 2025

EP - 2033

AU - Joong Chae NA

AU - Ji Eun KIM

AU - Kunsoo PARK

AU - Dong Kyue KIM

PY - 2009

DO - 10.1587/transinf.E92.D.2025

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E92-D

IS - 10

JA - IEICE TRANSACTIONS on Information

Y1 - October 2009

AB - Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, **rank** and **select**, are commonly used. In this paper we propose two implementations supporting **rank** and **select** in constant time for non-compressed bit strings. One uses *O*(*n* log log *n* / *n*+*O*(*n* log log *n* / log *n*) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.

ER -