序列和文本的熵压缩结构研究

发布时间：2023-04-09 20:24

　　信息化时代,数据量的激增给我们带来了机遇也带来了信息存储及检索的挑战。字符串匹配是信息检索最基本的操作,解决该问题的常用方式为索引匹配和顺序匹配。鉴于索引匹配的高效性,使用后缀数组(Suffix Array,SA)等索引结构的匹配方式逐渐代替了传统的顺序匹配。然而SA空间过大的问题,限制了其实用性。如何高效地存储SA这一索引结构,并使其支持快速查询操作,就成为了压缩索引领域重要的研究课题之一。就压缩后缀数组(Compressed Suffix Array,CSA)这一熵压缩结构而言,近年来的相关研究都以如何高效编码Ф数组为目标。本文沿袭这样的研究路线,结合Ф数组的差值序列(gap序列)针对不同文本展现出的数据特点,设计具有针对性的CSA新结构与算法,力图改善CSA面对不同类型文本输入时的压缩率及查询效率。首先,本文以GamCSA这一双层索引框架为基础,对各种类型的标准文本输入进行实验,发现不同文本具有不一样的gap序列统计特征,具体反映在其1-gap比重和1-gap-Runs的长度上,其中1-gap表示gap序列中的1值,1-gap-Runs表示gap序列中1值连续出现次数的平均值。1...

【文章页数】：82 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
    1.1 研究背景及意义
    1.2 研究现状
    1.3 本文工作
第二章 预备知识
    2.1 符号及问题描述
    2.2 文本的熵
    2.3 后缀数组
    2.4 BWT变换
    2.5 近邻函数Ф的定义
    2.6 本章小结
第三章 压缩后缀数组的基本框架
    3.1 近邻函数Ф的表示
    3.2 字符频数统计表
    3.3 近邻函数Ф的线性构造
    3.4 本章小结
第四章 编码
    4.1 差值序列分析
    4.2 候选编码
    4.3 混合编码及结构分类
    4.4 本章小结
第五章 压缩后缀数组的新结构和算法
    5.1 高度重复文本集的HiCSA结构
    5.2 普通文本集的NorCSA结构
    5.3 空间分析
    5.4 解码加速
    5.5 计数查询
        5.5.1 词汇加速表
        5.5.2 count算法
    5.6 定位和恢复查询
        5.6.1 采样方式
        5.6.2 locate和extract算法
        5.6.3 变长采样策略
    5.7 本章小结
第六章 实验结果与分析
    6.1 实验环境和数据源
    6.2 变长采样实验
    6.3 性能评估
    6.4 本章小结
第七章 总结与展望
    7.1 总结
    7.2 展望
参考文献
致谢
作者简介



本文编号：3787677