Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Urbina, Cristian"'
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
It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We generalize this proof to a general class of grammars we call Gener
Externí odkaz:
http://arxiv.org/abs/2404.07057
Detecting and measuring repetitiveness of strings is a problem that has been extensively studied in data compression and text indexing. However, when the data are structured in a non-linear way, like in the context of two-dimensional strings, inheren
Externí odkaz:
http://arxiv.org/abs/2404.07030
Autor:
Navarro, Gonzalo, Urbina, Cristian
We explore an extension to straight-line programs (SLPs) that outperforms, for some text families, the measure $\delta$ based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness (which are crucial in are
Externí odkaz:
http://arxiv.org/abs/2402.09232
It was recently proved that any SLP generating a given string $w$ can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We show that this result also holds for RLSLPs, which are SLPs extended with run-length r
Externí odkaz:
http://arxiv.org/abs/2206.13027
Autor:
Navarro, Gonzalo, Urbina, Cristian
An L-system (for lossless compression) is a CPD0L-system extended with two parameters $d$ and $n$, which determines unambiguously a string $w = \tau(\varphi^d(s))[1:n]$, where $\varphi$ is the morphism of the system, $s$ is its axiom, and $\tau$ is i
Externí odkaz:
http://arxiv.org/abs/2206.01688
Autor:
Navarro, Gonzalo, Urbina, Cristian
The size $b$ of the smallest bidirectional macro scheme, which is arguably the most general copy-paste scheme to generate a given sequence, is considered to be the strictest reachable measure of repetitiveness. It is strictly lower-bounded by measure
Externí odkaz:
http://arxiv.org/abs/2105.13595
Autor:
Navarro, Gonzalo, Urbina, Cristian
In order to use them for compression, we extend L-systems (without ε-rules) with two parameters d and n, and also a coding τ, which determines unambiguously a string w = τ(φ^d(s))[1:n], where φ is the morphism of the system, and s is its axiom.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e514cfad93cc2d90f959745084f28cd6
Morphisms are widely studied combinatorial objects that can be used for generating infinite families of words. In the context of Information theory, injective morphisms are called (variable length) codes. In Data compression, the morphisms, combined
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::40c05defe104123912d1493b72c78def
Autor:
Urbina, Cristian
Th. 3e cycle--Phys. nucl.--Paris 11--Orsay, 1977. N°: 2343.
Externí odkaz:
http://catalogue.bnf.fr/ark:/12148/cb360680262