大数据下高阶熵压缩全文自索引的创新技术

本文主要探讨了"高阶熵压缩的全文自索引"这一研究主题，针对大数据时代下快速增长的数据量，提出了一个高效且关键的问题解决方案。论文首先由西安电子科技大学计算机学院的霍红卫、陈晓阳、陈龙刚和于强四位作者合作完成，他们分别在算法设计与分析、大数据压缩索引与检索、压缩数据结构等领域有所专长。 论文的核心内容是提出了一种针对长度为n的文本T的压缩索引算法，特别关注的是k阶经验熵（Hk(T)），这是一个衡量文本信息复杂度的重要统计量，它基于文本中字符出现的频率分布。在设定k≤clogσn-1且c<1的前提下，这种压缩索引能够占用空间仅为2nHk(T) + n + o(n)位，这里的σ代表字符表的大小。这个设计使得空间效率得到了显著提升，尤其是当文本信息具有较高的熵值时。 值得一提的是，本文提出的压缩索引构建过程具备线性时间复杂度，这意味着在实际应用中，即使处理大规模数据，也能保持高效的实时构建能力。为了进一步优化性能，文中还引入了混合编码方法，根据1在gap序列中的分布动态调整编码策略，这在节省空间方面实现了额外的o(n)位开销。 实验部分展示了这种高阶熵压缩索引在pizza&Chilicorpus上的优秀表现，对比主流压缩索引，它在压缩率和查询时间上都显示出显著优势。这对于大数据存储和检索场景具有重要的实际意义，尤其是在减少存储需求和提高查询响应速度方面。 最后，文章的关键词包括大数据、压缩索引、自索引、高阶熵和混合编码，这些关键词揭示了论文的核心技术和关注点。论文的成果不仅理论价值高，而且具有很强的实用性，可供其他研究者参考和借鉴。有兴趣的读者可以通过Github获取作者们开发的压缩索引软件，进行更深入的学习和应用探索。