Results 171 to 180 of about 58,659 (213)
Some of the next articles are maybe not open access.
From Suffix Trees to Suffix Vectors
International Journal of Foundations of Computer Science, 2006We present a first formal setting for suffix vectors that are space economical alternative data structures to suffix trees. We give two linear algorithms for converting a suffix tree into a suffix vector and conversely. We enrich suffix vectors with formulas for counting the number of occurrences of repeated substrings.
Prieur, Elise, Lecroq, Thierry
openaire +3 more sources
Journal of Algorithms, 1998
Summary: We give first the representation of a suffix tree that uses \(n\lg n+ O(n)\) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in \(O(m)\) time, where \(n\) is the size of the text and \(m\) is the length of the pattern.
Munro, J. Ian +2 more
openaire +1 more source
Summary: We give first the representation of a suffix tree that uses \(n\lg n+ O(n)\) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in \(O(m)\) time, where \(n\) is the size of the text and \(m\) is the length of the pattern.
Munro, J. Ian +2 more
openaire +1 more source
Algorithmica, 1996
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Andersson, A. +2 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Andersson, A. +2 more
openaire +2 more sources
ACM Journal of Experimental Algorithmics, 2013
The suffix tree is a very important data structure in string processing, but typical implementations suffer from huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of three (compressed) components: the suffix array, the longest common prefix (LCP)-array and data structures for ...
Simon Gog, Enno Ohlebusch
openaire +1 more source
The suffix tree is a very important data structure in string processing, but typical implementations suffer from huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of three (compressed) components: the suffix array, the longest common prefix (LCP)-array and data structures for ...
Simon Gog, Enno Ohlebusch
openaire +1 more source
REACHABILITY ON SUFFIX TREE GRAPHS
International Journal of Foundations of Computer Science, 2008We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed
Higa, Yasuto +3 more
openaire +2 more sources
1996
A sparse suffix tree is a suffix tree that represents only a subset of the suffixes of the text. This is in contrast to the standard suffix tree that represents all suffixes. By selecting a small enough subset, a sparse suffix tree can be made to fit the available storage, unfortunately at the cost of increased search times.
Juha Kärkkäinen, Esko Ukkonen
openaire +1 more source
A sparse suffix tree is a suffix tree that represents only a subset of the suffixes of the text. This is in contrast to the standard suffix tree that represents all suffixes. By selecting a small enough subset, a sparse suffix tree can be made to fit the available storage, unfortunately at the cost of increased search times.
Juha Kärkkäinen, Esko Ukkonen
openaire +1 more source
Online suffix trees with counts
Data Compression Conference, 2004. Proceedings. DCC 2004, 2004This paper extend Ukkonen's online suffix tree construction algorithm to support substring frequency queries, by adding count fields to the internal nodes of the tree. This has applications in the field of sequential data compression. One major problem is that Ukkonen's online construction algorithm does not maintain explicit end of string markers in ...
Ó Nualláin, B.S., de Rooij, S.
openaire +2 more sources
Journal of the ACM, 2010
Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. This article proposes a new data structure for indexing protein 3-D structures.
openaire +1 more source
Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. This article proposes a new data structure for indexing protein 3-D structures.
openaire +1 more source
Algorithmica, 2007
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kim, Dong Kyue +2 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kim, Dong Kyue +2 more
openaire +2 more sources
Suffix Vector: A Space-Efficient Suffix Tree Representation
2001This paper introduces a new way of representing suffix trees. The basic idea behind the representation is that we are storing the nodes of the tree along with the string itself, thus edge labels can directly be read from the string. The new representation occupies less space than the best-known representation to date in case of English text and program
Krisztián Monostori +2 more
openaire +1 more source