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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n10https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n14https://github.com/simongog/
dbpedia-srhttp://sr.dbpedia.org/resource/
n21https://github.com/femto-dev/
freebasehttp://rdf.freebase.com/ns/
n20http://bowtie-bio.sourceforge.net/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n5https://web.archive.org/web/20120329222807/http:/pizzachili.di.unipi.it/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
n13http://bowtie-bio.sourceforge.net/bowtie2/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_data_structures
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
dbr:Suffix_array
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
dbr:Compressed_data_structure
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
dbr:Compressed_suffix_array
rdf:type
yago:Abstraction100002137 yago:SystemOfMeasurement113577171 yago:DataStructure105728493 yago:Scale113850304 yago:PsychologicalFeature100023100 yago:Arrangement105726596 yago:WikicatDatabaseIndexTechniques yago:Cognition100023271 yago:Structure105726345 yago:Know-how105616786 yago:Standard107260623 yago:Technique105665146 yago:Index113851067 yago:Ability105616246 yago:Measure100033615 yago:WikicatSubstringIndices yago:Method105660268 yago:WikicatStringDataStructures
rdfs:label
Compressed suffix array
rdfs:comment
In computer science, a compressed suffix array is a compressed data structure for pattern matching. Compressed suffix arrays are a general class of data structure that improve on the suffix array. These data structures enable quick search for an arbitrary string with a comparatively small index.
dcterms:subject
dbc:Substring_indices dbc:String_data_structures dbc:Database_index_techniques
dbo:wikiPageID
25296445
dbo:wikiPageRevisionID
1093705380
dbo:wikiPageWikiLink
dbr:Data_structure dbr:Entropy_(information_theory) dbr:Wavelet_Tree dbr:Compressed_data_structure dbc:Substring_indices dbr:Auxiliary_memory dbr:Sequence_alignment dbc:String_data_structures dbr:String_(computer_science) dbr:FM-index dbr:Suffix_Array dbr:Suffix_array dbr:Bioinformatics dbr:Computer_science dbr:Pattern_matching dbc:Database_index_techniques
dbo:wikiPageExternalLink
n5:indexes.html n13:index.shtml n14:sdsl-lite n20:index.shtml n21:femto
owl:sameAs
n10:4iEWA freebase:m.09glhrq dbpedia-sr:Компримовани_суфикс_низа yago-res:Compressed_suffix_array wikidata:Q5157028
dbp:wikiPageUsesTemplate
dbt:Tmath dbt:Short_description
dbo:abstract
In computer science, a compressed suffix array is a compressed data structure for pattern matching. Compressed suffix arrays are a general class of data structure that improve on the suffix array. These data structures enable quick search for an arbitrary string with a comparatively small index. Given a text T of n characters from an alphabet Σ, a compressed suffix array supports searching for arbitrary patterns in T. For an input pattern P of m characters, the search time is typically O(m) or O(m + log(n)). The space used is typically , where is the k-th order empirical entropy of the text T. The time and space to construct a compressed suffix array are normally . The original instantiation of the compressed suffix array solved a long-standing open problem by showing that fast pattern matching was possible using only a linear-space data structure, namely, one proportional to the size of the text T, which takes bits. The conventional suffix array and suffix tree use bits, which is substantially larger. The basis for the data structure is a recursive decomposition using the "neighbor function," which allows a suffix array to be represented by one of half its length. The construction is repeated multiple times until the resulting suffix array uses a linear number of bits. Following work showed that the actual storage space was related to the zeroth-order entropy and that the index supports self-indexing. The space bound was further improved achieving the ultimate goal of higher-order entropy; the compression is obtained by partitioning the neighbor function by high-order contexts, and compressing each partition with a wavelet tree. The space usage is extremely competitive in practice with other state-of-the-art compressors, and it also supports fast pattern matching. The memory accesses made by compressed suffix arrays and other compressed data structures for pattern matching are typically not localized, and thus these data structures have been notoriously hard to design efficiently for use in external memory. Recent progress using geometric duality takes advantage of the block access provided by disks to speed up the I/O time significantly In addition, potentially practical search performance for a compressed suffix array in external-memory has been demonstrated.
prov:wasDerivedFrom
wikipedia-en:Compressed_suffix_array?oldid=1093705380&ns=0
dbo:wikiPageLength
5648
foaf:isPrimaryTopicOf
wikipedia-en:Compressed_suffix_array
Subject Item
dbr:FM-index
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
dbr:Compressed_Suffix_Array
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
dbo:wikiPageRedirects
dbr:Compressed_suffix_array
Subject Item
dbr:Substring_index
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
dbr:Wavelet_Tree
dbo:wikiPageWikiLink
dbr:Compressed_suffix_array
Subject Item
wikipedia-en:Compressed_suffix_array
foaf:primaryTopic
dbr:Compressed_suffix_array