The term compressed data structure arises in the computer science subfields of algorithms, data structures, and theoretical computer science. It refers to a data structure whose operations are roughly as fast as those of a conventional data structure for the problem, but whose size can be substantially smaller. The size of the compressed data structure is typically highly dependent upon the information entropy of the data being represented.
Important examples of compressed data structures include the compressed suffix array[1][2] and the FM-index,[3] both of which can represent an arbitrary text of characters T for pattern matching. Given any input pattern P, they support the operation of finding if and where P appears in T. The search time is proportional to the sum of the length of pattern P, a very slow-growing function of the length of the text T, and the number of reported matches. The space they occupy is roughly equal to the size of the text T in entropy-compressed form, such as that obtained by Prediction by Partial Matching or gzip. Moreover, both data structures are self-indexing, in that they can reconstruct the text T in a random access manner, and thus the underlying text T can be discarded. In other words, they simultaneously provide a compressed and quickly searchable representation of the text T. They represent a substantial space improvement over the conventional suffix tree and suffix array, which occupy many times more space than the size of T. They also support searching for arbitrary patterns, as opposed to the inverted index, which can support only word-based searches. In addition, inverted indexes do not have the self-indexing feature.
An important related notion is that of a succinct data structure, which uses space roughly equal to the information-theoretic minimum, which is a worst-case notion of the space needed to represent the data. In contrast, the size of a compressed data structure depends upon the particular data being represented. When the data are compressible, as is often the case in practice for natural language text, the compressed data structure can occupy space very close to the information-theoretic minimum, and significantly less space than most compression schemes.[example needed][citation needed]
^Grossi, Roberto; Vitter, Jeffrey Scott (January 2005). "Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching" (PDF). SIAM Journal on Computing. 35 (2): 378–407. doi:10.1137/S0097539702402354. hdl:1808/18962.
^R. Grossi, A. Gupta, and J. S. Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, January 2003, 841-850.
^Ferragina, P.; Manzini, G. (2000). "Opportunistic data structures with applications". Proceedings 41st Annual Symposium on Foundations of Computer Science. pp. 390–398. doi:10.1109/SFCS.2000.892127. ISBN 0-7695-0850-2. S2CID 12530704.
and 21 Related for: Compressed data structure information
The term compresseddatastructure arises in the computer science subfields of algorithms, datastructures, and theoretical computer science. It refers...
that of a compresseddatastructure, insofar as the size of the stored or encoded data similarly depends upon the specific content of the data itself. Suppose...
Brodal queue In these datastructures each tree node compares a bit slice of key values. Radix tree Suffix tree Suffix array Compressed suffix array FM-index...
science, a compressed suffix array is a compresseddatastructure for pattern matching. Compressed suffix arrays are a general class of datastructure that...
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring...
digital tree or prefix tree, is a type of k-ary search tree, a tree datastructure used for locating specific keys from within a set. These keys are most...
In mechanics, compressive strength (or compression strength) is the capacity of a material or structure to withstand loads tending to reduce size (as...
minerals and chemicals. Abstract structures include datastructures in computer science and musical form. Types of structure include a hierarchy (a cascade...
coding format and can be uncompressed, or compressed to reduce the file size, often using lossy compression. The data can be a raw bitstream in an audio coding...
lossless data compression algorithms which operate by searching for matches between the text to be compressed and a set of strings contained in a data structure...
Compressed air is air kept under a pressure that is greater than atmospheric pressure. Compressed air is an important medium for transfer of energy in...
compressed representations, operations are performed directly on the compressed representation, i.e. without decompression. Similar datastructures include...
A quadtree is a tree datastructure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are...
efficient access and matrix operations, such as CSR (Compressed Sparse Row) or CSC (Compressed Sparse Column). DOK consists of a dictionary that maps...
Computing approximate quantiles from data arriving from a stream can be done efficiently using compresseddatastructures. The most popular methods are t-digest...
is a datastructure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams...
PCM or ITU-T G.711 μ-law PCM for uncompressed audio data, and IMA-ADPCM for compressed audio data). It does not support JPEG 2000 or GIF encoded images...
are used to collect multiple data files together into a single file for easier portability and storage, or simply to compress files to use less storage space...
digital data stream (a codec) that encodes or decodes audio. In software, an audio codec is a computer program implementing an algorithm that compresses and...
the compressed contents of a compressed drive was stored in a single file implied the possibility of a user accidentally deleting all of their data by...
Global Information