热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

【模式匹配】之——多模匹配下篇(AC算法之前缀树实现)

前言本文章对应代码下载地址:http:download.csdn.netdetailsun20434305286986AC算法之前缀树实现步骤步骤一构造前缀树步骤二设置每一个节点的Fai

前言

本文章对应代码下载地址:

http://download.csdn.net/detail/sun2043430/5286986


AC算法之前缀树实现步骤

  1. 步骤一 构造前缀树
  2. 步骤二 设置每一个节点的Failure Node
  3. 步骤三 收集每个节点的所有匹配模式串信息
  4. 步骤四 对目标串进行搜索匹配

AC自动机进行字符串匹配的过程,可以参考维基百科的说明:

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm


具体的实现方法就是创建一颗前缀树,根据被查找目标字符串,逐字符匹配目标字符串,从树的根节点往叶子节点一步步查找下去。在这个过程当中,如果失配了,要根据失配跳转点来进行跳转,如果找到匹配的模式串则进行打印输出。这样说还是只有一个模糊的大概印象,我们先看一个简单的例子,然后一步步说明具体的操作步骤。


步骤一:构造前缀树

比如我们现在有5个待搜索模式串:
"uuidi"

"ui"

"idi"

"idk"

"di"

建立如下所示的前缀树:


(图1)

其中,根节点Root为空,不表示任何字符,其ID为0。依次读取每一个模式串,将模式串的每一个字符添加到树上,并依次顺序编号,编号用红色数字显示在节点的右边,每一个叶子节点用黄色背景表示(5,6,9,10,12号节点),表示这里到达一个模式串的结尾(下文称之为尾节点)。如果2个模式串有相同的前缀,则相同的前缀共用相同的节点。例如"uuidi"、"ui"有共同前缀"u","idi"、"idk"有共同前缀"id"。

从根节点Root开始,每一个节点的孩子节点表示在此节点可以匹配哪些字符,例如根节点有三个孩子节点1,7,11,则根节点处可以匹配u,i,d三个字符,如果目标字符串相应位置上是这3个字符中的一个,则匹配上某一个孩子节点,接下来的匹配将从该孩子节点继续下去。这是可以匹配上的情况,还有不匹配的情况,对于不匹配的情况我们不是跳回到根节点处重新进行匹配(这样会造成目标字符串的回溯),而是模仿KMP算法中失配时,跳转到Failure Node(失配跳转节点)。例如目标字符串是"uuidk",我们按照上面构造出的树,会依次经过1,2,3,4节点(匹配上uuid),4的孩子节点5是i,不能匹配上目标串中的k,这个时候我们应该从4跳转到节点8,我们称8是4的Failure Node。

对于每一个树上的节点都应该有对应的Failure Node,以指示在不匹配的情况应该跳转到哪个节点继续进行匹配。


步骤二:设置每一个节点的Failure Node

上面我们举了一个例子,在节点4失配时,应该跳转到节点8去继续进行匹配,这和KMP算法中在失配时根据失配跳转next数组中记录的位置来进行跳转的原理是一样的,目的是避免对目标串进行回溯匹配。在KMP算法中求next数组值可以用迭代的方法计算出来,但多个模式串的情况下,我们计算Failure Node只能从树的根节点处开始遍历。但是Failure Node的作用和KMP中的next数组值是一样的,查找的原则也是一样的,就是在模式串中查找最长前缀能够匹配上当前失配位置处的最长后缀

仍以上面图中的节点4来举例,到达节点4的模式串为uuid,对应的后缀为"uid","id","d"(在程喆师弟的指正下修改此处笔误),我们要找树的前缀中,能匹配上这三个后缀且长度最长的那个位置,首先看"uid",从树的根节点开始(因为要找前缀)没有能匹配上的,在找"id",找到能匹配上的节点7,8。所以我们设置4的Failure Node为8。如果没有找到能匹配的前缀,则设置Failure Node为根节点Root。

:可能有看过KMP算法的同学会注意到,我们在找到最长后缀的同时还要看后面的孩子节点是否一样,如果找到的位置后面的孩子节点和本节点的孩子节点一样,那么跳转过去,也必然导致失配。实际上确实如此,但我们仍然简单处理,只看前缀和后缀是否匹配,而不管后面的孩子节点是否一样,其原因我们在后面说明。

针对上图的12个节点,每个节点对应的Failure Node如下表:


