Zobrazeno 1 - 10
of 94
pro vyhledávání: '"Liptak, Zsuzsanna"'
Autor:
Giuliani, Sara, Inenaga, Shunsuke, Lipták, Zsuzsanna, Romana, Giuseppe, Sciortino, Marinella, Urbina, Cristian
A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon for the Burrows-Wheeler Transform (BWT), a string transform at the heart
Externí odkaz:
http://arxiv.org/abs/2404.10426
We consider the problem of maintaining a collection of strings while efficiently supporting splits and concatenations on them, as well as comparing two substrings, and computing the longest common prefix between two suffixes. This problem can be solv
Externí odkaz:
http://arxiv.org/abs/2403.13162
Despite consistently yielding the best compression on repetitive text collections, the Lempel-Ziv parsing has resisted all attempts at offering relevant guarantees on the cost to access an arbitrary symbol. This makes it less attractive for use on co
Externí odkaz:
http://arxiv.org/abs/2403.09893
We present a new data structure for maintaining dynamic permutations, which we call a $\textit{forest of splay trees (FST)}$. The FST allows one to efficiently maintain the cycle structure of a permutation $\pi$ when the allowed updates are transposi
Externí odkaz:
http://arxiv.org/abs/2306.04470
It is known that the exact form of the Burrows-Wheeler-Transform (BWT) of a string collection depends, in most implementations, on the input order of the strings in the collection. Reordering strings of an input collection affects the number of equal
Externí odkaz:
http://arxiv.org/abs/2212.01156
Publikováno v:
Lipt\'ak, Zs., Masillo, F. & Puglisi, S.J. Suffix sorting via matching statistics. Algorithms Mol Biol 19, 11 (2024)
We introduce a new algorithm for constructing the generalized suffix array of a collection of highly similar strings. As a first step, we construct a compressed representation of the matching statistics of the collection with respect to a reference s
Externí odkaz:
http://arxiv.org/abs/2207.00972
Publikováno v:
In Theoretical Computer Science 19 February 2025 1027
Autor:
Cenzato, Davide, Lipták, Zsuzsanna
In recent years, the focus of bioinformatics research has moved from individual sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform (BWT) in string processing, a number of dedicated tools have been devel
Externí odkaz:
http://arxiv.org/abs/2202.13235
Autor:
Boucher, Christina, Cenzato, Davide, Lipták, Zsuzsanna, Rossi, Massimiliano, Sciortino, Marinella
Publikováno v:
In Information and Computation June 2024 298
Autor:
Boucher, Christina, Cenzato, Davide, Lipták, Zsuzsanna, Rossi, Massimiliano, Sciortino, Marinella
Mantaci et al. [TCS 2007] defined the eBWT to extend the definition of the BWT to a collection of strings, however, since this introduction, it has been used more generally to describe any BWT of a collection of strings and the fundamental property o
Externí odkaz:
http://arxiv.org/abs/2106.11191