The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
La représentation succincte est une méthode efficace en termes d'espace pour représenter n objets discrets en utilisant un espace proche de la limite inférieure de la théorie de l'information. Afin d'accéder directement au ième objet de structures de données succinctement représentées en temps constant, deux fonctions fondamentales, classer et Sélectionner, sont couramment utilisés. Dans cet article, nous proposons deux implémentations prenant en charge classer et Sélectionner en temps constant pour les chaînes de bits non compressées. On utilise O(n journal journal n /
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.
Copier
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 /
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.2025/_p
Copier
@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 /
keywords={},
doi={10.1587/transinf.E92.D.2025},
ISSN={1745-1361},
month={October},}
Copier
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 /
ER -