(图2)

将每个Failure Node不为0的节点,和其对应的Failure Node节点,用绿色虚线连接起来(绿色通道快捷跳转、虚线表示比较隐蔽不容易发现^_^),形成上图。

每个节点K的Failure Node节点的深度不会超过该节点K的深度,因为从跟节点到Failure Node节点是一个前缀。

另外每个节点K的Failure Node节点只有一个,不会有多个。因为Failure Node节点的定义是长度最长的前缀匹配失配位置的后缀,长度最长的只可能找到一处,不可能找到两处,如果有两处长度一样,且都是能够匹配的前缀,那么这两个分支按照前缀树的构造方法应该是重合在一起的。


构造完前缀树,设置好每一个节点的Failure Node之后,我们还有一件重要的事情没有做,观察上面的前缀树,当我们来到节点3时,节点2,3组成的字串"ui"其实已经匹配上一个模式串了,但节点3不是一个模式串的尾字符,所以我们无法报告给查询者,我们其实已经匹配上一个模式串了;另外看节点5,当到达节点5时,我们除了匹配上了"uuidi"字串之外,其实我们也匹配上了"idi","di"字符串。为了解决这个问题,我们需要收集每一个节点的模式串匹配情况。


步骤三:收集每个节点的所有匹配模式串信息

其实要收集每个节点的所有匹配模式串也很简单,观察图2,在节点3位置,应该报告匹配上了模式串"ui",我们可以看到节点3的Failure Node指向的是节点6。所以获取每个节点的所有匹配模式串的信息可以从该节点的Failure Node入口,如果节点K的Failure Node是一个尾节点,那么到达节点K相当于匹配上了一个模式串。另外,我们再观察节点5,节点5本身就是一个尾节点,所以它有自己的匹配模式串,再看5的Failure Node,指向9,节点9也是尾节点,所以5的匹配模式串除了自身的一个模式串(uuidi)之外还包括9所代表的模式串(idi),而9的Failure Node指向12,12也是一个尾节点,所以节点5也也应该包含节点12的匹配模式串(di)……这样进行下去,一直到Failure Node指向了根节点,遍历结束,遍历过程中遇到的所有尾节点都是可匹配的模式串。

在具体的代码实现中,我用一个std::verctor容器来保存一个节点所有的可匹配模式串信息。另外现在我们可以回答一下上面提到的问题。为什么我们没有去检查节点和其Failure Node节点是否有相同的孩子,比如图2中的节点8,我们上面计算出来8的Failure Node是11,但其实因为8有2个孩子9,10,如果8接下来的匹配失配,也就说明目标串中现在出现的字符不是i(9),k(10),而11的孩子节点12表示(i),则通过Failure Node到达11也必然是会匹配失败的。但是我们仍然设置8的Failure Node为11,是因为如果漏掉过了节点11,我们有可能会漏掉匹配的模式串。例如,5的Failure Node是9,9的Failure Node是12,12的Failure Node是7,如果我们因为5,9,12都没有孩子节点,而直接设置节点5的Failure Node为节点7,那么我们在收集所有的匹配模式串信息时,会漏掉尾节点9,12。

可以考虑一个更极端的情况,比如这样的模式串集:"aaaa","aaa","aa","a",如果我们考虑到节点K的Failure Node的孩子结点不应该全都包含在节点K的孩子节点中(和KMP求NEXT数组前缀和后缀的后一个字符不应该一样同理),那么我们在目标串"aaaaaaaaaaa"查找模式串集时会漏掉一些匹配的模式串信息报告。

下图显示了构造树的情况,depth是树的高度,ID=0的节点是Root。Children后面显示的是当前节点的孩子节点,Match pattern后面列出了在该节点位置能匹配上的模式串。

其中:

节点3  Match pattern: "ui"

节点5  Match pattern: "uuidi" "idi" "di"

节点6  Match pattern: "ui"

节点9  Match pattern: "idi" "di"

节点10 Match pattern: "idk"

节点12 Match pattern: "di"


步骤四:对目标串进行搜索匹配

上面3个步骤都完成了之后就可以开始对目标串进行搜索了,很简单的从头到尾线性扫描过程,且目标字符串没有回溯。

搜索之前先记录一个树的当前节点CurNode,初始时,树的当前节点CurNode为根节点Root

