一种快速近似模式匹配算法.docVIP

华南理工大学学报 ( 自 然 科 学 版) Journal of South China University of Technology ( Natural Science Edition) 第 40 卷 第 6 期 2012 年 6 月 Vol． 40 No ． 6 June 2012 文章编号: 1000-565X( 2012) 06-0103-06 一种快速近似模式匹配算法* 李拥军 敖道敢 ( 华南理工大学 计算机科学与工程学院，广东 广州 510006) 摘 要: 为进一步提升传统的近似模式匹配问题解决方法———动态规划算法的性能，提 出了一种新的过滤型近似模式匹配算法． 该算法结合动态规划算法，切分模式串得到长度 相等且更小的模式片; 在此基础上将待匹配的文本串分割成子串，并建立相应的索引; 同 时设计了一个新的过滤策略来消除匹配检查中的冗余． 通过实例将文中方法与现有方法 进行对比，结果表明: 文中方法的匹配时间较短，匹配性能优于现有方法; 随着模式串长度 的增加，文中算法的优越性更为明显，模式串长度大于 45 后，文中算法的匹配时间可比传 统动态规划算法缩短一半以上． 关键词: 近似模式匹配; 动态规划算法; 匹配时间 中图分类号: doi: 10． 3969 / j． issn． 1000-565X． 2012． 06． 017 TP 393 近似模式匹配是计算机科学的基本问题之一， 也是入侵检测、防火墙、病毒检测、内容分析与审计 等系统的关键技术，同时在计算生物学、信号处理、 模式识别、文本检索等领域也有重要的应用价值． 近 似匹配算法主要有 4 类: 基于动态规划的方法、基于 NFA 有哪些信誉好的足球投注网站的方法［1］、基于位并行的算法［2］和基于过 滤方法的算法． 当前的研究重点是用过滤算法解决 近似匹配． 一般而言，在错误水平较低时，过滤型算 法的效果是较理想的． 文献［3］中的算法将动态规 划( DP) 算法和过滤算法结合到一起，使得匹配的时 间比原 DP 算法大大缩短． 该算法虽然提高了匹配 效率，但它并不是最优的，仍然有改进的空间，文中 在其思想的基础上，增加一种新的过滤策略，以进一 步提高算法的性能，并通过实例对该算法进行验证． 换一个字符，称为编辑操作． 设 x、y 是两个字符串， 它们之间的编辑距离 edit ( x，y) 就是将 x 转变为 y ( 或者是将 y 转变为 x) 所需的最少编辑操作次数． 定义 2 在编辑距离模型下，给定一个整数 k、 一个 模 式 串 Pattern ［1，2，…，m］和 一 个 文 本 串 Text［1，2…，n］，找 出 Text 中 的 所 有 子 串 p，使 得 edit( Pattern，p) ≤k，称为近似匹配． 定义 3 在建立索引时采用长度为 q、滑动距离 为 d 的滑动窗口对文本串 Text 进行切分，切分得到 长度为 q 的子串就称为 q-gram 索引［4］，相邻 q-gram 在 Text 中的偏移量之差称为滑动距离，该索引具有 占用内存空间小、缓存容易管理、索引简单等优点． 根据以上定义，在文本串 Text 中，于 h ( h ≥q，h 由引理一给出) 的倍数位置取长度为 q 的子串作为 一个 q-gram 采样，把这些 q-gram 采样分别标记为 d1 ，d2 ，…，如图 1 所示． 模式串相应的处理: 将模式串 Pattern 切分成长 算法基础 定义 1 插入一个字符、删除一个字符或者替 1 收稿日期: 2011-12-26 * 基金项目: 国家自然科学基金资助项目 () ; 广东省科技计划项目 ( 2011B010200039 ) ; 广州市科技计划 项 目 ( 11 作者简介: 李拥军( 1968-) ，男，博士，副教授，主要从事计算机网络与人工智能研究． E-mail: liyj@ scut． edu． cn 符串匹配中非常有用，文献［6-7］中的算法建立可 变长度的 q-gram，文献［8-11］中的算法建立固定长 度的 q-gram，另外一些算法［12-13］会对文本串进行分 析，产生所有的索引结构，还有一些算法［3，5］则在扫 描文本串的过程中建立索引结构，它们都取得了较 好的效果． 文献［3］中的算法从左向右依次扫描文本串 Text 建立 q-gram 索引，然后分别计算该 q-gram 与每 个 Qf ( f∈［1 … m］) 的匹配情况，建立的数组 M 如 图 3 所示，实际上这里存在着冗余． 图 1 构造 q-gram 时对文本串的处理 Fig． 1 Text string processing when constructing q-gram 度为