La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Fast Computation of Rank and Select Functions for Succinct Representation Calcul rapide des fonctions de classement et de sélection pour une représentation succincte

Joong Chae NA, Ji Eun KIM, Kunsoo PARK, Dong Kyue KIM

  • Vues en texte intégral

    0

  • Citer

Résumé:

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 / ) les morceaux d'espace supplémentaire et les autres utilisations n+O(n journal journal n / enregistrer n) des morceaux d'espace supplémentaire dans le pire des cas. Le premier est plutôt un algorithme théorique et le second est un algorithme pratique qui fonctionne plus rapidement et utilise moins d'espace dans la pratique.

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.10 pp.2025-2033
Date de publication
2009/10/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E92.D.2025
Type de manuscrit
PAPER
Catégories
Théorie des algorithmes

Auteurs

Mots-clés

Table des matières