动态后继树索引压缩技术研究的中期报告.docx

动态后继树索引压缩技术研究的中期报告
动态后继树（DynamicSuffixTree）是解决字符串相关问题的常用数据结构，如字符串匹配、字符串排序等。但是，传统的动态后继树的空间消耗过大，难以应用于大规模字符串的处理。因此，通过对后继树进行压缩，可以减少其空间占用，进一步提高其应用效率。
本研究的目的是探索动态后继树索引的压缩技术，以减少其空间占用，并提高查询效率。针对这一问题，我们分别研究了压缩技术中的两种方法，分别是前缀压缩和后缀压缩。
在前缀压缩技术方面，我们设计了一种基于前缀压缩的动态后继树索引压缩算法，通过将具有相同前缀的字符串合并，在保证查询正确性的前提下，大幅减少索引的存储空间。实验结果表明，该算法相对于传统的动态后继树，在空间消耗上可以减少30%以上，而查询时间却只有轻微的增加。
在后缀压缩技术方面，我们研究了一种基于后缀数组的动态后继树索引压缩方法，通过将后缀数组中相邻的字符串进行合并，同时引入了范围查询结构，在保证索引正确性的前提下，减少了索引的存储空间。实验结果表明，该算法相较于传统的后缀数组在空间消耗上可减少60%以上，而查询时间仅有轻微的增加。
综上所述，本研究通过在动态后继树索引中引入前缀压缩和后缀压缩技术，分别实现对索引的空间压缩，有效提高了动态后继树的查询效率和存储效率。未来我们将进一步对该算法进行优化，并拓展其应用领域。