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

近似字符串匹配研究及其在URL检测中的应用

作　者: 谢豪
导　师: 李拥军；刘钢
学　校: 华南理工大学
专　业: 计算机技术
关键词: 近似匹配 q-gram 位并行编辑距离 DP算法
分类号: TP393.08
类　型: 硕士论文
年　份: 2011年
下　载: 24次
引　用: 0次
阅　读: 论文下载

内容摘要

字符串匹配的问题是计算机领域中基本并且广泛研究的问题之一,在现实生活中有着广泛的应用,尤其是随着信息检索以及计算生物学领域的迅猛发展,对字符串匹配的研究也随之高涨。对字符串匹配的研究,最初主要是集中在精确匹配上,也提出了许多著名的算法,比较有名的为KMP算法以及BM算法;后来逐渐发展到多字符串匹配,扩展字符串匹配以及正则表达式的匹配。然而在实际应用中,为了提高匹配效率,可以允许在模式串和对应的文本之间有稍许的不一致,比如信号处理中的传输纠正、拼写纠错、文本搜索、计算生物学领域中的序列比对等等。因此,设计高效的算法或者优化现有近似匹配算法具有重要的理论和实际价值。基于编辑距离模型的近似模式匹配问题,传统的解决方法是采用动态规划方法;或者是使用基于NFA的搜索,此类算法使用给定的模式串和阀值k构造NFA。近来近似匹配算法的研究侧重在位并行技术以及基于过滤的算法以缩短近似匹配的平均时间。本文对已有的一种基于q-gram索引的高效算法从位并行以及过滤两个方面进行了优化,分别适用于不同长度的模式串。实验表明,本改进算法在最好情况下比同类算法缩短一半的时间。本论文完成了如下的工作:本文的第一章介绍了论文的研究背景、研究内容、字符串匹配的概况以及论文的组织架构。第二章介绍了单字符串匹配的三种搜索方式以及各自经典算法的实现原理。第三、四章是论文的核心,介绍了近似匹配的研究方法,同时提出了基于文本过滤算法的改进版本,并且在实验中得到了很好的验证。在第五章中,设计了基于url的过滤系统,主要是基于近似字符串匹配算法实现简单的应用。最后对论文进行总结,同时对字符串匹配的应用前景进行了展望。

全文目录

摘要  5-6
Abstract  6-9
第一章绪论  9-13
  1.1 研究的背景  9-11
  1.2 国内外研究现状  11
  1.3 论文的主要工作  11-12
  1.4 论文的组织  12-13
第二章基本字符串匹配  13-27
  2.1 字符串匹配的概述  13-16
    2.1.1 前缀搜索  14-15
    2.1.2 后缀搜索  15-16
    2.1.3 子串搜索  16
  2.2 重要字符串匹配算法的分析  16-27
    2.2.1 Shift-And算法  16-19
    2.2.2 BM算法  19-21
    2.2.3 Horspool算法  21-23
    2.2.4 BNDM算法  23-27
第三章近似匹配算法的研究  27-34
  3.1 近似匹配的基本概念  27-28
  3.2 编辑距离的计算  28-29
  3.3 文本串中计算编辑距离  29-30
  3.4 DP算法介绍  30-31
  3.5 并行化动态规划矩阵  31-34
第四章基于文本过滤的近似匹配算法改进  34-51
  4.1 k+1 分片思想  34-36
  4.2 q-gram索引简介  36-37
  4.3 在近似匹配中使用q-gram  37-38
  4.4 改进算法一的提出和描述  38-42
  4.5 改进算法一的性能比较和分析  42-44
  4.6 改进算法二的提出与描述  44-49
  4.7 改进算法二的性能比较和分析  49-51
第五章基于Url的过滤驱动开发  51-70
  5.1 NDIS中间驱动概述  51-54
  5.2 中间层驱动的入口与绑定  54-56
    5.2.1 中间层驱动入口  54-55
    5.2.2 中间层驱动的绑定  55-56
  5.3 中间层驱动处理数据包  56-60
  5.4 包的分解  60-63
  5.5 系统总体架构  63-67
    5.5.1 系统架构概述  63-67
    5.5.2 缓存优化  67
  5.6 系统运行  67-70
结束语  70-72
参考文献  72-75
攻读硕士学位期间取得的研究成果  75-76
致谢  76

近似字符串匹配研究及其在URL检测中的应用

内容摘要

全文目录

相似论文