1 citations · 3 across the 6 of their papers we have counts for
4 papers · 1 filter
A New Algorithm for Building Alphabetic Minimax Trees
Travis Gagie
We show how to build an alphabetic minimax tree for a sequence (W = w_1, >..., w_n) of real weights in (O (n d \log \log n)) time, where is the number of distinct integers (\lc…
Bounds for Compression in Streaming Models
Travis Gagie
Compression algorithms and streaming algorithms are both powerful tools for dealing with massive data sets, but many of the best compression algorithms -- e.g., those based on the…
Empirical entropy in context
Travis Gagie
We trace the history of empirical entropy, touching briefly on its relation to Markov processes, normal numbers, Shannon entropy, the Chomsky hierarchy, Kolmogorov complexity, Ziv-…
A nearly tight memory-redundancy trade-off for one-pass compression
Travis Gagie
Let be a string of length over an alphabet of constant size and let and be constants with (1 \geq c \geq 0) and (ε> 0). Using (O (n)) time, (O (n^c)) bits of me…