Data Portal @ linkeddatafragments.org

Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Compressed_suffix_array> ?p ?o. }

• Compressed_suffix_array 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 a 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 O(n).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.".
• Compressed_suffix_array wikiPageExternalLink index.shtml.
• Compressed_suffix_array wikiPageExternalLink index.shtml.
• Compressed_suffix_array wikiPageExternalLink indexes.html.
• Compressed_suffix_array wikiPageExternalLink femto.
• Compressed_suffix_array wikiPageExternalLink sdsl-lite.
• Compressed_suffix_array wikiPageID "25296445".
• Compressed_suffix_array wikiPageRevisionID "586157482".
• Compressed_suffix_array hasPhotoCollection Compressed_suffix_array.
• Compressed_suffix_array subject Category:Database_index_techniques.
• Compressed_suffix_array subject Category:String_data_structures.
• Compressed_suffix_array subject Category:Substring_indices.
• Compressed_suffix_array type Ability105616246.
• Compressed_suffix_array type Abstraction100002137.
• Compressed_suffix_array type Arrangement105726596.
• Compressed_suffix_array type Cognition100023271.
• Compressed_suffix_array type DataStructure105728493.
• Compressed_suffix_array type DatabaseIndexTechniques.
• Compressed_suffix_array type Index113851067.
• Compressed_suffix_array type Know-how105616786.
• Compressed_suffix_array type Measure100033615.
• Compressed_suffix_array type Method105660268.
• Compressed_suffix_array type PsychologicalFeature100023100.
• Compressed_suffix_array type Scale113850304.
• Compressed_suffix_array type Standard107260623.
• Compressed_suffix_array type StringDataStructures.
• Compressed_suffix_array type Structure105726345.
• Compressed_suffix_array type SubstringIndices.
• Compressed_suffix_array type SystemOfMeasurement113577171.
• Compressed_suffix_array type Technique105665146.
• Compressed_suffix_array 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 a 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.".
• Compressed_suffix_array label "Compressed suffix array".
• Compressed_suffix_array sameAs m.09glhrq.
• Compressed_suffix_array sameAs Q5157028.
• Compressed_suffix_array sameAs Q5157028.
• Compressed_suffix_array sameAs Compressed_suffix_array.
• Compressed_suffix_array wasDerivedFrom Compressed_suffix_array?oldid=586157482.
• Compressed_suffix_array isPrimaryTopicOf Compressed_suffix_array.