当前位置: 首页 > 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; 文章图文…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...