Carlos Ochoa

Carlos Ochoa

Auto-generated profile, based on publicly available information

Carlos Ochoa

Universidad de Chile

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 December 2020 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Gonzalo NavarroGonzalo Navarro
Gonzalo Navarro
COCarlos Ochoa
Carlos Ochoa
Nicola PrezzaNicola Prezza
Nicola Prezza
Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is b, the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing b is NP-complete, a popular gold standard is z, the number of phrases in the Lempel-Ziv parse of the text, which is computed in linear time and yields the least number of phrases when those can be copied only from the left. Almost nothing has been known for decades about the approximation ratio of z with respect to b. In this paper we prove that z = O(b log(n/b)), where n is the text length. We also show that the bound is tight as a function of n, by exhibiting a text family where z = Ω(b log n). Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating b with r, the number of equal-letter runs in the Burrows-Wheeler transform of the text. We continue by observing that Lempel-Ziv is just one particular case of greedy parses–meaning that it obtains the smallest parse by scanning the text and maximizing the phrase length at each step–, and of ordered parses–meaning that phrases are larger than their sources under some order. As a new example of ordered greedy parses, we introduce lexicographical parses, where phrases can only be copied from lexicographically smaller text locations. We prove that the size v of the optimal lexicographical parse is also obtained greedily in O(n) time, that v = O(b log(n=b)), and that there exists a text family where v = Ω(b log n). Interestingly, we also show that v = O(r) because r also induces a lexicographical parse, whereas z = Ω(r log n) holds on some text families. We obtain some results on parsing complexity and size that hold on some general classes of greedy ordered parses. In our way, we also prove other relevant bounds between compressibility measures, especially with those related to smallest grammars of various types generating (only) the text.

20 September 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
COCarlos Ochoa
Carlos Ochoa
Gonzalo NavarroGonzalo Navarro
Gonzalo Navarro
Irreducible grammars are a class of context-free grammars with well-known representatives, such as REPAIR (with a few tweaks), LONGEST MATCH, GREEDY, and SEQUENTIAL. We show that a grammar-based compression method described by Kieffer and Yang (2000) is upper bounded by the high-order empirical entropy of the string when the underlying grammar is irreducible. Specifically, given a string S over an alphabet of size σ, we prove that if the underlying grammar is irreducible, then the length of the binary code output by this grammar-based compression method is bounded by |S|Hk(S)+o(|S| log σ) for any k ∈ o(logσ |S|), where Hk(S) is the k-order empirical entropy of S. This is the first bound encompassing the whole class of irreducible grammars in terms of the high-order empirical entropy, with coefficient 1.

27 October 2015 in Journal of Combinatorial Optimization
Verified
Journal Article
Closed access
LCL. E. Caraballo
L. E. Caraballo
COC. Ochoa
C. Ochoa
PPP. Pérez-Lantero
P. Pérez-Lantero
JRJ. Rojas-Ledesma
J. Rojas-Ledesma

1 June 2017 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
JDJosé Miguel Díaz-Báñez
José Miguel Díaz-Báñez
MLM.A. Lopez
M.A. Lopez
COC. Ochoa
C. Ochoa
PPP. Pérez-Lantero
P. Pérez-Lantero

26 February 2015 in Graphs and Combinatorics
Verified
Journal Article
Closed access
PDF file
OAO. Aichholzer
O. Aichholzer
LCL. E. Caraballo
L. E. Caraballo
JDJosé Miguel Díaz-Báñez
José Miguel Díaz-Báñez
RFR. Fabila-Monroy
R. Fabila-Monroy
COC. Ochoa
C. Ochoa
PNP. Nigsch
P. Nigsch

1 September 2020 in Theoretical Computer Science
Verified
Journal Article
Closed access
Travis GagieTravis Gagie
Travis Gagie
MHMeng He
Meng He
GNGonzalo Navarro
Gonzalo Navarro
COCarlos Ochoa
Carlos Ochoa