HASH GAME - Online Skill Game GET 300

　　第卷第期 计 算 机 学 报 ３７ ５ Ｖｏｌ．３７ Ｎｏ．５ 年月 ２０１４ ５ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｍａ ２０１４ｙ 一种面向大规模 过滤的多模式串匹配算法 犝犚犔 ），） ） ） ），） ），） １ ２ ３ ４ １ ２ １ ２ 刘燕兵 邵妍 王勇 刘庆云 郭莉 １） （中国科学院信息工程研究所北京 ） １０００９３ ２） （信息内容安全技术国家工程实验室北京 ） １０００９３ ３） （北京邮电大学计算机学院北京 ） １００８７６ ４） （国家计算机网络与信息安全管理中心北京 ） １０００２９ 摘要对大量有害的 进行过滤，是目前网络安全应用系统中所亟需的关键技术使用经典的串匹配算法检 ＵＲＬ ． 测庞大的 规则集，需要消耗大量的计算资源和存储资源，性能十分低下该文设计了一种适合于大规模 ＵＲＬ ． ＵＲＬ ——— ， ， 过滤的多模式串匹配算法 该算法在经典的 算法基础上针对 规则的特点提出了最优窗 ＳＯＧＯＰＴ． ＳＯＧ ＵＲＬ 口选择、模式串分组规约这两种优化技术，大幅度提高了 算法的匹配速度，在大规模 规则集上效果尤其 ＳＯＧ ＵＲＬ 显著该文设计的算法非常适合于大规模（万级） 实时在线 ＵＲＬ ． 关键词多模式串匹配； 过滤；最优窗口选择；模式串分组规约；信息安全；网络安全 ＵＲＬ 中图法分类号 ； 号 ／ ＴＰ３０９ＴＰ３９３ 犇犗犐 １０．３７２４ＳＰ．Ｊ．１０１６．２０１４．０１１５９ 犃犕狌犾狋犻犾犲犛狋狉犻狀犕犪狋犮犺犻狀犃犾狅狉犻狋犺犿犳狅狉犔犪狉犲犛犮犪犾犲犝犚犔犉犻犾狋犲狉犻狀 狆 犵 犵犵 犵 犵 ），） ） ） ），） ），） １ ２ ３ ４ １ ２ １ ２ ＬＩＵＹａｎＢｉｎ ＳＨＡＯＹａｎ ＷＡＮＧＹｏｎ ＬＩＵＱｉｎＹｕｎ ＧＵＯＬｉ ｇ ｇ ｇ １） （ ， ， ） 犐狀狊狋犻狋狌狋犲狅犐狀狅狉犿犪狋犻狅狀犈狀犻狀犲犲狉犻狀犆犺犻狀犲狊犲犃犮犪犱犲犿狅犛犮犻犲狀犮犲狊犅犲犻犻狀１０００９３ 犳犳 犵 犵 狔犳 犼犵 ２） （ ， ） 犖犪狋犻狅狀犪犾犈狀犻狀犲犲狉犻狀犔犪犫狅狉犪狋狅狉狅狉犐狀狅狉犿犪狋犻狅狀犛犲犮狌狉犻狋犜犲犮犺狀狅犾狅犻犲狊犅犲犻犻狀１０００９３ 犵 犵 狔犳 犳 狔 犵 犼犵 ３） （ ， ， ） 犛犮犺狅狅犾狅犆狅犿狌狋犲狉犛犮犻犲狀犮犲犅犲犻犻狀犝狀犻狏犲狉狊犻狋狅犘狅狊狋狊犪狀犱犜犲犾犲犮狅犿犿狌狀犻犮犪狋犻狅狀狊犅犲犻犻狀１００８７６ 犳 狆 犼犵 狔犳 犼犵 ４） （ ， ） 犖犪狋犻狅狀犪犾犃犱犿犻狀犻狊狋狉犪狋犻狏犲犆犲狀狋犲狉狅狉犖犲狋狑狅狉犽犪狀犱犐狀狅狉犿犪狋犻狅狀犛犲犮狌狉犻狋犅犲犻犻狀１０００２９ 犳 犳 狔 犼犵 犃犫狊狋狉犪犮狋Ｔｈｅｆｉｌｔｅｒｉｎ ｏｆｌａｒｅｓｃａｌｅｈａｚａｒｄｏｕｓＵＲＬｓ ｌａｓａｆｕｎｄａｍｅｎｔａｌｒｏｌｅｉｎｍａｎ ｎｅｔｗｏｒｋ ｇ ｇ ｐ ｙ ｙ ｓｅｃｕｒｉｔ ａ ｌｉｃａｔｉｏｎｓ．Ｔｈｅｃｌａｓｓｉｃａｌｍｕｌｔｉｌｅｓｔｒｉｎ ｍａｔｃｈｉｎ ａｌｏｒｉｔｈｍｓ ｅｒｆｏｒｍ ｏｏｒｌ ｏｎｌａｒｅ ｙ ｐｐ ｐ ｇ ｇ ｇ ｐ ｐ ｙ ｇ ， ｓｃａｌｅＵＲＬｓ ｄｕｅｔｏｔｈｅｈｅａｖ ｃｏｎｓｕｍｔｉｏｎｏｆＣＰＵ ｏｗｅｒａｎｄｍｅｍｏｒ ｓａｃｅ．Ｈｅｒｅｗｅ ｒｏｏｓｅａ ｙ ｐ ｐ ｙ ｐ ｐ ｐ ｍｕｌｔｉｌｅｓｔｒｉｎ ｍａｔｃｈｉｎ ａｌｏｒｉｔｈｍ—ＳＯＧＯＰＴｆｏｒｌａｒｅｓｃａｌｅＵＲＬｆｉｌｔｅｒｉｎ．Ｂ ｅｘｌｏｉｔｉｎ ｔｈｅ ｐ ｇ ｇ ｇ ｇ ｇ ｙ ｐ ｇ ， ， ｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＵＲＬｓ ｔｈｅ ｒｏｏｓｅｄａｌｏｒｉｔｈｍｄｅｖｉｓｅｓｔｗｏｓｔｒａｔｅｉｅｓ ｉ．ｅ．ｔｈｅｏｔｉｍａｌｗｉｎｄｏｗ ｐ ｐ ｇ ｇ ｐ ， ｓｅｌｅｃｔｉｏｎｓｔｒａｔｅ ａｎｄｔｈｅ ａｔｔｅｒｎｓｅｔ ａｒｔｉｔｉｏｎｉｎ ａｎｄｒｅｄｕｃｔｉｏｎｓｔｒａｔｅ ｔｏｓｅｅｄｕ ｔｈｅｃｌａｓｓｉｃａｌ ｇｙ ｐ ｐ ｇ ｇｙ ｐ ｐ ， ＳＯＧａｌｏｒｉｔｈｍ．Ｔｈｅ ｒｏｏｓｅｄａｌｏｒｉｔｈｍｉｍｒｏｖｅｓｔｈｅｓｅａｒｃｈｉｎ ｓｅｅｄｏｆＳＯＧ ｒｅａｔｌ ｅｓｅｃｉａｌｌ ｇ ｐ ｐ ｇ ｐ ｇ ｐ ｇ ｙ ｐ ｙ （ ） ｏｎｌａｒｅｇｓｃａｌｅＵＲＬｓ．Ｉｔｉｓｖｅｒ ｓｕｉｔａｂｌｅｆｏｒｌａｒｅｓｃａｌｅ ｕ ｔｏ１ｍｉｌｌｉｏｎＵＲＬｓ ａｎｄｏｎｌｉｎｅＵＲＬｙ ｇ ｐ ｆｉｌｔｅｒｉｎ．ｇ ； ； ；ａｔｔｅｒｎｓｅｔ 犓犲狑狅狉犱狊ｍｕｌｔｉｌｅｓｔｒｉｎ ｍａｔｃｈｉｎ ＵＲＬｆｉｌｔｅｒｉｎ ｏｔｉｍａｌｗｉｎｄｏｗｓｅｌｅｃｔｉｏｎ 狔 ｐ ｇ ｇ ｇ ｐ ｐ ａｒｔｉｔｉｏｎｉｎ ａｎｄｒｅｄｕｃｔｉｏｎ； ； ｐ ｇ ｉｎｆｏｒｍａｔｉｏｎｓｅｃｕｒｉｔ ｎｅｔｗｏｒｋｓｅｃｕｒｉｔｙ ｙ 收稿日期： ；最终修改稿收到日期： 本课题得到中国科学院战略性先导科技专项课题“媒体内容安全监管技术” ２０１１０６２０ ２０１４０３１８． （ ）、国家自然科学基金青年基金项目“复杂规则实时检测的模型和算法研究”（ ）资助刘燕兵，男， 年生，博 ＸＤ ． １９８１ 士，副研究员，中国计算机学会会员，主要研究方向为文本算法、数据流处理、信息内容安全 ： 邵妍，女， ．Ｅｍａｉｌ ｌｉｕａｎｂｉｎ ｉｉｅ．ａｃ．ｃｎ． ＠ ｙ ｇ 年生，硕士，主要研究方向为字符串匹配、信息内容安全王勇，男， 年生，博士研究生，高级工程师，主要研究方向为网络与信 １９８７ ． １９７９ 息安全刘庆云，男， 年生，博士研究生，高级工程师，主要研究方向为内容安全管理、网络安全郭莉，女， 年生，正高级工程 ． １９８０ ． １９６９ 师，主要研究方向为网络与信息安全． １１６０ 计 算 机 学 报 ２０１４年 ： 、 算法分为三大类基于自动机的匹配算法基于散列 的匹配算法和基于位并行的匹配算法（） １ 引言 ．１ 基于自 动机的匹配算法采用自动机作为基本的数据结构， （ ） ： ［］１ 所谓多模式串匹配后文简称串匹配是指给 用自动机识别模式串的前缀或者子串 和 ．ＡＣ （） （） （） （） 定字符串集合 １ ２ 狉 犻 ［］２ 犘＝｛，，…，｝，其中 ＝ 是这类算法的典型代表自动机类型匹配 狆狆 狆 狆 ＳＢＯＭ ． （）（） （） 犻 犻 犻 … 是字符集上的字符串，对于任意的输 狆狆狆 Σ １ ２ 犿 算法的优点是适应性好，在不同类型的数据集上的 犻 入文本串 …，找出中的字符串在中的 犜＝狋狋狋 犘 犜 １ ２ 狀 性能稳定其缺点是自动机需要消耗巨大的存储空 ． （） 犻 所有出现位置称为模式串集合，称 为模式 ．犘 狆 间，无法支持大规模串匹配例如，对于 万个长 ． １００ 串，称为文本串匹配技术在网络信息安全领域 犜 ． ６ 度为 的字符串，自动机大约需要消耗 １０ ＡＣ １０× 有着广泛的应用，典型的应用包括：入侵检测／防御 的存储空间（）基于散列的匹配 １０×１ＫＢ １０ＧＢ ．２ ≈ （／）、 （／ 系统ＩＤＳＩＰＳ 反病毒和反垃圾邮件检测ＡＶ 算法采用散列表作为基本的数据结构，用散列表记 ）、 （）、 网络带宽管理和服务质量 统一威胁管 ＡＳ ＱｏＳ 录模式串的散列值，并与待匹配文本的散列值进行 理（ ）等等与此同时，串匹配技术在文本检索、 ＵＴＭ ． 比对 ［］３ ，以检测模式串和文本是否匹配 和 ．ＫＲ 、 、 、 搜索引擎语言翻译拼写检查计算生物学等领域 ［］４ 是这类算法的典型代表散列类型算法的优 ＷＭ ． 也发挥着关键的作用． 点是存储空间较小，在大字符集随机数据上的匹配 对大量有害的 进行过滤，是目前网络安 ＵＲＬ 速度很快但是对于字符集较小并且字符分布极不 ． 全应用系统中所亟需的关键技术目前有七类典型 ． 均匀的数据（ 、 ）， 例如ＵＲＬＥｍａｉｌ等这类算法的实 ， ： 、 应用需要进行ＵＲＬ过滤包括色情内容垃圾邮 际性能很差（）基于位并行的匹配算法采用位向 ．３ 、 、 、 、 件恶意软件漏洞利用网络钓鱼代理和可能不受 量来模拟串匹配自动机的匹配过程，将自动机的状 欢迎的应用对这些造成巨大危害的 进行过 ． ＵＲＬ 态跳转表示为位向量的运算，并通过机器字来高效 ， 、 、 滤可以有效地对人们上网浏览非法有害不良信 执行 ［］５ ［］６ ／ 和 是这类算 ．ＳｈｉｆｔＡＮＤＳｈｉｆｔＯＲ ＢＮＤＭ ， 息内容进行控制与管理创造绿色洁净的网络空间 法的典型代表这类算法的优点是存储空间小，匹配 环境在海量的网络数据中检测庞大的 规则 ． ． ＵＲＬ 速度快， ／ 在普通 上甚至能达到 的匹配速 ＰＣ １ＧＢｓ ， ， 集需要消耗大量的计算资源和存储资源如何保证 度但是受限于机器字宽的限制，位并行算法只适合 串匹配算法仍然能够高效实时地运行，是我们当前 ． 于小规模（几个十几个模式串）串匹配 ． ～ 面临的一个重大难题． 近年来，国内外研究者在模式串匹配方面提出 本文设计了一种适合于大规模 过滤的多 ＵＲＬ ［ ］ ７１５ 了一些新的结果 文献［］和文献［］结合 ． ７ ８ ＡＣ ——— 该算法在经典的 模式串匹配算法 ＳＯＧＯＰＴ． 算法和跳跃的思想，提出了改进的多模式串匹配算 算法基础上，针对 规则的特点，提出了最 ＳＯＧ ＵＲＬ 法不同的是，前者采用 的思想进行 ． ＱｕｉｃｋＳｅａｒｃｈ 优窗口选择、模式串分组规约这两种优化技术，大幅 跳跃，而后者汲取 算法中跳跃的特性，采用后缀 ＢＭ 度提高了算法的匹配速度，在大规模 规则集 ＵＲＬ 树算法得到最大跳跃值当模式串数量较少时（千 上效果尤其显著实验结果显示：在 万 规 ． ． １００ ＵＲＬ 级），这两个算法的匹配效率相比 算法有较大提 则上， 算法的匹配速度是原始 算法 ＡＣ ＳＯＧＯＰＴ ＳＯＧ 高但是，对于大规模模式串（万级以上），这两个 的４．３３倍，并且性能远远优于其它经典串匹配算法 ． １０ ［］１ ［］ ［］ ［］２ ３ ４ 算法的跳跃能力基本退化至零，匹配效率与 算 （ 、 、 、 ）本文设计的算法 ＡＣ ＡＣ ＳＢＯＭＫＲ ＷＭ． 法相当文献［］提出了一种时间复杂度最优的串匹 非常适合于大规模ＵＲＬ实时在线匹配的应用环境． ． ９ 配算法 该算法综合使用后缀自动机 本文第节介绍串匹配的相关工作；第节介２ ３ ＬＤＭ． ＤＡＷＧ 和 自动机同时进行反向和正向匹配，其最坏时 绍本文提出的面向大规模ＵＲＬ过滤的串匹配算 ＡＣ 法——— ；第节将本文提出的匹配算法同 间复杂度和平均时间复杂度均达到理论最优但是， ＳＯＧＯＰＴ ４ ． ； 该算法需要存储两个自动机，庞大的存储开销更是 其它经典串匹配算法进行实验比较第节是本文５ 的总结 无法支持大规模串匹配文献［］利用散列函数和 ． １０ ． ＢｌｏｏｍＦｉｌｔｅｒ技术存储模式串的摘要信息，使得大 ２ 相关工作 部分的数据访问都局限在缓存之中，提高了缓存命 中率 ［］４ 该算法本质上是 算法的变体，只适合 ． ＷＭ 根据多模式串匹配算法的特点，我们将已有的 于大字符集和较长模式串的匹配文献［］提出了 ． １１ ５期 刘燕兵等：一种面向大规模 过滤的多模式串匹配算法 ＵＲＬ １１６１ ， 基于 技术的匹配算法 该算法利用 对于可能出现的匹配位置使用二级哈希和二分搜 ｇｒａｍ ＳＯＧ． 狇 ， 索进行校验， ， ｒａｍ技术快速排除掉不可能匹配的文本对剩下 以报告所有真正匹配的结果本质上 狇ｇ ． 可能匹配的文本和模式串进行比对随机数据集上 算法是一种过滤型串匹配算法，适合于模式串 ． ＳＯＧ 的实验表明， 命中较少的应用场景 该算法能够有效地进行万 万规 １ ～１０ ． 模的串匹配， ， 但是在 数据集上的实际效果不 直接使用 算法进行大规模 匹配其 ＵＲＬ ＳＯＧ ＵＲＬ 佳文献［］从 过滤的应用目的出发，提出了 匹配速度比较低下究其原因，存在如下两个方面的 ． １２ ＵＲＬ ． 一种 不足 ＵＲＬ散列与多模式串匹配算法相结合的方法， ： 以达到较高的查找速度和有效的内存利用率但是 （）哈希函数严重聚集与冲突： 算法与 ． １ ＳＯＧ 该方法只支持分节 ［］ ［］３ ４ 前缀匹配，并不支持子串 、 等算法一样，都使用哈希函数对可能 ＵＲＬ ＫＲ ＷＭ 匹配功能，因而限制了其应用范围 出现的匹配位置进行校验，以报告所有真正匹配的 ． 结果 综上所述，已有的算法比较适合中小规模的串 当模式串长度不相等时，算法需要从每个模式 ． 匹配，当模式串规模为几千时，现有算法的匹配效率 串中选取一个长度为犿的子串作为待查找的目标， 很高但是当模式串规模达到 万以上时，这些算 这里是最短模式串的长度选取的长度为的子 ． １０ 犿 ． 犿 法存在存储空间过大或匹配速度降低的问题 串称之为窗口 ， 无法 通常的窗口选择方法是从每个模式 ． 完全满足实际应用的需求同时，现有的匹配算法研 串中选取长度为的前缀或者后缀但是， 分 ． 犿 ． ＵＲＬ 究主要是针对一般的模式串（ 、 、 ） 布极不均匀， ， 随机串中文英文等 往往具有大量的相同前缀或者后缀从 ， （ 、 每个模式串中选取的长度为 进行优化针对特定类型模式串如ＵＲＬＥｍａｉｌ 犿的子串往往出现大 等）的研究工作很少因此，需要进一步研究针对大 量重复，导致哈希函数的严重聚集与冲突大量的模 ． ． 规模ＵＲＬ过滤的高效匹配算法． 式串散列到相同的位置，散列表中某些链表过长，大 幅度增加了校验的代价针对这一缺点，节提出 ． ３．２ 大规模 串匹配算法——— 最优窗口选择方法，为模式串选择合适的窗口子串， ３ 犝犚犔 犛犗犌犗犘犜 使得哈希函数的冲突达到最小． （） ： 较高的校验次数 算法是一种过滤型 ２ ＳＯＧ 算法 本节提出一种面向大规模 过滤的多模式 ，需要对可能出现匹配的位置进行校验校验是 ＵＲＬ ． 串匹配算法 极费时间的操作 ——— 该算法在经典的 ，校验次数越多，算法匹配速度越 ＳＯＧＯＰＴ． ＳＯＧ ［］ １１ 慢 算法的基础上，针对 的特点进行专门优化， 随着模式串集合的增大， 算法的校验次数 ＵＲＬ ． ＳＯＧ 以适应大规模 匹配的需求本文主要通过如 越来越高，算法匹配速度下降针对这一缺点，节 ＵＲＬ ． ． ３．３ 下两种优化技术来提高串匹配算法的速度：（）以 提出模式串分组规约方法，大幅度减少了 算法 １ ＳＯＧ 最大二部图匹配理论为基础，为 模式串选择 的校验次数 ＵＲＬ ． 最优的窗口，以减少哈希函数的冲突，使得 散 最优窗口选择 ＵＲＬ ３２ 列更加均匀；（）对 模式串进行分组规约，在 如上节所述，当模式串长度不相等时， 、、 ２ ＵＲＬ ＳＯＧＷＭ 同一个机器字内并行执行多组 算法，以达到减 等算法需要从每个模式串中选取一个长度为 ＳＯＧ ＫＲ 犿 少校验次数、提高匹配速度的目的 的子串作为待查找的目标，这里是最短模式串的 ． 犿 长度 在 节中，我们首先介绍原始 算法的基 选取的长度为的子串称之为窗口对于模 ３．１ ＳＯＧ ． 犿 ． （） （） （） （） 本思想 式串集合 １ ２ 狉 犻 ，并分析其对大规模 进行过滤时的不 ｛，，…，｝，其中 ＵＲＬ 犘＝狆狆 狆 狆＝ （）（） （） 足之处 犻 犻 犻 针对原始 算法的缺点，节和 … 有 种可供选择的窗口 ． ＳＯＧ ３．２ ３．３ 狆狆狆 犿－犿＋１ ． １ ２ 犿 犻 犻 节分别介绍本文提出的两种优化技术． 在经典的串匹配算法中，并没有考虑窗口选择 算法的基本思想及其不足 的问题在 、、等算法中，通常是截取每 ３１ 犛犗犌 ．ＳＯＧＷＭＫＲ ［］ １１ 个模式串中最左 算法是 等人提出的面向万 （或者最右）的个字符作为模式 ＳＯＧ Ｓａｌｍｅｌａ １０ 犿 规模模式串的匹配方法在随机数据集上的测试表 串的窗口，然后对这些窗口计算哈希值（不是对整个 ． 明，该算法优于众多其它经典串匹配算法该算法的 模式串计算哈希值），将模式串插入到散列表中 ． ． （） （） 基本思想是 １ ２ ：首先，将模式串集合 ｛，，…， 这种字符分布极不均匀的模式串，往往具有大 犘＝狆狆 ＵＲＬ （） 狉｝规约为一个通配形式的模式串；然后，使用位 量的相同前缀或者后缀，如果简单地选取最左（或者 狆 狆 并行串匹配算法 ［］５ 最右 对进行搜索；最后， ）的窗口进行散列，必然导致大量的 散列 ＳｈｉｆｔＯＲ 狆 ＵＲＬ １１６２ 计 算 机 学 报 ２０１４年 ， ， 到同一个桶中导致严重的哈希冲突哈希表的查找 ８．ＥＮＤＦＯＲ ９． （（，，）） 犚犕犪狓犅犻犪狉狋犻狋犲犕犪狋犮犺犻狀犌＝犞犞犈 ← 性能也十分低下为了减少串匹配算法中哈希表的 狆 犵 １ ２ ． （） 犽 （，）， １０．ｆｏｒｅａｃｈ ａｉｒ 狏犚ｓｕｂｓｔｒｉｎ 狏ｉｓｔｈｅ ｐ 狆 ∈ ｇ 冲突，本文提出一种最优的窗口选择方法，使得哈希 （） ｏｔｉｍａｌｗｉｎｄｏｗｆｏｒ ａｔｔｅｒｎｐ ｐ 犽 狆 表的均匀性最好该方法的基本思想是选出模式串 ． 基于最大二部图匹配的窗口选择方法虽然能得 中最独特、最具有区分度的子串，使得它能唯一代表 到理论上的最优解， ， 但是算法的时间复杂度很高１ 该模式串，即寻找模式串集合与其子串之间的一一 不适合在实际工程中应用为此，我们设计了一种快 ． 对应关系， ， 使得每个模式串尽可能对应不同的子串 速的近似算法来进行窗口选择， 以降低计算的代价 ． 从而最大程度地减少哈希函数的聚集与冲突通过 ． 近似算法的基本思想是：首先统计所有模式串中可 为每一个ＵＲＬ模式串选择合适的窗口，每个窗口 能出现的长度为犿的子串的出现频率（算法的第２ ， 唯一代表该 避免了相同前缀的 散列到 ＵＲＬ ＵＲＬ 行）子串出现频率越低，说明该子串是不常见 １ ７ ． ～ 同一个桶中 ． 的字符串，因而适合被选作模式串的窗口对于特定 ． 因为每个模式串有犿－犿＋１种可供选择的窗 犻 的模式串，选择其窗口为它所包含的长度为的子 犿 （） （） （） 口 １ ２ 狉 ，模式串集合 ｛，，…，｝上共有 犘＝狆狆 狆 串中出现频率最低者（算法的第 行）近似 ２ ８ １１ ． ～ 狉 算法的步骤如算法所示 （ ）种不同的窗口选择组合，简单的枚 ２ ． 犿－犿＋１ ∏犻 犻１ ＝ 算法 近似最优的窗口选择方法 ２． ． 举搜索显然是不可行的我们将上述最优窗口选择 ． （） （） （） １ ２ 狉 ： ｛，，…，｝ 输入模式串集合犘＝狆狆 狆 形式化为最大二部图匹配问题：设二部图为犌＝ 输出：各模式串的近似最优窗口 （） （） （） １ ２ 狉 （） （） （） （，，）模式串集合 ｛，，…，｝中 １ ２ 狉 犞犞犈． 犘＝狆狆 狆 （｛，，…，｝） １ ２ 犖犲犪狉犗狋犻犿犪犾犠犻狀犱狅狑犛犲犾犲犮狋犻狅狀犘＝狆狆 狆 狆 的模式串组成顶点集 模式串所有长度为的 １．犿ｍｉｎ ← ｜｜ 犞．１ 犿 狆 犘 ∈ 狆 ２． ［］ 子串组成顶点集 二部图中存在一条连接左侧 犮狅狌狀狋← 犞． 犌２ （） （）（） （） 犽 犽 犽 犽 ３．ＦＯＲｅａｃｈ ａｔｔｅｒｎ ＝ … 犘ＤＯ ｐ １ ２ 犿∈ 狆 狆狆 狆 顶点 和右侧顶点 的边 （，），当 犽 狌犞 狏犞 犲＝狌狏犈 ∈１ ∈２ ∈ （）（） （） 犽 犽 犽 ４．ＦＯＲｅａｃｈｓｕｂｓｔｒｉｎｇ狏＝ … （１ 犻 犻 犻＋１ 犻＋犿－１ （） （）（） 狆狆 狆 且仅当是的子串显然，模式串犻 犻 犻… 狏狌 ． ＝ 狆狆狆 １ ２ ） 犻犿－犿＋１ ＤＯ 犽 （） 犻在二部图中对应于 条边于是，模式 狆 犿－犿＋１ ． 犿 犻 ［］ ［］ 犻 ５．犮狅狌狀狋狏犮狅狌狀狋狏＋１ ← 犻 犻 串的最优窗口选择问题等价于求解二部图犌的最 ６．ＥＮＤＦＯＲ 大匹配问题，即为中的每一个顶点寻找一条边， ７．ＥＮＤＦＯＲ 犞１ （） （）（） （） 犽 犽 犽 犽 ８．ＦＯＲｅａｃｈ ａｔｔｅｒｎ ＝ … 犘ＤＯ ｐ １ ２ 犿∈ 狆 狆狆 狆 使得中的顶点出现的最多 犽 犞２ ． （）（） （） 犽 犽 犽 ９． ｛ ［］ … ， 狏 ａｒｍｉｎ犮狅狌狀狋狏狏＝ ←ｇ ｜ ｍｉｎ 犻 犻 犻 犻＋１ 犻＋犿－１ 狆狆 狆 利用最大二部图匹配理论选择最优窗口的过程 １ 犻犿－犿＋１｝ 犽 如算法所示首先，根据模式串集合构造二部 （） １ ． 犘 犽 １０．狏ｉｓｔｈｅｎｅａｒｏｔｉｍａｌｗｉｎｄｏｗｆｏｒ ａｔｔｅｒｎｐ ｐ ｍｉｎ 狆 图（算法的第 行），然后使用经典的最大流算 １ １ ８ ～ １１．ＥＮＤＦＯＲ （ ）， 法求解最大二部图匹配算法的第行最后根 １ ９ 算法和算法的时间复杂度和空间复杂度分 １ ２ 据二部图匹配的结果为每个模式串选择最优的窗口 析如下． 算法的第行 ２ ２ （ ） 定理 算法的时间复杂度为（ ），空 １ １０ ． １． １ 犗狉犔 算法 基于最大二部图匹配的最优窗口选 间复杂度为（），其中是模式串的个数，为模 １． 犗狉犔 狉 犔 择方法． 式串的平均长度． （） （） （） １ ２ 狉 输入：模式串集合 ｛，，…，｝ 犘＝狆狆 狆 证明根据最大流算法的理论，最大二部图匹配 ． 输出：各模式串的最优窗口 的时间复杂度为（ ），空间复杂度为（ 犗犞犈 犗犞＋ ｜｜｜｜ ｜｜ （） （） （） １ ２ 狉 （｛，，…，｝） 犗狋犻犿犪犾犠犻狀犱狅狑犛犲犾犲犮狋犻狅狀犘＝狆狆 狆 狆 ），其中 是二部图的顶点数，是二部图的边 犈 犞 犈 ｜｜ ｜｜ ｜｜ １．犿ｍｉｎ ← ｜｜ 狆 犘 ∈ 狆 数算法的主要时间开销为计算最大二部图匹配， ． １ ２． ， ， 犞犘犞 犈 １← ←←２ 狉 （） （）（） （） 犽 犽 犽 犽 ３．ＦＯＲｅａｃｈ ａｔｔｅｒｎ ＝ … 犘ＤＯ ｐ １ ２ 犿∈ 狆 狆狆 狆 二部图的顶点数 （ ） 犽 犞＝犗狉＋ 犿－犿＋１ ＝ ｜｜（∑犻 ） （）（） （） 犽 犽 犽 犻１ ＝ ４．ＦＯＲｅａｃｈｓｕｂｓｔｒｉｎｇ狏＝ … 犻 犻 犻＋１ 犻＋犿－１ 狆狆 狆 狉 （ ） １ 犻犿－犿＋１ ＤＯ 犽 （），边数 （ ） （），因 犗狉犔 犈犗 犿－犿＋１ ＝犗狉犔 ＝ ｜｜（ 犻 ） ∑ （） 犽 犻１ ５． ｛（，）｝ ＝ 犈犈 狏 ←∪狆犻 ２ ２ 此算法的时间复杂度为（ ）（ ）， １ 犗犞犈＝犗狉犔 ｛｝ ｜｜｜｜ ６．犞犞 狏 ←∪ ２ ２ 犻 ７．ＥＮＤＦＯＲ 空间复杂度为（ ）（） 证毕 犗犞 犈＝犗狉犔． ． ＋ ｜｜｜｜ ５期 刘燕兵等：一种面向大规模 过滤的多模式串匹配算法 ＵＲＬ １１６３ 定理 算法的时间复杂度为（ ）， （ ） ２． ２ 犗狉犔ｌｏ狉犔 犖犖＋１ｇ 犻 犻 ， 因此查询 个 的平均代价为 犖 ＵＲＬ （），