当前位置: 首页 > news >正文

Aho Corasick Algorithm

文章目录

    • 前言
    • 介绍
    • 实现
    • 参考

前言

Aho Corasick Algorithm又叫AC自动机,该算法是一个匹配算法,用来匹配文本Text中多个patterns分别出现的次数;

我们定义npatterns的总长度;mText的长度;

问题:在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 linksfailure links,在匹配不成功的时候,若有最长的后缀节点,指向最长的后最节点,若没有则指向root进行重新查找;

假设在一颗Trie上有字符串w,x,...,其中xw的最长的后缀,所以有红线连接wa,若存在waxa,这xa也是wa的最长后缀,也用红线连接;

xa不存在,就去找除了x以外的和w的最大公共后缀,如果发现y符合条件,可以对y进行匹配;如果y不符合条件,就接着找除了x,y以外的和w的最大公共后缀,依次进行;

其次需要优化的一点输出环节,如果pattern1pattern2的后缀的情况下,我们可能会忽略掉pattern1,所以在寻找最大后缀时需要进行判断,如果最大后缀结点是pattern,就用output link连接原结点指向该结点,在以该结点为原结点去连接,直到root;如果不是就判断该结点的最大后缀结点是否是pattern,再用原结点去连接这一个结点;

在文本sting中,遍历到i的时候,可以发现sti的最大后缀ti并不是pattern,于是就找ti的最大后缀i,是pattern,于是用蓝色的线把stii结合起来;这里加粗了这一过程;

在遍历到n的时候,发现tinin都是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自动机&#xff0c;该算法是一个匹配算法&#xff0c;用来匹配文本Text中多个patterns分别出现的次数&#xff1b; 我们定义n为patterns的总长度&#xff1b;m为Text的长度&#xff1b; 问题&#xff1a;在ahis…...

用户管理 --汇总

一、第一节课 1.1 本人写的 前端&#xff1a; 鱼皮 --&#xff1e; 用户中心 第1节课-CSDN博客 中期&#xff1a; 一、用户管理 第1节课中间-CSDN博客 后端&#xff1a; 一、用户管理-CSDN博客 其他的链接 亿图脑图MindMaster 1.2 优秀球友&#xff0c;推荐 Docs 另…...

Flutter视频播放器在iOS端和Android端都能实现全屏播放

Flutter开发过程中&#xff0c;对于视频播放的三方组件有很多&#xff0c;在Android端适配都挺好&#xff0c;但是在适配iPhone手机的时候&#xff0c;如果设置了UIInterfaceOrientationLandscapeLeft和UIInterfaceOrientationLandscapeRight都为false的情况下&#xff0c;无法…...

面试遇到的一些问题(二)

1、v-if v-show 区别,他们的生命周期区别 v-show: (类似于display:none/black 的切换)不管初始值是true 或false 都会进行渲染,状态改变也不会销毁和重新生成。不会影响生命周期 v-if : 是根据条件,dom进行删除插入操作。 依附于普通元素时:会触发父组件的beforeUpdate和u…...

JDK8新特性:Lambda表达式规则及用法,方法引用

目录 Lambda表达式是JDK8新增的一种语法格式 1.作用 2.用法规则&#xff1a; 3.方法引用 Lambda表达式是JDK8新增的一种语法格式 1.作用 简化匿名内部类的代码写法 Lambad用法前提&#xff1a;只能简化函数式接口&#xff08;一般加有Funcationallnterface&#xff09;&a…...

【GIS】JDK版本升级到17后,GeoServer的图层无法通过openLayer预览

JDK版本升级到17后&#xff0c;图层无法通过openLayer预览 1. 错误图示 终端输出的错误 网页端无法显示图层&#xff0c;并且输出错误提示 2.原因猜测 估计可能是由于java17的模块化&#xff0c;Java被分成了多个独立部署和运行的模块&#xff0c;这使得Java应用能够更快…...

vue 批量下载文件,不走后端接口的方法

今天ld提了一个需求&#xff0c;说页面的列表里面有要下载的地址,然后点击批量下载。我思索片刻&#xff0c;给出了代码 1.这个是列表页面的代码 <!-- 这个是列表页面的代码 --> <el-table :data"userListShow" align"center"border highlight-…...

