Succinct Data Structures with Applications to Large Data Sets

有效地存储和检索信息是计算机科学中的一个重要课题。在过去的几十年里，已经开发了各种技术来索引数据，从而可以通过执行对关键字或短语的查询来几乎即时地检索有用的信息。近年来，随着数据大小的快速增长，许多对小而旧的系统有用的技术已经变得不适用于大型的现代应用程序，因为它们占用了太多的存储空间。这些空间中的大部分不是原始数据，而是为提高搜索效率而添加的结构性信息。为了解决这一问题，人们提出了简洁的数据结构，以便快速检索大型系统中的信息，但空间需求与原始数据相差不大。

The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, various techniques have been developed to index data so that the useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that were useful for small, older systems have become infeasible for large, modern applications because they occupy too much storage. Most of this space is not the raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data.