Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Compressed_data_structure> ?p ?o }
Showing triples 1 to 33 of
33
with 100 triples per page.
- Compressed_data_structure abstract "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 entropy of the data being represented. Important examples of compressed data structures include the compressed suffix array and the FM-index, 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.".
- Compressed_data_structure wikiPageID "24757213".
- Compressed_data_structure wikiPageLength "3176".
- Compressed_data_structure wikiPageOutDegree "14".
- Compressed_data_structure wikiPageRevisionID "570642049".
- Compressed_data_structure wikiPageWikiLink Algorithm.
- Compressed_data_structure wikiPageWikiLink Category:Data_structures.
- Compressed_data_structure wikiPageWikiLink Compressed_suffix_array.
- Compressed_data_structure wikiPageWikiLink Computer_science.
- Compressed_data_structure wikiPageWikiLink Data_structure.
- Compressed_data_structure wikiPageWikiLink FM-index.
- Compressed_data_structure wikiPageWikiLink Gzip.
- Compressed_data_structure wikiPageWikiLink Inverted_index.
- Compressed_data_structure wikiPageWikiLink Pattern_matching.
- Compressed_data_structure wikiPageWikiLink Prediction_by_partial_matching.
- Compressed_data_structure wikiPageWikiLink Succinct_data_structure.
- Compressed_data_structure wikiPageWikiLink Suffix_array.
- Compressed_data_structure wikiPageWikiLink Suffix_tree.
- Compressed_data_structure wikiPageWikiLink Theoretical_computer_science.
- Compressed_data_structure wikiPageWikiLinkText "Compressed data structure".
- Compressed_data_structure wikiPageWikiLinkText "compressed data structure".
- Compressed_data_structure subject Category:Data_structures.
- Compressed_data_structure type Datum.
- Compressed_data_structure type Structure.
- Compressed_data_structure comment "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 entropy of the data being represented.".
- Compressed_data_structure label "Compressed data structure".
- Compressed_data_structure sameAs Q5157018.
- Compressed_data_structure sameAs Structure_de_données_compressée.
- Compressed_data_structure sameAs m.0808812.
- Compressed_data_structure sameAs Компресоване_структуре_података.
- Compressed_data_structure sameAs Q5157018.
- Compressed_data_structure wasDerivedFrom Compressed_data_structure?oldid=570642049.
- Compressed_data_structure isPrimaryTopicOf Compressed_data_structure.