从目标串的第一个字符开始,和Root的孩子节点进行匹配,如果不匹配,则目标字符串往后挪一个字符,继续在Root的孩子节点中查找匹配。

如果找到匹配的孩子,则目标字符串往后挪一个字符,CurNode变为匹配上的孩子节点。在接下来的匹配过程中,如果失配将跳转到CurNode节点的Failure Node处继续进行匹配。

在树上每次往孩子节点方向走一步都要检查该孩子节点的匹配模式串信息,如果有匹配的模式串信息,则应该报告搜索者找到了哪些能够匹配的模式串。


对代码的一些说明

代码有两个,1个是在维基百科“Aho–Corasick string matching algorithm”词条给出的链接,地址为:

http://sourceforge.net/projects/multifast/

使用C语言编写,函数式实现,里面含有大量英文注释,理解原理在看代码应该很不难看懂。


另外一个我写的C++代码,使用类的方式,调用起来比较方便,当然我没有加很多的注释,一些细节可能需要阅读者自己琢磨一下。本文中的例子、图片,均来自我实现的代码。

构造树的过程调用

bool CTrie::Create(const MY_PATTERN pattern[], int nCount)
在该函数内部调用了CTrie::SetFailure()设置每个节点 Failure Node,调用CTrie::SetMatchPattern(NODE *pNode)设置每一个节点的所有匹配模式串信息。

因为是多叉树结构,所以上面两个函数都是从根节点向叶子节点的深度优先递归调用。

前缀树构造完毕之后就可以开始在目标字符串中查找匹配的模式串了,例如在目标字符串"hello uuididkidid"中查找图1所示的5个模式串,显示的结果如下:

下标数:0         1         2         3
下标数:0123456789012345678901234567890123456789
目标串:hello uuididkidid
Match pattern at 8:
    "ui"
Match pattern at 10:
    "uuidi"
    "idi"
    "di"
Match pattern at 12:
    "idk"
Match pattern at 15:
    "idi"
    "di"


本文章对应代码下载地址:

http://download.csdn.net/detail/sun2043430/5286986



