学位论文 > 优秀研究生学位论文题录展示

支持压缩数据的近似子串查询处理技术的研究与系统实现

作　者: 侯闯
导　师: 杨晓春
学　校: 东北大学
专　业: 计算机系统结构
关键词: 压缩数据近似子串查询高效过滤系统
分类号: TP274
类　型: 硕士论文
年　份: 2010年
下　载: 5次
引　用: 0次
阅　读: 论文下载

内容摘要

随着社会的发展,各种信息数据的总量正在不断的扩大。数据量的激增给数据的保存和使用都带来了巨大的压力。为了解决数据规模的增加与存储空间的矛盾,高效的压缩算法被相继提出。数据查询技术在各个领域都是必不可少的,然而数据压缩技术却给数据查询带来了巨大的挑战。如何针对压缩数据进行数据查询成为本文的主要研究内容。本文首先对近似字符串查询处理技术进行了综述。基于最新的一种数据无损压缩技术,提出并设计实现支持压缩数据的近似子串查询技术。这种无损压缩技术利用字符串数据之间的高相似性,实现数据压缩。为了对数据进行高效的查询,对压缩数据采用了高效的B+-tree结构和先进的倒排表索引技术,根据倒排表索引提供的信息可以快速进行查询定位,B+-tree结构可以快速完成信息的获取,通过对这两种索引技术的改进使之可以应用于近似子串查询算法。提出了高效率的相关过滤方法,最后提出并设计了完善的近似子串查询算法。基于上述理论研究并实现了近似子串查询系统,对系统的可行性、功能需求以及性能需求都做了详细的分析,采用B/S架构设计该系统,使用户通过网络进行使用。运行测试和性能测试表明该系统基于压缩数据,节省了大量的空间代价,并可以保证查询时间的有效性。同时可以提供稳定的对外服务。

全文目录

摘要  5-6
Abstract  6-10
第1章引言  10-14
  1.1 研究背景  10-11
  1.2 本文的研究内容及面临的挑战  11
  1.3 研究的意义  11-12
  1.4 本文的组织结构  12-14
第2章相关工作  14-26
  2.1 近似字符串匹配定义  14-15
  2.2 编辑操作与距离函数  15-18
    2.2.1 编辑距离  15-18
    2.2.2 海明距离  18
  2.3 倒排列表和Q-GRAM技术  18-22
  2.4 区间树  22-24
  2.5 本章小结  24-26
第3章压缩数据表示及问题定义  26-30
  3.1 压缩数据相关定义  26-28
  3.2 压缩数据近似子串查询问题定义  28
  3.3 本章小结  28-30
第4章压缩数据上的近似子串查询技术  30-42
  4.1 压缩数据索引技术  30-34
    4.1.1 倒排索引构建  30-31
    4.1.2 增量树△-Tree  31-34
    4.1.3 获取子串算法  34
  4.2 近似子串查询算法  34-41
    4.2.1 基础算法  34-36
    4.2.2 过滤原理  36-37
    4.2.3 改进算法  37-41
  4.3 本章小结  41-42
第5章子串查询系统的设计与实现  42-56
  5.1 系统分析  42-44
    5.1.1 系统可行性分析  42-43
    5.1.2 系统功能和性能需求  43-44
    5.1.3 系统架构分析  44
  5.2 系统设计与实现  44-54
    5.2.1 运行环境设置  44-46
    5.2.2 系统功能设计  46-52
    5.2.3 数据库设计  52-54
  5.3 本章小结  54-56
第6章系统测试  56-64
  6.1 黑盒测试  57-59
    6.1.1 界面测试  57-58
    6.1.2 功能测试  58-59
  6.2 白盒测试  59-60
  6.3 性能测试  60-61
  6.4 本章小结  61-64
第7章总结  64-66
  7.1 本文总结  64-65
  7.2 工作展望  65-66
参考文献  66-70
致谢  70-72
攻硕期间参与的项目  72

支持压缩数据的近似子串查询处理技术的研究与系统实现

内容摘要

全文目录

相似论文