Compressing and Indexing Structured Text

Trees are a fundamental structure in computing. They are used in almost every aspect of modeling and representation for computations like searching for keys, maintaining directories, and representations of parsing or execution traces, to name just a few. One of the latest uses of trees is XML, the de facto format for data storage, integration, and exchange over the Internet (see http://​www.​w3.​org/​XML/​). Explicit storage of trees, with one pointer per child as well as other auxiliary information (e.g., label), is often taken as given but can account for the dominant storage cost. Just to have an idea, a simple tree encoding needs at least 16 bytes per tree node: one pointer to the auxiliary information (e.g., node label) plus three node pointers to the parent, the first child, and the next sibling. This large space occupancy may even prevent the processing of medium-sized trees. This entry deals with compressed or succinct storage of trees.