Advanced Search
Now showing items 1-10 of 38
Fully functional suffix trees and optimal text searching in BWT-Runs bounded space
(Assoc Computing Machinery, USA, 2020)
(sigma)/w). Within that space, we similarly provide access to arbitrary suffix array, inverse suffix array, and longest common prefix array cells in time O(log(n/r)), and extend these capabilities to full suffix tree functionality, typically in O(log(n1r)) time per...
Protein complex prediction via dense subgraphs and false positive analysis
(Public Library Science, 2017)
define an
inverse traveler function, as follows.
Fig 1. DAPG example. (A) shows a PPI as an undirected graph. (B) shows a PPI network as an adjacency list. (C) shows the DAPG using total order
function ϕ (ID) and (D) shows the DAPG using total order...
function ϕ FREQUENCY. https://doi.org/10.1371/journal.pone.0183460.g001 Protein complex prediction and false positive analysis PLOS ONE | https://doi.org/10.1371/journal.pone.0183460 September 22, 2017 6 / 37 Definition 3 Inverse traveler function...
function ϕ FREQUENCY. https://doi.org/10.1371/journal.pone.0183460.g001 Protein complex prediction and false positive analysis PLOS ONE | https://doi.org/10.1371/journal.pone.0183460 September 22, 2017 6 / 37 Definition 3 Inverse traveler function...
Efficient Fully-Compressed Sequence Representations
(Springer, 2012)
contribution in this article is, on one hand, to show that a particular way to
define the sub-alphabets, according to a quantization of the logarithms of the inverse
probabilities of the characters, achieves o(H0(s) + 1) bits of redundancy per charac-
ter...
function, respectively, supporting direct and inverse applications and in some cases improving upon previous results [6, 7, 38, 47]. We describe further applications to text indexes and binary relations. In particular, an ap- plication of our structure...
function, respectively, supporting direct and inverse applications and in some cases improving upon previous results [6, 7, 38, 47]. We describe further applications to text indexes and binary relations. In particular, an ap- plication of our structure...
Reducing the space requirement of LZ-index
(SPRINGER-VERLAG BERLIN, 2006)
(par, i) + 1 (i.e., the symbol with preorder position i),
which is computed in constant time.
- ids0...n: The array of LZ78 phrase identifiers in preorder. We use the rep-
resentation of Munro et al. [12] for ids such that the inverse permutation ids−1...
to nodes in the new rep- 3 As ancestor(x, y) ≡ rank1(par,x) � rank1(par, y) � rank1(par, x) + subtreesize(par,x) − 1. 4 This data structure ensures that one finds the inverse after following the permutation O(1/�) times. D. Arroyuelo, G. Navarro, and K...
to nodes in the new rep- 3 As ancestor(x, y) ≡ rank1(par,x) � rank1(par, y) � rank1(par, x) + subtreesize(par,x) − 1. 4 This data structure ensures that one finds the inverse after following the permutation O(1/�) times. D. Arroyuelo, G. Navarro, and K...
Top-k Term-Proximity in Succinct Space
(Springer, 2017)
to that of the compressed collection. A CSA
finds the suffix array interval of P [1..p] in time ts(p) and retrieves any cell of the
suffix array or its inverse in time tSA. Hon et al. achieved O(ts(p)+k tSA log
3+ε n)
query time, using O(n/ logε n) bits. Subsequent work...
, ep] of P in time ts(p). It can output any value SA[i], and even of its inverse permutation, SA−1[i], in time tSA. For example, a CSA using nHh(T) + o(n log σ) bits [2] gives ts(p) = O(p) and tSA = O(log 1+� n) for any constant � > 0, where Hh...
, ep] of P in time ts(p). It can output any value SA[i], and even of its inverse permutation, SA−1[i], in time tSA. For example, a CSA using nHh(T) + o(n log σ) bits [2] gives ts(p) = O(p) and tSA = O(log 1+� n) for any constant � > 0, where Hh...
On the approximation ratio of Lempel-Ziv parsing
(Springer Verlag, 2018)
in T
of the ith smallest suffix of T in lexicographic order.
The inverse permutation of SA, ISA[1 . . . n], is called the inverse suffix array,
so that ISA[j] is the lexicographical position of the suffix T [j . . . n] among the
suffixes of T .
The Burrows...
Space-efficient construction of LZ-index
(SPRINGER-VERLAG BERLIN, 2005)
closing parenthesis.
Once the LZTrie is built we free the space of the normal trie, and build Node. This
is just an array with the n nodes of LZTrie, using �logn� bits for each. It is built as the
inverse of permutation ids.
To construct RevTrie we...
, rids. Empty unary nodes are removed only at this step. Finally, we build the normal reverse trie and build RNode as the inverse permutation of rids. In the experiments of the original LZ-index [26,25], the largest extra space needed to build LZTrie...
, rids. Empty unary nodes are removed only at this step. Finally, we build the normal reverse trie and build RNode as the inverse permutation of rids. In the experiments of the original LZ-index [26,25], the largest extra space needed to build LZTrie...
Compressed Full-Text Indexes
(ASSOC COMPUTING MACHINERY, 2007-04)
and Vitter 2000; Sadakane 2000]
builds on the inverse of function LF(i). This inverse function, denoted �, maps suf-
fix TA[i],n to suffix TA[i]+1,n, and thus it enables scanning the text in forward direc-
tion, from left to right. Continuing our example, we...
computed LF(6) = 17, and thus the inverse is �(17) = 6. Mapping � has the simple definition �(i) = i′ such that A[i′] = (A[i] mod n) + 1. This is illustrated in Figure 6. While the Occ(c, i) function demonstrated the backward search paradigm, the inverse...
computed LF(6) = 17, and thus the inverse is �(17) = 6. Mapping � has the simple definition �(i) = i′ such that A[i′] = (A[i] mod n) + 1. This is illustrated in Figure 6. While the Occ(c, i) function demonstrated the backward search paradigm, the inverse...
Colored range queries and document retrieval
(2013)
structures to compute the pattern’s frequency in each document,
increasing the time bound to O(search(m)+ ndoc(lookup(n)+ log log ndoc)) (assuming lookup(n) is also the time to find
CSA−1[q], where CSA−1 denotes the inverse permutation of A).
Hon et al. [32...
). In rows 6 and 7, g is the size (in bits) of a given context-free grammar generating S and only S. In rows 4 and 6, α(·) is the inverse Ackermann function. Rows 9 and 10 only solve queries of the form rankS[i](S, i). Row Source Space (in bits) tacc tenum...
). In rows 6 and 7, g is the size (in bits) of a given context-free grammar generating S and only S. In rows 4 and 6, α(·) is the inverse Ackermann function. Rows 9 and 10 only solve queries of the form rankS[i](S, i). Row Source Space (in bits) tacc tenum...