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.