Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Succinct data structure
Résumé
In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a compressed data structure, insofar as the size of the stored or encoded data similarly depends upon the specific content of the data itself.
Suppose that is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:
implicit if it takes bits of space,
succinct if it takes bits of space, and
compact if it takes bits of space.
For example, a data structure that uses bits of storage is compact, bits is succinct, bits is also succinct, and bits is implicit.
Implicit structures are thus usually reduced to storing information using some permutation of the input data; the most well-known example of this is the heap.
Succinct indexable dictionaries, also called rank/select dictionaries, form the basis of a number of succinct representation techniques, including binary trees, -ary trees and multisets, as well as suffix trees and arrays. The basic problem is to store a subset of a universe , usually represented as a bit array where iff An indexable dictionary supports the usual methods on dictionaries (queries, and insertions/deletions in the dynamic case) as well as the following operations:
for .
In other words, returns the number of elements equal to up to position while returns the position of the -th occurrence of .
There is a simple representation which uses bits of storage space (the original bit array and an auxiliary structure) and supports rank and select in constant time.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.