Results 171 to 180 of about 6,253 (207)
Some of the next articles are maybe not open access.
International Journal of Foundations of Computer Science, 2009
We introduce the VST (virtual suffix tree), an efficient data structure for suffix trees and suffix arrays. Starting from the suffix array, we construct the suffix tree, from which we derive the virtual suffix tree. Later, we remove the intermediate step of suffix tree construction, and build the VST directly from the suffix array. The VST provides the
Jie Lin +2 more
openaire +1 more source
We introduce the VST (virtual suffix tree), an efficient data structure for suffix trees and suffix arrays. Starting from the suffix array, we construct the suffix tree, from which we derive the virtual suffix tree. Later, we remove the intermediate step of suffix tree construction, and build the VST directly from the suffix array. The VST provides the
Jie Lin +2 more
openaire +1 more source
Tight upper and lower bounds on suffix tree breadth [PDF]
Theoretical Computer Science, 2021 The suffix tree — the compacted trie of all the suffixes of a string — is the most important and widely-used data structure in string processing. We consider a natural combinatorial question about suffix trees: for a string S of length n, how many nodes ...
Simon Puglisi +2 more
exaly +3 more sources
Algorithmica, 1996
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Arne Andersson +2 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Arne Andersson +2 more
openaire +2 more sources
A suffix tree approach to anti-spam email filtering [PDF]
Machine Learning, 2006 We present an approach to email filtering based on the suffix tree data structure. A method for the scoring of emails using the suffix tree is developed and a number of scoring and score normalisation functions are tested.
Boris Mirkin +2 more
exaly +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
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
Yasuto Higa +3 more
openaire +3 more sources
A Note on the Height of Suffix Trees
SIAM Journal on Computing, 1992Summary: Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities \(p_ i\), and let \(H_ n\) be the height of the suffix tree constructed from the first \(n\) suffixes of this word.
Devroye, Luc +2 more
openaire +2 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.
J. Ian Munro +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.
J. Ian Munro +2 more
openaire +1 more source
Data Compression Conference (DCC'06), 2006
A close inspection of Fiala and Green's implementation of Ziv-Lempel'77 dictionary compression method reveals a surprising inefficiency. The match they are searching for from the root down the suffix tree can be obtained for free from the suffix tree construction algorithm!
openaire +1 more source
A close inspection of Fiala and Green's implementation of Ziv-Lempel'77 dictionary compression method reveals a surprising inefficiency. The match they are searching for from the root down the suffix tree can be obtained for free from the suffix tree construction algorithm!
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