This HTML5 document contains 50 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbr:Compressed_data_structure

rdf:type

yago:DataStructure105728493 yago:WikicatDataStructures yago:Structure105726345 yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:PsychologicalFeature100023100

rdfs:label

Compressed data structure Structure de données compressée

rdfs: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. Le terme structure de données compressée (en anglais : compressed data structure) apparaît dans les domaines informatiques que sont l'algorithmique, les structures de données, et l'informatique théorique. Il désigne une structure de données dont les opérations sont à peu près aussi rapides que celles sur les structures de données conventionnelles pour un problème, mais dont la taille est substantiellement plus petite. En général, la taille d'une structure de données compressée dépend fortement de l’entropie des données à représenter.

owl:sameAs

dbpedia-sr:Компресоване_структуре_података n5:4hsF6 dbpedia-fr:Structure_de_données_compressée n19:0808812 wd:Q5157018 yago-res:Compressed_data_structure dbr:Compressed_data_structure

foaf:topic

dbr:Compressed_suffix_array dbr:Succinct_data_structure dbr:Straight-line_grammar wikipedia-en:Compressed_data_structure dbr:List_of_computer_scientists n20:this dbr:Compressed_data_structures

wdrs:describedby

n11:Data_structures

dct:subject

dbc:Data_structures

dbo:wikiPageID

24757213

dbo:wikiPageRevisionID

1053967243

dbo:wikiPageWikiLink

dbr:Succinct_data_structure dbr:Data_structures dbr:Pattern_matching dbr:Theoretical_computer_science dbr:FM-index dbr:Compressed_suffix_array dbc:Data_structures dbr:Prediction_by_Partial_Matching dbr:Suffix_array dbr:Computer_science dbr:Algorithms dbr:Suffix_tree dbr:Gzip dbr:Inverted_index

foaf:isPrimaryTopicOf

wikipedia-en:Compressed_data_structure

prov:wasDerivedFrom

n14:0

dbo: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. Le terme structure de données compressée (en anglais : compressed data structure) apparaît dans les domaines informatiques que sont l'algorithmique, les structures de données, et l'informatique théorique. Il désigne une structure de données dont les opérations sont à peu près aussi rapides que celles sur les structures de données conventionnelles pour un problème, mais dont la taille est substantiellement plus petite. En général, la taille d'une structure de données compressée dépend fortement de l’entropie des données à représenter.

dbo:wikiPageLength

3370

dbp:wikiPageUsesTemplate

dbt:Citation_needed dbt:Example_needed