Development of Practical Succinct Data Structures with Application to Huge Data

对于简洁数据结构的研究一直只是理论上的。在这项研究中，我们开发了简洁的数据结构，解决了在实际计算机上使用它们的问题。对于有序树，我们将简洁数据结构的大小减少了40%，同时支持现有数据结构中不支持的各种操作。我们还创建了一个压缩后缀数组和压缩后缀树库，它们是用于字符串搜索的简洁数据结构。通过使用它，我们可以减少数据结构的大小，这是用于搜索110个字节的文本数据，从680个字节到22个字节。

There had been only theoretical researches on succinct data structures. In this research, we have developed succinct data structures which solve the problems of using them on actual computers. For ordinal trees, we have reduced the size of succinct data structures by 40%, while supporting various operations which had not been supported in existing data structures. We have also created a library of compressed suffix arrays and compressed suffix trees, which are succinct data structures for string searches. By using it, we can reduce the size of the data structure, which is used for searching text data of 110 Gigabytes, from 680 Gigabytes to 22 Gigabytes.