推荐阅读
  • 通过利用代码自动生成技术,旨在减轻软件开发的复杂性,缩短项目周期,减少冗余代码的编写,从而显著提升开发效率。该方法不仅能够降低开发人员的工作强度,还能确保代码的一致性和质量。 ... [详细]
  • 本文详细介绍了一种利用 ESP8266 01S 模块构建 Web 服务器的成功实践方案。通过具体的代码示例和详细的步骤说明,帮助读者快速掌握该模块的使用方法。在疫情期间,作者重新审视并研究了这一未被充分利用的模块,最终成功实现了 Web 服务器的功能。本文不仅提供了完整的代码实现,还涵盖了调试过程中遇到的常见问题及其解决方法,为初学者提供了宝贵的参考。 ... [详细]
  • 本文详细介绍了在Linux系统上编译安装MySQL 5.5源码的步骤。首先,通过Yum安装必要的依赖软件包,如GCC、GCC-C++等,确保编译环境的完备。接着,下载并解压MySQL 5.5的源码包,配置编译选项,进行编译和安装。最后,完成安装后,进行基本的配置和启动测试,确保MySQL服务正常运行。 ... [详细]
  • 深入解析 Java 程序的执行机制与运行流程
    本文深入探讨了Java程序的执行机制与运行流程,详细解析了从源代码编译到字节码生成,再到JVM加载和执行的全过程。通过实例分析,读者可以更好地理解Java虚拟机的工作原理及其在实际开发中的应用。 ... [详细]
  • 在同一个应用程序中,`Class JavaLaunchHelper` 存在多个实现版本,导致了 objc 系统报告冲突。具体表现为:objc[64179] 指出 `Class JavaLaunchHelper` 在两个不同的路径中被实现,这可能会影响应用程序的稳定性和性能。为了解决这一问题,建议检查并统一 `JavaLaunchHelper` 的实现版本,确保其唯一性。 ... [详细]
  • 在PHP多线程扩展开发中,面临的主要挑战之一是多线程调用PHP用户类方法时可能出现的内存错误。具体表现为当多个线程同时调用同一个类实例的同一方法时,系统会抛出内存错误。为了解决这一问题,本文深入分析了PHP多线程扩展的实现机制,并提出了几种有效的解决方案和技术思路,包括线程安全的类设计、内存管理优化以及线程同步机制的改进。通过这些方法,可以显著提升PHP多线程扩展的稳定性和性能。 ... [详细]
  • 在Java Web服务开发中,Apache CXF 和 Axis2 是两个广泛使用的框架。CXF 由于其与 Spring 框架的无缝集成能力,以及更简便的部署方式,成为了许多开发者的首选。本文将详细介绍如何使用 CXF 框架进行 Web 服务的开发,包括环境搭建、服务发布和客户端调用等关键步骤,为开发者提供一个全面的实践指南。 ... [详细]
  • 为了优化用户体验,本文探讨了如何调整下拉菜单的宽度。通过合理设置宽度,可以提升界面的美观性和易用性。文章提供了具体的代码示例,帮助开发者实现这一目标。例如,可以通过 CSS 或 JavaScript 来动态调整下拉菜单的宽度,确保其在不同设备和屏幕尺寸上都能保持良好的显示效果。 ... [详细]
  • 本指南介绍了 `requests` 库的基本使用方法,详细解释了其七个主要函数。其中,`requests.request()` 是构建请求的基础方法,支持其他高级功能的实现。此外,我们还重点介绍了如何使用 `requests.get()` 方法来获取 HTML 网页内容,这是进行网页数据抓取和解析的重要步骤。通过这些基础方法,读者可以轻松上手并掌握网页数据抓取的核心技巧。 ... [详细]
  • 在iOS开发中,基于HTTPS协议的安全网络请求实现至关重要。HTTPS(全称:HyperText Transfer Protocol over Secure Socket Layer)是一种旨在提供安全通信的HTTP扩展,通过SSL/TLS加密技术确保数据传输的安全性和隐私性。本文将详细介绍如何在iOS应用中实现安全的HTTPS网络请求,包括证书验证、SSL握手过程以及常见安全问题的解决方法。 ... [详细]
  • 在日常开发中,正则表达式是处理字符串时不可或缺的工具。本文汇总了常用的正则表达式,帮助开发者高效解决常见问题。例如,验证数字:`1$`;验证n位数字:`^\d{n}$`;验证至少n位数字:`^\d{n,}$`;验证m到n位数字:`^\d{m,n}$`。此外,还涵盖了验证零和非零数字、邮箱地址、手机号码等多种场景,建议关注并收藏以备不时之需。 ... [详细]
  • Gliffy Diagrams:高效实用的流程图绘制工具
    Gliffy Diagrams 是一款高效且易于使用的流程图绘制工具,能够显著提升工作效率。结合百度脑图等辅助工具,用户可以更加便捷地创建和管理各种图表。本文详细介绍了 Gliffy Diagrams 的核心功能和使用方法,帮助读者快速上手。 ... [详细]
  • 本文深入探讨了Java多线程环境下的同步机制及其应用,重点介绍了`synchronized`关键字的使用方法和原理。`synchronized`关键字主要用于确保多个线程在访问共享资源时的互斥性和原子性。通过具体示例,如在一个类中使用`synchronized`修饰方法,展示了如何实现线程安全的代码块。此外,文章还讨论了`ReentrantLock`等其他同步工具的优缺点,并提供了实际应用场景中的最佳实践。 ... [详细]
  • 斯坦福大学公开课:利用神经网络技术实现自动驾驶的案例分析
    斯坦福大学的公开课深入探讨了如何利用神经网络技术实现自动驾驶。课程中通过实例展示了汽车如何通过学习算法自主驾驶。具体而言,课程展示了一幅图解,其中左下角显示了汽车前方的实时路况图像,而左上角则呈现了一个水平的菜单栏,用于展示系统处理和决策的过程。这一案例详细解析了神经网络在自动驾驶中的应用,为学生提供了宝贵的实践参考。 ... [详细]
  • 深入解析IP地址、子网掩码与网关的基本概念——Vecloud微云网络技术详解
    本文旨在为网络新手详细解析IP地址、子网掩码和网关的基本概念。IP地址用于唯一标识网络中的设备,类似于现实生活中的身份证;子网掩码则用于确定IP地址中网络部分和主机部分的划分;而网关则是连接不同网络的桥梁,使数据能够在不同的网络间传输。通过这些基础概念的深入理解,读者将能够更好地掌握网络通信的核心原理。 ... [详细]
author-avatar
soseast9975
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有