30 citations · 82 across the 38 of their papers we have counts for
4 papers · 1 filter
Efficient Fully-Compressed Sequence Representations
Jeremy Barbay, Francisco Claude, Travis Gagie +2
We present a data structure that stores a sequence over alphabet in $n\Ho(s) + o(n)(\Ho(s){+}1)$ bits, where $\Ho(s)$ is the zero-order entropy of . This stru…
Tight Bounds for Online Stable Sorting
Travis Gagie, Yakov Nekrich
Although many authors have considered how many ternary comparisons it takes to sort a multiset of size , the best known upper and lower bounds still differ by a term linear…
Data Structures for Approximate Range Counting
Yakov Nekrich
We present new data structures for approximately counting the number of points in orthogonal range. There is a deterministic linear space data structure that supports updates in O(…
Fast and Compact Prefix Codes
Travis Gagie, Gonzalo Navarro, Yakov Nekrich
It is well-known that, given a probability distribution over characters, in the worst case it takes (Θ(n \log n)) bits to store a prefix code with minimum expected codeword len…