  Succinct data structures give space-efficient representations of large
amounts of data without sacrificing performance. They rely one cleverly
designed data representations and algorithms. We present here the formalization
in Coq/SSReflect of two different tree-based succinct representations and their
accompanying algorithms. One is the Level-Order Unary Degree Sequence, which
encodes the structure of a tree in breadth-first order as a sequence of bits,
where access operations can be defined in terms of Rank and Select, which work
in constant time for static bit sequences. The other represents dynamic bit
sequences as binary balanced trees, where Rank and Select present a low
logarithmic overhead compared to their static versions, and with efficient
insertion and deletion. The two can be stacked to provide a dynamic
representation of dictionaries for instance. While both representations are
well-known, we believe this to be their first formalization and a needed step
towards provably-safe implementations of big data.
