  We introduce a new compression scheme for labeled trees based on top trees.
Our compression scheme is the first to simultaneously take advantage of
internal repeats in the tree (as opposed to the classical DAG compression that
only exploits rooted subtree repeats) while also supporting fast navigational
queries directly on the compressed representation. We show that the new
compression scheme achieves close to optimal worst-case compression, can
compress exponentially better than DAG compression, is never much worse than
DAG compression, and supports navigational queries in logarithmic time.
