Aho Corasick Algorithm
文章目录
- 前言
- 介绍
- 实现
- 参考
前言
Aho Corasick Algorithm又叫AC自动机,该算法是一个匹配算法,用来匹配文本Text中多个patterns分别出现的次数;
我们定义n为patterns的总长度;m为Text的长度;
问题:在ahishershe文本中找出以下"he", "she", "hers", "his"各个patterns出现的次数;
最直接的暴力解法时间时间复杂度为O(n*m),如果采用KMP Algorithm,会把时间度降低为O(n+m),但是这是在单一的pattern的情况下,在k个pattern的情况下,应该成倍的增长m,时间复杂度为O(n+k*m),使用Aho Corasick Algorithm可以把时间优化为O(n+m+z),其中z表示出现的次数;
介绍
AC自动机利用的前缀树Trie这一数据结构;前缀树是一种很简单的结构,其构造如下:
我们可以构建Trie然后使用窗口进行暴力搜索,其时间复杂度为O(m*max(L)),这里面的max(L)是Trie的深度;
这里面可以优化的一个点是,我们可以利用不匹配词的最长后缀作为词的前缀去优化查找,而不是不匹配就重新从root开始;找到最长的公共后缀将保证我们不需要再次检查那么多字符串,并且在每次不匹配之后我们都会重复上一步骤;
如图所示:
这些指向最长后缀的节点的链接被称为suffix links或failure links,在匹配不成功的时候,若有最长的后缀节点,指向最长的后最节点,若没有则指向root进行重新查找;
假设在一颗Trie上有字符串w,x,...,其中x是w的最长的后缀,所以有红线连接w和a,若存在wa和xa,这xa也是wa的最长后缀,也用红线连接;
若xa不存在,就去找除了x以外的和w的最大公共后缀,如果发现y符合条件,可以对y进行匹配;如果y不符合条件,就接着找除了x,y以外的和w的最大公共后缀,依次进行;
其次需要优化的一点输出环节,如果pattern1是pattern2的后缀的情况下,我们可能会忽略掉pattern1,所以在寻找最大后缀时需要进行判断,如果最大后缀结点是pattern,就用output link连接原结点指向该结点,在以该结点为原结点去连接,直到root;如果不是就判断该结点的最大后缀结点是否是pattern,再用原结点去连接这一个结点;
在文本sting中,遍历到i的时候,可以发现sti的最大后缀ti并不是pattern,于是就找ti的最大后缀i,是pattern,于是用蓝色的线把sti和i结合起来;这里加粗了这一过程;
在遍历到n的时候,发现tin和in都是pattern,依次进行连接
这时时间复杂度为O(m+z),其中z表示pattern的出现次数;
实现
下面是python实现的代码:
from collections import defaultdictclass ahocorasick:def __init__(self, words):self.max_states = sum([len(word) for word in words])self.max_characters = 26self.out = [0] * (self.max_states + 1)self.fail = [-1] * (self.max_states + 1)self.goto = [[-1] * self.max_characters for _ in range(self.max_states + 1)]for i in range(len(words)):words[i] = words[i].lower()self.words = wordsself.states_count = self.__build_matching_machine()def __build_matching_machine(self):k = len(self.words)states = 1for i in range(k):word = self.words[i]current_state = 0for character in word:ch = ord(character) - 97if self.goto[current_state][ch] == -1:self.goto[current_state][ch] = statesstates += 1current_state = self.goto[current_state][ch]self.out[current_state] |= (1 << i)for ch in range(self.max_characters):if self.goto[0][ch] == -1:self.goto[0][ch] = 0queue = []for ch in range(self.max_characters):if self.goto[0][ch] != 0:self.fail[self.goto[0][ch]] = 0queue.append(self.goto[0][ch])while queue:state = queue.pop(0)for ch in range(self.max_characters):if self.goto[state][ch] != -1:failure = self.fail[state]while self.goto[failure][ch] == -1:failure = self.fail[failure]failure = self.goto[failure][ch]self.fail[self.goto[state][ch]] = failureself.out[self.goto[state][ch]] |= self.out[failure]queue.append(self.goto[state][ch])return statesdef __find_next_state(self, current_state, next_input):answer = current_statech = ord(next_input) - 97while self.goto[answer][ch] == -1:answer = self.fail[answer]return self.goto[answer][ch]def search_words(self, text):text = text.lower()current_state = 0result = defaultdict(list)for i in range(len(text)):current_state = self.__find_next_state(current_state, text[i])if self.out[current_state] == 0: continuefor j in range(len(self.words)):if (self.out[current_state] & (1 << j)) > 0:word = self.words[j]result[word].append(i - len(word) + 1)return resultif __name__ == "__main__":words = ["he", "she", "hers", "his"]text = "ahishershe"aho_chorasick = ahocorasick(words)result = aho_chorasick.search_words(text)for word in result:for i in result[word]:print("Word", word, "appears from", i, "to", i + len(word) - 1)
参考
Aho Corasick Algorithm (opengenus.org)
相关文章:
Aho Corasick Algorithm
文章目录 前言介绍实现参考 前言 Aho Corasick Algorithm又叫AC自动机,该算法是一个匹配算法,用来匹配文本Text中多个patterns分别出现的次数; 我们定义n为patterns的总长度;m为Text的长度; 问题:在ahis…...
用户管理 --汇总
一、第一节课 1.1 本人写的 前端: 鱼皮 --> 用户中心 第1节课-CSDN博客 中期: 一、用户管理 第1节课中间-CSDN博客 后端: 一、用户管理-CSDN博客 其他的链接 亿图脑图MindMaster 1.2 优秀球友,推荐 Docs 另…...
Flutter视频播放器在iOS端和Android端都能实现全屏播放
Flutter开发过程中,对于视频播放的三方组件有很多,在Android端适配都挺好,但是在适配iPhone手机的时候,如果设置了UIInterfaceOrientationLandscapeLeft和UIInterfaceOrientationLandscapeRight都为false的情况下,无法…...
面试遇到的一些问题(二)
1、v-if v-show 区别,他们的生命周期区别 v-show: (类似于display:none/black 的切换)不管初始值是true 或false 都会进行渲染,状态改变也不会销毁和重新生成。不会影响生命周期 v-if : 是根据条件,dom进行删除插入操作。 依附于普通元素时:会触发父组件的beforeUpdate和u…...
JDK8新特性:Lambda表达式规则及用法,方法引用
目录 Lambda表达式是JDK8新增的一种语法格式 1.作用 2.用法规则: 3.方法引用 Lambda表达式是JDK8新增的一种语法格式 1.作用 简化匿名内部类的代码写法 Lambad用法前提:只能简化函数式接口(一般加有Funcationallnterface)&a…...
【GIS】JDK版本升级到17后,GeoServer的图层无法通过openLayer预览
JDK版本升级到17后,图层无法通过openLayer预览 1. 错误图示 终端输出的错误 网页端无法显示图层,并且输出错误提示 2.原因猜测 估计可能是由于java17的模块化,Java被分成了多个独立部署和运行的模块,这使得Java应用能够更快…...
vue 批量下载文件,不走后端接口的方法
今天ld提了一个需求,说页面的列表里面有要下载的地址,然后点击批量下载。我思索片刻,给出了代码 1.这个是列表页面的代码 <!-- 这个是列表页面的代码 --> <el-table :data"userListShow" align"center"border highlight-…...
科技云报道:AI+PaaS,中国云计算市场迎来新“变量”?
科技云报道原创。 没有小的市场,只有还没有被发现的大生意。 随着企业数字化转型的逐级深入,市场需求进一步向PaaS和SaaS层进发,使之成为公有云服务市场增长的主要动力。 根据IDC最新发布的报告显示,2022-2027五年间中国公有云…...
Windows Service Name重复问题
Windows Service Name重复问题 1,问题 2,打开命令提示符,管理员身份运行 3,输入命令:sc delete MYSQL57 4,验证一下,可以看见已经没有感叹号啦 ,可以看见已经没有感叹号啦...
BBS项目
一.BBS项目介绍 1.项目开发流程 项目立项 ------> 公司高层决定需求调研和分析 ------> 市场人员,技术人员参与 -需求文档说明开发部门开会 ------> 确定项目架构,技术选型,数据库设计UI,UD团队(产品经…...
Java基础——对象类型转换(向上、向下转型)
非继承关系的类之间对象类型不可以互相类型转换,只有继承关系才可以互相转换。 简单说,对象类型转换的前提要是继承关系。 对象类型转换分为:向上转型和向下转型。多态就是一种自动向上转型。 向上转型:子类对象用父类类型接收…...
期末速成数据库极简版【查询】(2)
目录 select数据查询----表 【1】筛选列 【2】where简单查询 【3】top-n/distinct/排序的查询 【4】常用内置函数 常用日期函数 常用的字符串函数 【5】模糊查询 【6】表数据操作——增/删/改 插入 更新 删除 【7】数据汇总 聚合 分类 🙂&#…...
2023年终总结-轻舟已过万重山
自我介绍 高考大省的读书人 白,陇西布衣,流落楚、汉。-与韩荆州书 我来自孔孟故里山东济宁,也许是小学时的某一天,我第一次接触到了电脑,从此对它产生了强烈的兴趣,高中我有一个愿望:成为一名计…...
手机号,邮箱,密码,验证码正则表达式[Java]
Util类: public abstract class RegexPatterns {/*** 手机号正则*/public static final String PHONE_REGEX "^1([38][0-9]|4[579]|5[0-3,5-9]|6[6]|7[0135678]|9[89])\\d{8}$";/*** 邮箱正则*/public static final String EMAIL_REGEX "^[a-zA-Z…...
普冉(PUYA)单片机开发笔记(7): ADC-轮询式多路采样
概述 应用中经常会有使用单片机进行模数转换的需求。PY32F003 具有 1 个 12 位的模拟数字转换器(ADC),今天我们一起来使用一下这个 ADC。 数据手册中对 ADC 简介如下。 SAR ADC:逐次逼近式 ADC,原理参见“参考链接&a…...
uniapp切换页面时报错问题
我们来看如下错误: 该错误的意思是不能切换到 tabbar 页面。tabbar页面通常是公共页面或者底部导航栏,如果我们用 navigateTo 或者 redirectTo 都不能实现页面切换。 我们有两种方式: 第一种是用 switchTab 来进行切换,但注意切…...
Nginx 简单入门操作
前言:之前的文章有些过就不罗嗦了。 Nginx 基础内容 是什么? Nginx 是一个轻量级的 HTTP 服务器,采用事件驱动、异步非阻塞处理方式的服务器,它具有极好的 IO 性能,常用于 HTTP服务器(包含动静分离)、正向代理、反向代理、负载均衡 等等. Nginx 和 Node.js 在很多方…...
ChatGPT是科学还是艺术?
OpenAI最近谈到GPT4变懒的问题,说“它更像是多人共同参与的艺术创作”,那到底大模型是科学还是艺术?...
线程及实现方式
一、线程 线程是一个基本的CPU执行单元,也是程序执行流的最小单位。引入线程之后,不仅是进程之间可以并发,进程内的各线程之间也可以并发,从而进一步提升了系统的并发度,使得一个进程内也可以并发处理各种任务&#x…...
2023年11月10日 Go生态洞察:十四年Go的成长之路
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...
