Compressed Suffix Trees: Design, Construction, and Applications

如果文本（例如染色体的DNA序列）或文本集合（例如多个染色体或基因组）没有或很少改变，那么在许多应用程序中，在预处理步骤中为文本编制索引是值得的。然后使用构建的索引数据结构来加速应用程序（例如两个基因组的比较）。当自动处理大量数据时，会出现一个基本问题：如果索引不能完全装入计算机的主存储器，则必须将其中的一部分交换回辅助存储器。由于这会导致相当大的效率损失，因此该项目的目标是开发一个基本算法库，以构建简洁的索引数据结构，即使文本非常大也可以保存在主存中。库还应提供这些索引数据结构的应用算法。此外，在合作项目中，算法和数据结构应集成到软件系统CoCoNUT中。

If a text (e.g. the DNA sequence of a chromosome) or a collection of texts (e.g. multiple chromosomes or genomes) does not or rarely change, then in many applications it is worthwhile to index the text in a preprocessing step. The constructed index data structure is then used to accelerate applications (e.g. the comparison of two genomes). A fundamental problem arises when a huge amount of data is processed automatically: If the index does not completely fit into the main memory of the computer, then parts of it must be swapped back into secondary storage. Since this results in a considerable loss in efficiency, it is the goal of the project to develop a library of basic algorithms to construct succinct index data structures that can be kept in main memory even if the text is very large. The library shall also provide application algorithms on these index data structures. Furthermore, in a cooperation project the algorithms and data structures shall be integrated into the software system CoCoNUT.