【算法】AC自动机的优化:增量更新与删除

一、概述

AC自动机(Aho-Corasick Automation)是著名的多模匹配算法,源于贝尔实验室,并且在实际应用中得到广泛的引用,且具有以下特点:

  • 只需要扫描一次文本,即可获取所有匹配该文本的模式串
  • 复杂度O(n)
  • 以树的结构进行存储
  • 通过Fail节点和Fail指针来提高匹配效率

对于AC自动机的具体实现,感兴趣可以自行搜索。

但是在实际应用场景中,AC自动机不仅仅只考虑匹配模式,还要考虑其模式串数据源的处理,比如模式串数据源的频繁变动(更新or移除数据),针对这样的情况下如果不断地对AC检测树进行推倒重建,在性能上消耗是十分庞大的。

因此,基于这样的场景,我们需要支持动态、快速、便捷地对已生成的AC检测树进行数据的插入、删除。

二、原理

原理很好理解,即:

  1. 新增节点自前往后遍历,删除节点自后往前遍历,逐一获取需要新增/删除的节点
  2. 更新指向该节点的Fail指针
  3. 更新该节点指向的Fail节点
  4. 在AC检测树中合并/移除该节点

在第2步中,原来的AC检测树的节点是不记录相关信息的,因此需要引入一个列表来管理该信息。

1. 新增节点

新增节点,即需要将新增加需要匹配的模式串源数据合并到已构建好的AC检测树中。

