Algorithm Science Series, Mathematical Techniques Editions, Vol. 8 Kanketsu-Data Kozo (Succinct Data Structures)

This is a textbook on succinct data structures, a type of data structures, which are used for creating computer programs. Succinct data structures allow searches and other processing tasks to be carried out while the data is in a compressed form. These are beneficial data structures that enable efficient processing of massive amounts of data. With the traditional compression methods, one is unable to use the data in a compressed form. Such data needs to be reconstituted before it can be used; thus, the same amount of computer memory as used before the compression becomes necessary. The succinct data structure allows for restoration of only the requested data portions, thereby, enabling efficient processing while the data remains compressed. In the case of mass data, a data structure called an “index” is sometimes added for high-speed data searches. Ordinarily, this data structure is large, sometimes larger than the original data; thus, necessitating index compression. The index compression can also be performed with a succinct data structure.
 
This book includes representative succinct data structures, explanation on these structures, and theoretical consequences. For data structures with identical functions, I have introduced a more refined and easier-to-understand structure, which was developed later, rather than a basic data structure that was proposed earlier. In addition, I have also introduced a rigorous proof of its theorem. Certainly, if one’s task is limited to writing a program, then it is perfectly acceptable not to understand its related proofs. However, in such a case, one is limited to using a previously existing library, and if the operations you want to perform is not supported by the program, then, it cannot be executed. Here, you will be required to create a new data structure by yourself, and for this, understanding its proof becomes essential. The interested readers are strongly encouraged to develop their own new succinct data structures.
 
As for the history of succinct data structures, we revisit 1989, a year that saw proposals of bit vectors, tree structures, and graph structures. In the year 2000, much of the research was performed after the proposal of a data structure for character-string searches. Especially, the Burrows-Wheeler (BW) transform of 2000 (Chapter 8 of the book) and the wavelet tree of 2003 (Chapter 4 of the book), which can be called as two of the most important succinct data structures, are widely used even today. In particular, the succinct data structure is now the predominant structure that is used in DNA-sequence searching. Chapter 3 of this book explains the most basic succinct data structure: bit vectors. Succinct data structures in other chapters are built using it as a building block. The book is written in such a way that it will enable the readers to understand the dependencies between the data structures. The readers of this book will, thus, be able to gain a bird’s-eye overview of the succinct data structure.
 

(Written by SADAKANE Kunihiko, Professor, Graduate School of Information Science and Technology / 2021)