Compressed depth sequences

We show how, given a probability distribution P over a set of size n, in O(n) time we can construct an efficient data structure that stores a code with less than 3 bits redundancy, and takes o(n) bits of space when P consists of o(n/logn) runs of nearly equal probabilities.