科技云报道:AI+PaaS,中国云计算市场迎来新“变量”?

科技云报道原创。 没有小的市场&#xff0c;只有还没有被发现的大生意。 随着企业数字化转型的逐级深入&#xff0c;市场需求进一步向PaaS和SaaS层进发&#xff0c;使之成为公有云服务市场增长的主要动力。 根据IDC最新发布的报告显示&#xff0c;2022-2027五年间中国公有云…...

Windows Service Name重复问题

Windows Service Name重复问题 1&#xff0c;问题 2&#xff0c;打开命令提示符&#xff0c;管理员身份运行 3&#xff0c;输入命令&#xff1a;sc delete MYSQL57 4&#xff0c;验证一下&#xff0c;可以看见已经没有感叹号啦 &#xff0c;可以看见已经没有感叹号啦...

BBS项目

一.BBS项目介绍 1.项目开发流程 项目立项 ------> 公司高层决定需求调研和分析 ------> 市场人员&#xff0c;技术人员参与 -需求文档说明开发部门开会 ------> 确定项目架构&#xff0c;技术选型&#xff0c;数据库设计UI&#xff0c;UD团队&#xff08;产品经…...

Java基础——对象类型转换(向上、向下转型)

非继承关系的类之间对象类型不可以互相类型转换&#xff0c;只有继承关系才可以互相转换。 简单说&#xff0c;对象类型转换的前提要是继承关系。 对象类型转换分为&#xff1a;向上转型和向下转型。多态就是一种自动向上转型。 向上转型&#xff1a;子类对象用父类类型接收…...

期末速成数据库极简版【查询】(2)

目录 select数据查询----表 【1】筛选列 【2】where简单查询 【3】top-n/distinct/排序的查询 【4】常用内置函数 常用日期函数 常用的字符串函数 【5】模糊查询 【6】表数据操作——增/删/改 插入 更新 删除 【7】数据汇总 聚合 分类 ​ &#x1f642;&#…...

2023年终总结-轻舟已过万重山

自我介绍 高考大省的读书人 白&#xff0c;陇西布衣&#xff0c;流落楚、汉。-与韩荆州书 我来自孔孟故里山东济宁&#xff0c;也许是小学时的某一天&#xff0c;我第一次接触到了电脑&#xff0c;从此对它产生了强烈的兴趣&#xff0c;高中我有一个愿望&#xff1a;成为一名计…...

手机号,邮箱,密码,验证码正则表达式[Java]

Util类&#xff1a; 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 位的模拟数字转换器&#xff08;ADC&#xff09;&#xff0c;今天我们一起来使用一下这个 ADC。 数据手册中对 ADC 简介如下。 SAR ADC&#xff1a;逐次逼近式 ADC&#xff0c;原理参见“参考链接&a…...

uniapp切换页面时报错问题

我们来看如下错误&#xff1a; 该错误的意思是不能切换到 tabbar 页面。tabbar页面通常是公共页面或者底部导航栏&#xff0c;如果我们用 navigateTo 或者 redirectTo 都不能实现页面切换。 我们有两种方式&#xff1a; 第一种是用 switchTab 来进行切换&#xff0c;但注意切…...

Nginx 简单入门操作

前言:之前的文章有些过就不罗嗦了。 Nginx 基础内容 是什么? Nginx 是一个轻量级的 HTTP 服务器,采用事件驱动、异步非阻塞处理方式的服务器,它具有极好的 IO 性能,常用于 HTTP服务器(包含动静分离)、正向代理、反向代理、负载均衡 等等. Nginx 和 Node.js 在很多方…...

ChatGPT是科学还是艺术?

OpenAI最近谈到GPT4变懒的问题&#xff0c;说“它更像是多人共同参与的艺术创作”&#xff0c;那到底大模型是科学还是艺术&#xff1f;...

线程及实现方式

一、线程 线程是一个基本的CPU执行单元&#xff0c;也是程序执行流的最小单位。引入线程之后&#xff0c;不仅是进程之间可以并发&#xff0c;进程内的各线程之间也可以并发&#xff0c;从而进一步提升了系统的并发度&#xff0c;使得一个进程内也可以并发处理各种任务&#x…...

2023年11月10日 Go生态洞察:十四年Go的成长之路

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...