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

中英混合多模式匹配算法的改进及GPU并行化研究

作　者: 王震
导　师: 李仁发
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 内容审计多模式匹配中英文混合图形处理单元并行计算统一计算设备架构
分类号: TP391.1
类　型: 硕士论文
年　份: 2013年
下　载: 0次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机、通信与网络的飞速发展，信息泄漏等问题受到了越来越多的关注。基于内容的网络信息审计，是保证信息不被泄漏，防止非法信息传播的有效手段，其关键技术为多模式文本匹配。在我国现有的网络环境下，多模式文本匹配将会面临中英文混合处理这一特殊难题。传统的多模式匹配在此环境下，则会产生空间膨胀、误匹配或漏匹配等问题。且随着网络数据信息规模的日益增加，对内容审计的实时性有了更高的要求。论文的主要工作包括：（1）在Trie结构的基础上，提出了一种基于节点添加的中英混合多模式匹配算法—NA-Trie。该算法通过添加少量的节点，以避免中文首字节错位匹配等问题。算法能够正确处理模式串同时含有中英文字符这一情况，有效避免错误匹配的发生；并且简化匹配过程，消去了多余的分支语句，使得算法更易于并行加速。给出一种基于记忆化存储状态结果的优化算法，通过预处理所有状态节点，记忆化地保存各状态所能获得的匹配数。该算法降低了匹配算法的时间常数，减少了时间开销，在一定程度上提高了匹配效率。（2）分多个小文本、单个大文本两种情况，利用GPU对多模式匹配进行并行优化。并针对单个大文本情形，给出一种基于文本拆分的并行文本匹配算法。该算法通过预处理以去除中文文本的数据相关性，再进行文本拆分和并行匹配，以大幅提升算法匹配效率。设计并实现了一种基于GPU的通用并行文本匹配原型系统，该原型系统模块化了并行匹配过程，提供了统一的函数接口。研究人员只需将自己的核心匹配代码嵌入到接口函数中，即可完成多模式匹配算法的并行优化。该原型系统简化了编码过程，提高了开发效率。

全文目录

摘要  5-6
Abstract  6-10
插图索引  10-11
附表索引  11-12
第1章绪论  12-19
  1.1 研究背景  12-13
  1.2 相关研究问题  13-16
    1.2.1 多模式匹配  13
    1.2.2 Trie 结构  13
    1.2.3 中英文混合环境  13-14
    1.2.4 GPU 并行处理  14-15
    1.2.5 CUDA 架构  15-16
    1.2.6 面临的困难和挑战  16
  1.3 研究内容与贡献  16-17
    1.3.1 研究思路与内容  16-17
    1.3.2 研究贡献  17
  1.4 论文组织结构  17-19
第2章相关研究  19-27
  2.1 引言  19-20
  2.2 多模式匹配算法  20-21
    2.2.1 前缀搜索  20
    2.2.2 后缀搜索  20-21
    2.2.3 子串搜索  21
  2.3 中英文混合环境下的匹配算法  21-25
    2.3.1 所有字节的完全哈希的匹配算法  22
    2.3.2 基于字符拆分的匹配算法  22
    2.3.3 基于跳跃的多模式匹配算法  22
    2.3.4 完全哈希算法  22-24
    2.3.5 线索化的完全哈希算法  24-25
  2.4 多模式匹配的并行化  25
    2.4.1 Brute Force 算法并行化  25
    2.4.2 增加冗余信息的匹配并行化  25
    2.4.3 并行化的 AC 算法  25
  2.5 结论  25-27
第3章基于节点添加的中英混合多模式匹配  27-38
  3.1 引言  27-28
  3.2 基于节点添加的完全哈希 Trie 算法  28-33
    3.2.1 Trie 结构的线索化  28-29
    3.2.2 中文字符的错位匹配  29-30
    3.2.3 Trie 结构上的节点添加算法  30-32
    3.2.4 构建完全的状态转移  32-33
    3.2.5 基于节点添加的文本匹配过程  33
  3.3 记忆化存储状态结果  33-35
    3.3.1 当前状态所含的匹配数  33-34
    3.3.2 优化的文本匹配过程  34-35
  3.4 多字节汉字编码的处理  35-36
    3.4.1 多字节编码的节点添加  35
    3.4.2 一种折中的实时添加策略  35-36
  3.5 时空复杂度分析  36
    3.5.1 空间复杂度  36
    3.5.2 时间复杂度  36
  3.6 结论  36-38
第4章基于 GPU 的中英混合多模式匹配的并行化  38-48
  4.1 引言  38-39
  4.2 多文本并行算法  39
  4.3 基于文本拆分的 GPU 并行算法  39-43
    4.3.1 文本拆分  40-41
    4.3.2 处理拆分后的小文本  41-42
    4.3.3 文本拆分处的处理  42-43
  4.4 GPU 并行算法的优化  43-46
    4.4.1 并行化预处理  43-44
    4.4.2 数据结构的存储  44-45
    4.4.3 空间压缩  45-46
  4.5 基于 GPU 的通用并行文本匹配原型系统  46-47
  4.6 结论  47-48
第5章实验及结果分析  48-57
  5.1 引言  48
  5.2 实验环境  48
    5.2.1 硬件平台  48
    5.2.2 软件平台  48
  5.3 实验数据  48-49
    5.3.1 多文本实验  49
    5.3.2 大文本实验  49
  5.4 实验结果与分析  49-55
    5.4.1 THT 与 NA-Trie 算法效率对比  49-51
    5.4.2 串行/并行算法效率对比  51-54
    5.4.3 模式串数量对匹配效率的影响  54-55
  5.5 结论  55-57
结论  57-59
参考文献  59-63
附录A 攻读硕士学位期间发表论文  63-64
附录B 攻读硕士学位期间参与项目及所获奖项  64-65
致谢  65

中英混合多模式匹配算法的改进及GPU并行化研究

内容摘要

全文目录

相似论文