假定新增模式串为Z,已构建的AC检测树为AC_TREE

  • 判断ZAC_TREE的中最长前缀,并记录最长前缀的最后一个节点NODE
  • NODE作为遍历起点并开始遍历Z
    • 为新字符NEW_CHAR创建节点NEW_NODE并添加到NODE
    • 沿着NODE的Fail指针向上查找,直至找到某个节点下的子节点是NEW_CHAR,记录该节点的子节点为NEW_FAIL_NODE(如果没找到,则NEW_FAIL_NODE = ROOT
    • 更新NEW_NODE的Fail节点为NEW_FAIL_NODE
    • 获取Fail节点为NODE的节点列表REVER_NODE_LIST,并遍历
      • 判断REVER_NODE_LIST中节点的子节点REVER_CHILD_NODE的值是否有NEW_CHAR,如果有,则将REVER_CHILD_NODE的Fail节点设置为NEW_NODE,并更新NEW_NODEREVER_NODE_LIST
    • 设置NEW_NODE的其他属性

图文说明:

【初始状态】
在这里插入图片描述
【新增模式串后:ers】
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2. 删除节点

删除节点,即需要将某些模式串源数据已构建好的AC检测树中移除。

假定移除的模式串为Z,已构建的AC检测树为AC_TREE

  • 判断ZAC_TREE的位置,找到Z最后一个字符在AC_TREE中的节点NODE(如果不存在该模式串则跳出处理流程)
  • NODE作为遍历起点并开始反向遍历Z
    • 判断NODE是否存在其他子节点,有则跳出循环
    • 获取Fail节点为NODE的节点列表REVER_NODE_LIST,并遍历
      • REVER_NODE_LIST中的节点REVER_NODE的Fail节点设置为NODE的Fail节点
      • 更新NODEREVER_NODE_LIST
    • 更新NODE的Fail节点为NULL
    • 删除NODE,并更新NODE的父节点PARENT_NODE的子节点列表

图文说明:

【初始状态】
在这里插入图片描述

【删除模式串后:ers】
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

三、实现流程

P.S. 通过伪代码形式给出主要代码流程

// 新增节点
AddNode(list[str_1..str_n])
	for i ← 0 to n-1 do
    	str ←  list[i]; pos ← 0; node ← root
    	for j ← pos to str.len() do
    		pos ← j
    		node ← node.childNodeList[str[pos]]
   		
   		now_node ← node 
   		for j ← pos to str.len() do
   			chr ← str[j]
   			 // 查找Fail节点
   			fail_node ← GetFailNode(now_node, chr)
   			
   			// 创建新节点
   			next_node  ← CreateNewNode(now_node, chr) 
   			next_node, fail_node ← SetFailNode(next_node, fail_node)
   			
   			// 处理需要指向该节点的Fail指针
   			for k ← 0 to now_node.reverseFailNodeList do
   				tmp_node ← now_node.reverseFailNodeList[k][chr]
   				tmp_node , next_node ← SetFailNode(tmp_node , next_node)
   				now_node. reverseFailNodeList[k].childNodeList[chr] ← tmp_node 
   			

// 删除节点
DelNode(list[str_1..str_n])
	for i ← 0 to n-1 do
    	str ←  list[i]; pos ← 0; node ← root; nodeList  ← []
    	for j ← pos to str.len() do
    		pos ← j
    		nodeList.add(node)
    		node ← node.childNodeList[str[pos]]
    	
    	nodeList.reverse()
    	for j ← pos to str.len() do
    		now_node ← nodeList[j]
			fail_node ← now_node.faliNode
			// 处理指向该节点的所有Fail指针
			for k ← 0 to now_node.reverseFailNodeList do
				tmp_node ← now_node.reverseFailNodeList[k][chr]
   				tmp_node , next_node ← SetFailNode(tmp_node , next_node)
   				now_node. reverseFailNodeList[k].childNodeList[chr] ← tmp_node
   			
   			// 处理当前节点的Fail节点
  			now_node, tmpFail_node← SetFailNode(now_node, NULL) 

			// 删除该节点
			delete now_node.parentNode.childNodeList[now_node.char]
			

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/466645.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

svg代码应用于button

将svg代码的path属性应用于按钮内容&#xff0c;去掉按钮边框&#xff0c;并且自适应svg大小&#xff0c;以下实现的是一个旋转按钮。 svg代码如下(iconfont下载)&#xff1a; <svg t"1710741485848" class"icon" viewBox"0 0 1024 1024" ve…

SpringCloudLoadBalancer入门与实战系列

目录 一、什么是LoadBalancer&#xff1f; 1.1 负载均衡的分类 1.2 负载均衡策略 二、 为什么要学习 Spring Cloud Balancer &#xff1f; 三、 Spring Cloud LoadBalancer 内置的两种负载均衡策略 3.1 轮询负载均衡策略&#xff08;默认的&#xff09; 3.2 随机负载均衡…

高防服务器秒解是什么意思

高防服务器秒解是指高防服务器在遭受大规模的DDoS攻击时&#xff0c;能够迅速解决问题或应对攻击。DDoS攻击是指攻击者通过向目标服务器发送大量的请求&#xff0c;使服务器资源耗尽或无法正常响应其他合法用户的请求&#xff0c;从而导致服务不可用。高防服务器通过具备高性能…

C++容器适配器与stack,queue,priority_queue(优先级队列)的实现以及仿函数(函数对象)与deque的简单介绍

&#x1f389;个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名乐于分享在学习道路上收获的大二在校生 &#x1f648;个人主页&#x1f389;&#xff1a;GOTXX &#x1f43c;个人WeChat&#xff1a;ILXOXVJE &#x1f43c;本文由GOTXX原创&#xff0c;首发CSDN&…

centos云服务器安装cs(cobaltstrike4.0)教程

1、先安装JAVA环境 mkdir download #创建download目录 cd download #进入download目录 mkdir java1.8 #在download目录下再创建java1.8目录 cd java1.8 #进入java1.8目录 wget https://repo.huaweicloud.com/java/jdk/8u201-b09/jdk-8u201-linux-x64.tar.gz #下载jdk压缩包 tar…

积分法卷径计算(CODESYS ST完整源代码)

在学习积分法卷径计算课程之前大家需要属性下PLC的数值积分器运算。 1、博途PLC积分法卷径计算完整源代码 https://rxxw-control.blog.csdn.net/article/details/136719982https://rxxw-control.blog.csdn.net/article/details/1367199822、转动圈数累积功能块 https://rxxw…

代码随想录算法训练营三刷day27 | 回溯之 39. 组合总和 40.组合总和II 131.分割回文串

三刷day27 39. 组合总和回溯三部曲剪枝优化 40.组合总和II回溯三部曲 131.分割回文串回溯三部曲判断回文子串 39. 组合总和 题目链接 解题思路&#xff1a; 本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本…

组件化开发

一、引言 Vue.js 的组件化开发是其核心特性之一&#xff0c;它允许开发者将复杂的界面拆分为可复用的、独立的、小的组件&#xff0c;从而提高开发效率和代码的可维护性。 二、关键点 1.组件的定义 在components下创建.vue文件timecard.vue用来编辑内容。 文件创建完毕后&am…

我的导航学习笔记仓库大改版,欢迎关注!!

链接&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 我的导航学习笔记&#xff0c;内容涵盖导航定位开源程序的源码解读 ( 包括&#xff1a;RTKLIB、GAMP、SoftGNSS、KF-GINS、ORB-SLAM3 等)、各种导航设备的使用方式、书籍讲义、博客翻译、开源项目梳理、…

python爬取微博话题、关键词下方的所有帖子

文章目录 github repository项目介绍输出安装必备库获取cookiegithub repository 网址:https://github.com/dataabc/weibo-search 在GitHub获取到的非常成熟的微博话题、关键词等微博帖子的获取方案,并且可以指定一个或多个关键词,指定获取微博类型,指定获取日期等等。 项…

文件处理(二)

CSV文件的读取和写入 CSV文件的操作 csv是逗号分隔符文本格式&#xff0c;常用于数据交换、Excel文件和数据库数据的导入和导出。 与Excel文件不同&#xff0c;CSV文件中&#xff1a; 值没有类型&#xff0c;所有值都是字符串不能指定字体颜色等样式不能指定单元格的宽高&…

全网最全100个AI工具导航网站合集

随着ChatGPT年前的爆火&#xff0c;人工智能也变成当今最热门的领域之一&#xff0c;它正在改变着我们的生活和工作方式。无论你是想要学习人工智能的基础知识&#xff0c;还是想要利用人工智能来提升你的业务效率和创新能力&#xff0c;都需要找到合适的AI工具来帮助你实现目标…

VS Code安装Live Server插件搭建web网页结合内网穿透实现公网访问

文章目录 前言1. 编写MENJA小游戏2. 安装cpolar内网穿透3. 配置MENJA小游戏公网访问地址4. 实现公网访问MENJA小游戏5. 固定MENJA小游戏公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&…

数仓建模简介

1 建模的意义 如果把数据看作图书馆里的书&#xff0c;我们希望看到它们在书架上分门别类地放置&#xff1b;如果把数据看作城市的建筑&#xff0c;我们希望城市规划布局合理&#xff1b;如果把数据看作电脑文件和文件夹&#xff0c;我们希望按照自己的习惯有很好的文件夹组织方…

docker小白第十二天

docker小白第十二天 docker network简介 docker不启动时默认的网络情况。 # 停止docker服务 systemctl stop docker.socket systemctl stop docker # 查看docker镜像 docker images输入查看docker镜像命令后&#xff0c;显示未连接到docker服务器 docker启动时网络情况 sy…

async与defer的区别

原文解释 async vs defer attributes - Growing with the Web

【OpenCV • c++】图像平滑处理(1) —— 线性滤波

文章目录 一、平滑处理二、图像滤波三、邻域算子与线性邻域滤波四、方框滤波代码演示 一、平滑处理 平滑处理也称为模糊处理&#xff0c;是一种简单且使用频率很高的图像处理方法&#xff0c;平滑处理的用途有很多&#xff0c;最常见的是用来减少图像上的噪点或者失真。在涉及到…

资深老鸟,性能测试-TPS上不去分析+电商系统TPS计算(详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、性能测试-TPS上…

YOLOv9详解

1.概述 在逐层进行特征提取和空间转换的过程中&#xff0c;会损失大量信息&#xff0c;例如图中的马在建模过程中逐渐变得模糊&#xff0c;从而影响到最终的性能。YOLOv9尝试使用可编程梯度信息PGI解决这一问题。 具体来说&#xff0c; PGI包含三个部分&#xff0c;&#xff0…

C语言例:表达式 45-35+1^2 的值

代码如下&#xff1a; #include<stdio.h> int main(void) {int a;a 4&5-3&&51^2;printf("4&5-3&&51^2 %d\n",a);return 0; } 结果如下&#xff1a;