用于小巧且快速的压缩后缀数组的自适应编码

《ACM Transactions on Algorithms》:Adaptive encodings for small and fast compressed suffix arrays

【字体: 大 中 小 】 时间:2026年08月30日 来源:ACM Transactions on Algorithms 1.4

编辑推荐:

   摘要AI摘要要查看此AI生成的摘要,您需要高级访问权限。了解更多登录摘要摘要压缩后缀数组用于索引大型重复序列集,并广泛应用于生物信息学、版本控制和自然语言处理。r-index及其变体将游程编码的Burrows-Wheeler变换(BWT)与后缀数组采样相结合,以实现与相同符号

  

摘要

摘要

压缩后缀数组用于索引大型重复序列集,并广泛应用于生物信息学、版本控制和自然语言处理。r-index及其变体将游程编码的Burrows-Wheeler变换(BWT)与后缀数组采样相结合,以实现与相同符号游程数量成比例的存储空间。虽然对近乎相同的字符串有效,但当向集合中添加编辑副本时,其大小会迅速增长,因为BWT游程数量对变异敏感。现有方法要么以较慢的查询为代价进行额外压缩,要么以牺牲空间为代价优先保证速度,限制了大规模应用中的实用权衡。
我们引入了变长分块(VLB),这是一种针对基于BWT的压缩后缀数组的自适应编码。我们的技术根据局部游程结构调整索引信息量:可压缩区域保留较少的辅助数据,而不可压缩区域存储更多。具体而言,我们递归划分BWT,直到每个块最多包含w个游程(参数),并将块组织成树。访问某个位置需要沿根到叶的路径下降,然后进行短暂的游程扫描。可压缩区域位于树的根部附近,而不可压缩区域位于更深处,并增加额外的索引数据以加快访问速度。该策略通过将可压缩区域节省的位重新分配来加速对不可压缩区域的访问,从而平衡空间与查询速度。VLB树还通过使相关的BWT和后缀数组信息共存同一位置来提高内存局部性。
反向搜索依赖于对BWT的rank和successor查询。我们引入了一种采样技术,通过保证这些查询仅在有效的反向搜索状态下正确来放宽全局正确性。这一限制在不影响模式匹配的速度或正确性的情况下减少了空间使用。
我们进一步扩展VLB树的概念以编码后缀数组采样,并扩展到子采样r-index(sr-index),从而生成一个小型完全功能化的压缩后缀数组。实验表明,VLB树变体在查询时间上优于r-index和sr-index,同时保持了接近sr-index的空间使用。move数据结构是一种较新的编码,比VLB树更快,但使用的空间明显更多,形成了清晰的空间-时间权衡。

AI摘要

AI生成的摘要(实验性)

此摘要使用自动化工具生成,未经本文作者编写或审核。它旨在支持发现,帮助读者评估相关性,并协助来自相邻研究领域的读者理解本文内容。它旨在补充作者提供的摘要,后者仍是论文的主要摘要。全文仍是权威记录版本。 点击此处了解更多。

点击 此处 评论此摘要的准确性、清晰度和实用性。这样做将有助于改进和未来的重新生成版本。

要查看此AI生成的通俗语言摘要,您需要高级访问权限。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号