一、Aho-Corasic算法Python使用官方教程pyahocorasick — ahocorasick documentation二、Aho-Corasic算法的定义及功能2.1 Aho-Corasick算法的定义Aho-Corasick简称为AC自动机是一种基于前缀的使用了确定有限自动机(DFA)原理的字符串多模匹配算法。什么是DFA?DFA也就是确定有限自动机英文全称是Deterministic Finite Automaton。具体的细节介绍可以参照百度百科、维基百科以及《算法导论》之类的算法书。在这里我们尝试用通俗的语言和图示来解释一遍。我们一个一个字母的来解释DFA的含义首先什么是自动机(A)。自动机就是一个代码块。这段代码块只做一件事那就是接收输入值和状态值输出同为状态值的结果。图表述如下其次下一个字母——有限(F)是指自动机接收、输入的状态种类是有限的。而相对应的非有限自动机的状态就是有无限种的。再者下一个字母——确定的(D)是指自动机的输出状态是单一的一个状态。如果不太好理解的话那就是看一下对应的非确定自动机。这种自动机的输出状态就不是单一的而是许多个状态的集合。用图示来表述就是下面这样:先有限后无限所以三个字母合起来以后DFA的意思就像英文全称一样了是一种状态值种类有限且返回结果单一的自动机。简单的代码例子def automata (value, state): if state 0: if value a: return 0 elif value b: return 1 elif state 1: if value a: return 0 elif value b: return 1上面的这段代码其内部的状态转化逻辑可以用图示也就是所谓的状态转化图表示:而更加复杂的自动机状态转化图可以参照下面这张截取自百度百科的图示:2.2 Aho-Corasick算法的功能Aho-Corasick的核心功能是实现字符串多模匹配。比如现在有个大的列表客户输入一句话如何根据客户输入的一句话从大列表中匹配出字符串交集。三、Aho-Corasic算法的基本原理3.1Tire Tree的由来上一节对DFA进行了介绍那么现在实际操作一把构建一个DFA状态转化图使得输入下面三条字符串以后都能得到终点态: aababbaba、aaabbaba、aabababa状态转化图过程分析状态0为初始态状态9为终点态。虽然可能不是十分完善但我们输入上面那三条字符串的任意一条都能成功的得到终点态9。那么既然能用纸笔画出来我们就能用代码实现出来。大致构想一下代码的数据结构和逻辑应该是下面这样:首先数据结构应该是使用链表来表示每个节点其次代码逻辑大致有下面这几步:2.1 接收输入的字符判断是否和当前状态所在节点的字符内容相同2.2 如果不同或者当前状态节点为初始态节点则为本次输入字符新建节点。然后将当前状态所在节点的next指针指向新建的节点2.3 如果相同则略过本次输入跳转至步骤2.1接收下一个字符我们按照这样的逻辑实现了以后输入上面那三条字符串会发现得到的结果跟我们用纸笔画出的状态转化图不一样而是像下面这样:跟我们用纸笔画出来的图示区别在于变成了树状的分叉结构。而这种我们无意之间得到的树状分叉结构只要把状态节点换成对应的输入字符内容就是Tire Tree了也叫做单词查找树。可以看出每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀即单词本身。单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支root-i-in。同理ate, age, adv, 和ant共享前缀a所以他们共享从根节点到节点a的边。查询操纵非常简单。比如要查找int顺着路径i - in - int就找到了。3.2 Aho-Corasick算法原理按照上一节中生成Tire Tree类似结构DFA的代码设计我们输入下面这三条字符串: his、hers、she。可以得到下面这样的状态转化图:观察这个状态转化图我们发现可以拿来做字符串匹配。比如我们输入这样一段内容: hisdef当输入了s以后我们就得到了终点态所以我们可以判定当前字符串内包含有his。可是如果我们输入的是abchisdef呢想要得到终点态就得略过前面的abc。那如果我们输入的是shis呢匹配she的时候匹配一半就得切换到对his的匹配。因此我们发现需要对这种状态树做一点改进。相较于Tire Tree而言Aho-Corasick算法引入Fail路径(失败路径)进行算法优化。还是用上面的his、hers、she做例子添加了红色虚线Fail路径的状态转化图像下面这样:这些红色的Fail路径就是如果我们输入的字符内容无法使状态值从当前状态节点跳转到下一个预定的状态节点时我们就通过Fail路径回溯到前面的某一个状态节点。例如正常情况下的跳转动作是这样的: f(1, i) 2。而当我们的输入值不是1和i的时候就无法得到2了。此时得到的则是0即f(1, x) 0。四、如何构建Fail路径Fail路径就是指向另一个可以作为某一范式前缀的节点。Fail路径的构建逻辑可以分解成下面这几步如果自己是根节点则其Fail路径指向自己如果自己的父节点是根节点则其Fail路径仍指向根节点找到自己父节点Fail路径指向的节点执行如下操作1如果自己父节点Fail路径指向的节点可以正常接收自己的输入字符那么就指向这个节点接收自己输入字符后所指向的那个节点2如果自己父节点Fail路径指向的节点不能正常接收自己的输入字符就按照第3步的判断检查自己父节点的父节点的Fail路径指向的节点依次递推一直父节点、父节点、父节点......这样的回溯如果直到回溯至根节点还没找到的话那么其Fail路径就指向根节点4.1构建Fail路径的典型范例例如通过字符串nihao、hao、hs、hsr得到的状态转化图是下面这样:接下来我们按照上面说的步骤来一步一步分析nihao、hao、hs、hsr例子得到的状态转化图。首先是0节点因为是根节点所以就指向了它自己也就是0 - 0然后是1节点1节点的父节点是0节点也就是根节点所以指向0节点也就是1 - 0由于2节点的父节点是1节点1节点的Fail路径指向了0节点。那么因为0节点不能正常接收2节点的输入字符也就是i所以我们继续回溯去看2节点的父节点的父节点也就是0节点。这时因为已经回溯到了根节点所以按照逻辑我们只能最终确定指向0也就是2 - 0由于3节点的父节点是2节点2节点的Fail路径指向了0节点。那么因为0节点可以正常接收3节点的输入字符也就是h所以3节点就应该指向0节点接收了h后指向的节点也就是6。所以最终我们得到3 - 6依照上述原理添上Fail路径后的状态转化图如下:3.5 如何进行状态跳转正常路径的跳转很简单我们主要关注Fail路径跳转。和其文本含义一样即当正常路径失败时就通过Fail路径跳转。Aho-Corasick算法——状态节点间的跳转逻辑如果当前这个节点可以正常接收输入值那么就跳转到输入值对应的下一个节点本轮跳转结束接收下一个输入值以进入下一轮跳转如果当前这个节点不能正常接收输入值那么就先跳转到自己Fail路径指向的节点然后再尝试执行第一步如果现在已经跳转回到了根节点那么先尝试第一步如果失败则就不再执行第二步而是停留在根节点了本轮跳转结束接收下一个输入值以进入下一轮跳转。典型范例还是使用his、hers、she的状态转化图来举个例子当我们输入字符串ushhis时详细的跳转步骤如下:当前状态0输入u无法正常跳转进入Fail路径到达状态0当前状态0输入s可以正常跳转到达状态7当前状态7输入h可以正常跳转到达状态8当前状态8输入h无法正常跳转进入Fail路径到达状态1当前状态1输入i可以正常跳转到达状态2当前状态2输入s可以正常跳转到达状态3当我们执行到上面的第八步时我们发现状态3是一个终点态。所以我们可以判定此时我们找到了范式his。4.2如何得到匹配结果匹配结果由两部分组成:每轮跳转结束后所停留在的节点如果是终点态则该节点对应的模式串匹配成功从停留的节点开始一路沿Fail路径递归至根节点期间路过的所有的节点只要是终点态节点则该节点对应的模式串也就匹配成功。典型范例用nihao、hao、hs、hsr的状态转化图举例。如果经过跳转后停留在节点5那么因为节点5是终点态所以节点5对应的模式串nihao就匹配成功了。然后我们沿着Fail路径递归至节点8因为节点8也是终点态所以节点8对应的模式串hao也匹配成功了。再继续沿着Fail路径递归这时候我们到了根节点那么至此这一轮匹配结束。4.3 Aho-Corasic算法中构建Fail路径的意义为了解释这个问题让我们回到本文最开始的位置。在第一节中我们用一句话解释了什么是Aho-Corasick算法而那句话中的“基于前缀的”这五个字就是答案。在构建Fail路径过程中我们反复的回溯其实就是在试图拓展上一步找到的前缀而得到此范式的更长前缀。在我们使用Fail路径跳转的时候我们发现Fail路径所指向的节点其所在的正常状态节点链上从根节点开始到该节点为止每个节点组成的字符串必定是某一个范式的前缀。由his、hers、she所组成的状态转化图里节点9的Fail节点指向了节点4。那么在节点4所在的这条状态节点链上从根节点0开始到节点4为止一共0、1、4三个节点所组成的字符串是he而he就是hers范式的前缀。五、Aho-Corasic算法的Python调用5.1 ahocorasick.Automaton()函数介绍import ahocorasick # 导入ahocorasick模块 A ahocorasick.Automaton() # 建树create an Automaton # You can use the Automaton class as a trie.即将A看做trie for idx, key in enumerate(he her hers she.split()): # str.split()去除字符串收尾的空格 A.add_word(key, (idx, key)) # 此处我们将 (idx, key)作为与key关联的value添加到刚建的树Automaton中 A.make_automaton() # 现在将trie即A转换为Aho Corasick自动机以启用Aho Corasick搜索 # 补充用法说明 # Then check if some string exists in the trie: he in A True HER in A False # And play with the get() dict-like method: A.get(he) # 使用get函数来获取匹配到的key如果匹配到输入Word则返回对应于key的(idx, key) (0, he) A.get(she) (3, she) A.get(cat, not exists) # 使用get函数来获取匹配到的key如果未匹配到输入Word则指定返回值为“not exists” not exists A.get(dog) # 使用get函数来获取匹配到的key如果未匹配到输入Word且未指定匹配失败返回值则直接报错 Traceback (most recent call last): File stdin, line 1, in module KeyErrorAutomaton.iter() 方法的返回结果为一个二元组它由2部分构成1input字符串所匹配到的key的结束索引2所匹配到的key的关联value【insertion index, original string】haystack heissgirlsheissboy for end_index, (insert_order, original_value) in A.iter(haystack): start_index end_index - len(original_value) 1 # 通过input字符串所匹配到的key的结束索引推算开始索引 print((start_index, end_index, (insert_order, original_value))) assert haystack[start_index:start_index len(original_value)] original_value # assert语句用来声明某个条件是真的。 (0, 1, (0, he)) (9, 11, (3, she)) (10, 11, (0, he))5.2 示例比如我们有一个wordlist列表长度很长包含43430个元素[长春海外制药接骨续筋片, 香菇炖甲鱼, 三鹤药业黄柏胶囊, 上海衡山熊去氧胆酸片, 升和药业依托泊苷注射液, 怡诺思, 人格障碍, 转铁蛋白饱和度, 脾囊肿, 素烧白萝卜, 利君现代冠脉宁片, 上海复华药业注射用还原型谷, 阴囊上有白色小疙瘩, 腹痛伴休克, 成都通德胰激肽原酶肠溶片, 蒸猪肝, 河北百善血尿胶囊, 精神障碍, 输卵管畸形, 元和抑眩宁胶囊, 莲藕豆腐, 辰欣哈西奈德溶液, 信谊烟酸片, 慢性胆囊炎, 参芪降糖颗粒, 康普药业盐酸普萘洛尔片, 西安迪赛胸腺肽肠溶片, 双鹭药业注射用复合辅酶, 慢性筛窦炎, 新高制药维胺酯维E乳膏, 冰黄肤乐软膏, 神经类疾病, 液晶热图, 枣干, 股外侧皮神经病, 浙江惠松硅炭银片, 牙根外露, 湖北潜江氯霉素滴眼液, 盐类皮质激素分泌过多, 五子衍宗丸, 小儿阵发性睡眠性血红蛋白尿症, 功能失调性子宫出血病, 茵栀黄口服液, 眼底出血和渗出, 斯达制药注射用头孢噻肟钠, 复方白芷酊, 胫腓骨骨折, 西南药业氯霉素片, 宫颈炎, 茶碱缓释胶囊, 原发性硬化性胆管炎, 郑州韩都利肺胶囊, 咽反射消失, 脊髓灰质炎, 甲状腺片, 回盲瓣功能不全, 乙肝e抗体抗..., 马齿苋粥, 动脉硬化, 宝宝乐, 肠闭锁, 肺放线菌病, 江苏晨牌产妇安颗粒, 犬吠样咳嗽, 胃康灵胶囊, 小儿烟酸缺乏病, 青龙防风通圣丸, 广东南国维生素C片, 碘化油咀嚼片, 西乐葆, 伟哥甲磺酸酚妥拉明分散片, 成都迪康药业樟脑醑, 斑疹, 五花炖墨鱼, 肉炖芸豆粉条, 陕西东泰制药益脉康胶囊, 桔梗八味颗粒, 华南牌溴丙胺太林片, 吉林敖东洮南小牛脾提取物注, 仁青芒觉, 血吸虫病与肝胆疾病,...,持续性枕横位难产, 弯曲菌感染, 丝瓜蘑菇肉片汤, 长春银诺克清咽片, 肝叶萎缩, 迪皿盐酸左西替利嗪口服溶液]index, (index, word)如下0 (0, 长春海外制药接骨续筋片) 1 (1, 香菇炖甲鱼) 2 (2, 三鹤药业黄柏胶囊) 3 (3, 上海衡山熊去氧胆酸片) 4 (4, 升和药业依托泊苷注射液) 5 (5, 怡诺思) 6 (6, 人格障碍) 7 (7, 转铁蛋白饱和度) 8 (8, 脾囊肿) 9 (9, 素烧白萝卜) 10 (10, 利君现代冠脉宁片) ...... 43422 (43422, 弯曲菌感染) 43423 (43423, 丝瓜蘑菇肉片汤) 43424 (43424, 长春银诺克清咽片) 43425 (43425, 肝叶萎缩) 43426 (43426, 迪皿盐酸左西替利嗪口服溶液) 43427 (43427, 华润天和麝香壮骨膏) 43428 (43428, 湖北恒安曲咪新乳膏) 43429 (43429, 子宫小)5.2.1 建树import ahocorasick actree ahocorasick.Automaton() for index, word in enumerate(wordlist): actree.add_word(word, (index, word)) actree.make_automaton() #其中wordlist就是上面的那个长度为43430的列表5.2.2 快速匹配for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): print(i)这样客户输入一个字符串我们能够快速的从之前的列表中匹配出相应的实体元素果然我们通过查看索引与上图结果一致从结果上看算法是根据客户输入相当于遍历每个列表元素来判断每个元素是否存在于客户输入中。效果似乎是这样时间复杂度比较高如果词库列表比较大时间会更长但是本质是采用了Aho-Corasic多模匹配算法以达到匹配的目的时间复杂度构建O(k*m) 匹配O(n) -- k表示模式字符串的数量m表示模式字符串的平均长度n表示待匹配字符串的长度存在一个问题从上面的客户输入看客户输入了瓜烧白菜但是匹配出了白菜和瓜烧白菜我们从客户输入看客户是想输入瓜烧白菜白菜我们并不想匹配出来。region_wds [] for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): wd i[1][1] # i形如(31, (13, 白菜))所以通过i[1][1]切片出‘白菜’ print(wd:, wd) region_wds.append(wd) # 将匹配到的Word添加到列表region_wds中 print(region_wds:,region_wds) stop_wds [] for wd1 in region_wds: for wd2 in region_wds: if wd1 in wd2 and wd1 ! wd2: print(w1:{},w2:{}.format(wd1,wd2)) stop_wds.append(wd1) print(stop_wds:, stop_wds) final_wds [i for i in region_wds if i not in stop_wds] # 当欲匹配的wordlist中包含string和它的截断字符串组成的sub_string时例如此处瓜烧白菜, 白菜剔除sub_string部分的匹配项。 print(final_wds:, final_wds) wd: 发烧 wd: 阿司匹林 wd: 牛黄清胃丸 wd: 瓜烧白菜 wd: 白菜 w1:白菜,w2:瓜烧白菜 region_wds: [发烧, 阿司匹林, 牛黄清胃丸, 瓜烧白菜, 白菜] 白菜 瓜烧白菜 stop_wds: [白菜] final_wds: [发烧, 阿司匹林, 牛黄清胃丸, 瓜烧白菜]根据 Automaton.iter() 方法的返回结果为一个二元组它由2部分构成1input字符串所匹配到的key的结束索引2所匹配到的key的关联value【insertion index, original string】 可知下面代码段中的二元组的第一个值3、11、22、31、31分别对应于input字符串所匹配到的key的结束索引索引从0开始计数。for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): print(i) (3, (24, 发烧)) (11, (45, 阿司匹林)) (22, (56, 牛黄清胃丸)) (31, (1, 瓜烧白菜)) (31, (13, 白菜))六、参考链接ahocorasick使用 - 1直在路上1 - 博客园 (cnblogs.com)python ahocorasick介绍-CSDN博客Aho-Corasic多模匹配算法的学习、理解和应用Python环境下_ahocorasick.automaton()-CSDN博客# coding:utf-8 import ahocorasick def make_AC(AC, word_set): for word in word_set: AC.add_word(word, word) return AC def test_ahocorasick(): ahocorasick:自动机的意思可实现自动批量匹配字符串的作用即可一次返回该条字符串中命中的所有关键词 key_list [苹果, 香蕉, 梨, 橙子, 柚子, 火龙果, 柿子, 猕猴挑] # 建树 AC_KEY ahocorasick.Automaton() AC_KEY make_AC(AC_KEY, set(key_list)) AC_KEY.make_automaton() test_str_list [我最喜欢吃的水果有苹果、梨和香蕉,我也喜欢吃香蕉但是我不喜欢吃梨] for content in test_str_list: name_list set() # 将AC_KEY中每一项与content内容作比对若匹配则返回 # 快速匹配 for item in AC_KEY.iter(content): name_list.add(item[1]) name_list list(name_list) if len(name_list) 0: print(content, ----命中的关键词有,\t.join(name_list)) if __name__ __main__: test_ahocorasick() 我最喜欢吃的水果有苹果、梨和香蕉 ----命中的关键词有 梨 苹果 香蕉 我也喜欢吃香蕉但是我不喜欢吃梨 ----命中的关键词有 梨 香蕉
人工智能|机器学习——Aho-Corasic多模匹配算法的学习、理解和应用（Python）
一、Aho-Corasic算法Python使用官方教程pyahocorasick — ahocorasick documentation二、Aho-Corasic算法的定义及功能2.1 Aho-Corasick算法的定义Aho-Corasick简称为AC自动机是一种基于前缀的使用了确定有限自动机(DFA)原理的字符串多模匹配算法。什么是DFA?DFA也就是确定有限自动机英文全称是Deterministic Finite Automaton。具体的细节介绍可以参照百度百科、维基百科以及《算法导论》之类的算法书。在这里我们尝试用通俗的语言和图示来解释一遍。我们一个一个字母的来解释DFA的含义首先什么是自动机(A)。自动机就是一个代码块。这段代码块只做一件事那就是接收输入值和状态值输出同为状态值的结果。图表述如下其次下一个字母——有限(F)是指自动机接收、输入的状态种类是有限的。而相对应的非有限自动机的状态就是有无限种的。再者下一个字母——确定的(D)是指自动机的输出状态是单一的一个状态。如果不太好理解的话那就是看一下对应的非确定自动机。这种自动机的输出状态就不是单一的而是许多个状态的集合。用图示来表述就是下面这样:先有限后无限所以三个字母合起来以后DFA的意思就像英文全称一样了是一种状态值种类有限且返回结果单一的自动机。简单的代码例子def automata (value, state): if state 0: if value a: return 0 elif value b: return 1 elif state 1: if value a: return 0 elif value b: return 1上面的这段代码其内部的状态转化逻辑可以用图示也就是所谓的状态转化图表示:而更加复杂的自动机状态转化图可以参照下面这张截取自百度百科的图示:2.2 Aho-Corasick算法的功能Aho-Corasick的核心功能是实现字符串多模匹配。比如现在有个大的列表客户输入一句话如何根据客户输入的一句话从大列表中匹配出字符串交集。三、Aho-Corasic算法的基本原理3.1Tire Tree的由来上一节对DFA进行了介绍那么现在实际操作一把构建一个DFA状态转化图使得输入下面三条字符串以后都能得到终点态: aababbaba、aaabbaba、aabababa状态转化图过程分析状态0为初始态状态9为终点态。虽然可能不是十分完善但我们输入上面那三条字符串的任意一条都能成功的得到终点态9。那么既然能用纸笔画出来我们就能用代码实现出来。大致构想一下代码的数据结构和逻辑应该是下面这样:首先数据结构应该是使用链表来表示每个节点其次代码逻辑大致有下面这几步:2.1 接收输入的字符判断是否和当前状态所在节点的字符内容相同2.2 如果不同或者当前状态节点为初始态节点则为本次输入字符新建节点。然后将当前状态所在节点的next指针指向新建的节点2.3 如果相同则略过本次输入跳转至步骤2.1接收下一个字符我们按照这样的逻辑实现了以后输入上面那三条字符串会发现得到的结果跟我们用纸笔画出的状态转化图不一样而是像下面这样:跟我们用纸笔画出来的图示区别在于变成了树状的分叉结构。而这种我们无意之间得到的树状分叉结构只要把状态节点换成对应的输入字符内容就是Tire Tree了也叫做单词查找树。可以看出每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀即单词本身。单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支root-i-in。同理ate, age, adv, 和ant共享前缀a所以他们共享从根节点到节点a的边。查询操纵非常简单。比如要查找int顺着路径i - in - int就找到了。3.2 Aho-Corasick算法原理按照上一节中生成Tire Tree类似结构DFA的代码设计我们输入下面这三条字符串: his、hers、she。可以得到下面这样的状态转化图:观察这个状态转化图我们发现可以拿来做字符串匹配。比如我们输入这样一段内容: hisdef当输入了s以后我们就得到了终点态所以我们可以判定当前字符串内包含有his。可是如果我们输入的是abchisdef呢想要得到终点态就得略过前面的abc。那如果我们输入的是shis呢匹配she的时候匹配一半就得切换到对his的匹配。因此我们发现需要对这种状态树做一点改进。相较于Tire Tree而言Aho-Corasick算法引入Fail路径(失败路径)进行算法优化。还是用上面的his、hers、she做例子添加了红色虚线Fail路径的状态转化图像下面这样:这些红色的Fail路径就是如果我们输入的字符内容无法使状态值从当前状态节点跳转到下一个预定的状态节点时我们就通过Fail路径回溯到前面的某一个状态节点。例如正常情况下的跳转动作是这样的: f(1, i) 2。而当我们的输入值不是1和i的时候就无法得到2了。此时得到的则是0即f(1, x) 0。四、如何构建Fail路径Fail路径就是指向另一个可以作为某一范式前缀的节点。Fail路径的构建逻辑可以分解成下面这几步如果自己是根节点则其Fail路径指向自己如果自己的父节点是根节点则其Fail路径仍指向根节点找到自己父节点Fail路径指向的节点执行如下操作1如果自己父节点Fail路径指向的节点可以正常接收自己的输入字符那么就指向这个节点接收自己输入字符后所指向的那个节点2如果自己父节点Fail路径指向的节点不能正常接收自己的输入字符就按照第3步的判断检查自己父节点的父节点的Fail路径指向的节点依次递推一直父节点、父节点、父节点......这样的回溯如果直到回溯至根节点还没找到的话那么其Fail路径就指向根节点4.1构建Fail路径的典型范例例如通过字符串nihao、hao、hs、hsr得到的状态转化图是下面这样:接下来我们按照上面说的步骤来一步一步分析nihao、hao、hs、hsr例子得到的状态转化图。首先是0节点因为是根节点所以就指向了它自己也就是0 - 0然后是1节点1节点的父节点是0节点也就是根节点所以指向0节点也就是1 - 0由于2节点的父节点是1节点1节点的Fail路径指向了0节点。那么因为0节点不能正常接收2节点的输入字符也就是i所以我们继续回溯去看2节点的父节点的父节点也就是0节点。这时因为已经回溯到了根节点所以按照逻辑我们只能最终确定指向0也就是2 - 0由于3节点的父节点是2节点2节点的Fail路径指向了0节点。那么因为0节点可以正常接收3节点的输入字符也就是h所以3节点就应该指向0节点接收了h后指向的节点也就是6。所以最终我们得到3 - 6依照上述原理添上Fail路径后的状态转化图如下:3.5 如何进行状态跳转正常路径的跳转很简单我们主要关注Fail路径跳转。和其文本含义一样即当正常路径失败时就通过Fail路径跳转。Aho-Corasick算法——状态节点间的跳转逻辑如果当前这个节点可以正常接收输入值那么就跳转到输入值对应的下一个节点本轮跳转结束接收下一个输入值以进入下一轮跳转如果当前这个节点不能正常接收输入值那么就先跳转到自己Fail路径指向的节点然后再尝试执行第一步如果现在已经跳转回到了根节点那么先尝试第一步如果失败则就不再执行第二步而是停留在根节点了本轮跳转结束接收下一个输入值以进入下一轮跳转。典型范例还是使用his、hers、she的状态转化图来举个例子当我们输入字符串ushhis时详细的跳转步骤如下:当前状态0输入u无法正常跳转进入Fail路径到达状态0当前状态0输入s可以正常跳转到达状态7当前状态7输入h可以正常跳转到达状态8当前状态8输入h无法正常跳转进入Fail路径到达状态1当前状态1输入i可以正常跳转到达状态2当前状态2输入s可以正常跳转到达状态3当我们执行到上面的第八步时我们发现状态3是一个终点态。所以我们可以判定此时我们找到了范式his。4.2如何得到匹配结果匹配结果由两部分组成:每轮跳转结束后所停留在的节点如果是终点态则该节点对应的模式串匹配成功从停留的节点开始一路沿Fail路径递归至根节点期间路过的所有的节点只要是终点态节点则该节点对应的模式串也就匹配成功。典型范例用nihao、hao、hs、hsr的状态转化图举例。如果经过跳转后停留在节点5那么因为节点5是终点态所以节点5对应的模式串nihao就匹配成功了。然后我们沿着Fail路径递归至节点8因为节点8也是终点态所以节点8对应的模式串hao也匹配成功了。再继续沿着Fail路径递归这时候我们到了根节点那么至此这一轮匹配结束。4.3 Aho-Corasic算法中构建Fail路径的意义为了解释这个问题让我们回到本文最开始的位置。在第一节中我们用一句话解释了什么是Aho-Corasick算法而那句话中的“基于前缀的”这五个字就是答案。在构建Fail路径过程中我们反复的回溯其实就是在试图拓展上一步找到的前缀而得到此范式的更长前缀。在我们使用Fail路径跳转的时候我们发现Fail路径所指向的节点其所在的正常状态节点链上从根节点开始到该节点为止每个节点组成的字符串必定是某一个范式的前缀。由his、hers、she所组成的状态转化图里节点9的Fail节点指向了节点4。那么在节点4所在的这条状态节点链上从根节点0开始到节点4为止一共0、1、4三个节点所组成的字符串是he而he就是hers范式的前缀。五、Aho-Corasic算法的Python调用5.1 ahocorasick.Automaton()函数介绍import ahocorasick # 导入ahocorasick模块 A ahocorasick.Automaton() # 建树create an Automaton # You can use the Automaton class as a trie.即将A看做trie for idx, key in enumerate(he her hers she.split()): # str.split()去除字符串收尾的空格 A.add_word(key, (idx, key)) # 此处我们将 (idx, key)作为与key关联的value添加到刚建的树Automaton中 A.make_automaton() # 现在将trie即A转换为Aho Corasick自动机以启用Aho Corasick搜索 # 补充用法说明 # Then check if some string exists in the trie: he in A True HER in A False # And play with the get() dict-like method: A.get(he) # 使用get函数来获取匹配到的key如果匹配到输入Word则返回对应于key的(idx, key) (0, he) A.get(she) (3, she) A.get(cat, not exists) # 使用get函数来获取匹配到的key如果未匹配到输入Word则指定返回值为“not exists” not exists A.get(dog) # 使用get函数来获取匹配到的key如果未匹配到输入Word且未指定匹配失败返回值则直接报错 Traceback (most recent call last): File stdin, line 1, in module KeyErrorAutomaton.iter() 方法的返回结果为一个二元组它由2部分构成1input字符串所匹配到的key的结束索引2所匹配到的key的关联value【insertion index, original string】haystack heissgirlsheissboy for end_index, (insert_order, original_value) in A.iter(haystack): start_index end_index - len(original_value) 1 # 通过input字符串所匹配到的key的结束索引推算开始索引 print((start_index, end_index, (insert_order, original_value))) assert haystack[start_index:start_index len(original_value)] original_value # assert语句用来声明某个条件是真的。 (0, 1, (0, he)) (9, 11, (3, she)) (10, 11, (0, he))5.2 示例比如我们有一个wordlist列表长度很长包含43430个元素[长春海外制药接骨续筋片, 香菇炖甲鱼, 三鹤药业黄柏胶囊, 上海衡山熊去氧胆酸片, 升和药业依托泊苷注射液, 怡诺思, 人格障碍, 转铁蛋白饱和度, 脾囊肿, 素烧白萝卜, 利君现代冠脉宁片, 上海复华药业注射用还原型谷, 阴囊上有白色小疙瘩, 腹痛伴休克, 成都通德胰激肽原酶肠溶片, 蒸猪肝, 河北百善血尿胶囊, 精神障碍, 输卵管畸形, 元和抑眩宁胶囊, 莲藕豆腐, 辰欣哈西奈德溶液, 信谊烟酸片, 慢性胆囊炎, 参芪降糖颗粒, 康普药业盐酸普萘洛尔片, 西安迪赛胸腺肽肠溶片, 双鹭药业注射用复合辅酶, 慢性筛窦炎, 新高制药维胺酯维E乳膏, 冰黄肤乐软膏, 神经类疾病, 液晶热图, 枣干, 股外侧皮神经病, 浙江惠松硅炭银片, 牙根外露, 湖北潜江氯霉素滴眼液, 盐类皮质激素分泌过多, 五子衍宗丸, 小儿阵发性睡眠性血红蛋白尿症, 功能失调性子宫出血病, 茵栀黄口服液, 眼底出血和渗出, 斯达制药注射用头孢噻肟钠, 复方白芷酊, 胫腓骨骨折, 西南药业氯霉素片, 宫颈炎, 茶碱缓释胶囊, 原发性硬化性胆管炎, 郑州韩都利肺胶囊, 咽反射消失, 脊髓灰质炎, 甲状腺片, 回盲瓣功能不全, 乙肝e抗体抗..., 马齿苋粥, 动脉硬化, 宝宝乐, 肠闭锁, 肺放线菌病, 江苏晨牌产妇安颗粒, 犬吠样咳嗽, 胃康灵胶囊, 小儿烟酸缺乏病, 青龙防风通圣丸, 广东南国维生素C片, 碘化油咀嚼片, 西乐葆, 伟哥甲磺酸酚妥拉明分散片, 成都迪康药业樟脑醑, 斑疹, 五花炖墨鱼, 肉炖芸豆粉条, 陕西东泰制药益脉康胶囊, 桔梗八味颗粒, 华南牌溴丙胺太林片, 吉林敖东洮南小牛脾提取物注, 仁青芒觉, 血吸虫病与肝胆疾病,...,持续性枕横位难产, 弯曲菌感染, 丝瓜蘑菇肉片汤, 长春银诺克清咽片, 肝叶萎缩, 迪皿盐酸左西替利嗪口服溶液]index, (index, word)如下0 (0, 长春海外制药接骨续筋片) 1 (1, 香菇炖甲鱼) 2 (2, 三鹤药业黄柏胶囊) 3 (3, 上海衡山熊去氧胆酸片) 4 (4, 升和药业依托泊苷注射液) 5 (5, 怡诺思) 6 (6, 人格障碍) 7 (7, 转铁蛋白饱和度) 8 (8, 脾囊肿) 9 (9, 素烧白萝卜) 10 (10, 利君现代冠脉宁片) ...... 43422 (43422, 弯曲菌感染) 43423 (43423, 丝瓜蘑菇肉片汤) 43424 (43424, 长春银诺克清咽片) 43425 (43425, 肝叶萎缩) 43426 (43426, 迪皿盐酸左西替利嗪口服溶液) 43427 (43427, 华润天和麝香壮骨膏) 43428 (43428, 湖北恒安曲咪新乳膏) 43429 (43429, 子宫小)5.2.1 建树import ahocorasick actree ahocorasick.Automaton() for index, word in enumerate(wordlist): actree.add_word(word, (index, word)) actree.make_automaton() #其中wordlist就是上面的那个长度为43430的列表5.2.2 快速匹配for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): print(i)这样客户输入一个字符串我们能够快速的从之前的列表中匹配出相应的实体元素果然我们通过查看索引与上图结果一致从结果上看算法是根据客户输入相当于遍历每个列表元素来判断每个元素是否存在于客户输入中。效果似乎是这样时间复杂度比较高如果词库列表比较大时间会更长但是本质是采用了Aho-Corasic多模匹配算法以达到匹配的目的时间复杂度构建O(k*m) 匹配O(n) -- k表示模式字符串的数量m表示模式字符串的平均长度n表示待匹配字符串的长度存在一个问题从上面的客户输入看客户输入了瓜烧白菜但是匹配出了白菜和瓜烧白菜我们从客户输入看客户是想输入瓜烧白菜白菜我们并不想匹配出来。region_wds [] for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): wd i[1][1] # i形如(31, (13, 白菜))所以通过i[1][1]切片出‘白菜’ print(wd:, wd) region_wds.append(wd) # 将匹配到的Word添加到列表region_wds中 print(region_wds:,region_wds) stop_wds [] for wd1 in region_wds: for wd2 in region_wds: if wd1 in wd2 and wd1 ! wd2: print(w1:{},w2:{}.format(wd1,wd2)) stop_wds.append(wd1) print(stop_wds:, stop_wds) final_wds [i for i in region_wds if i not in stop_wds] # 当欲匹配的wordlist中包含string和它的截断字符串组成的sub_string时例如此处瓜烧白菜, 白菜剔除sub_string部分的匹配项。 print(final_wds:, final_wds) wd: 发烧 wd: 阿司匹林 wd: 牛黄清胃丸 wd: 瓜烧白菜 wd: 白菜 w1:白菜,w2:瓜烧白菜 region_wds: [发烧, 阿司匹林, 牛黄清胃丸, 瓜烧白菜, 白菜] 白菜 瓜烧白菜 stop_wds: [白菜] final_wds: [发烧, 阿司匹林, 牛黄清胃丸, 瓜烧白菜]根据 Automaton.iter() 方法的返回结果为一个二元组它由2部分构成1input字符串所匹配到的key的结束索引2所匹配到的key的关联value【insertion index, original string】 可知下面代码段中的二元组的第一个值3、11、22、31、31分别对应于input字符串所匹配到的key的结束索引索引从0开始计数。for i in actree.iter(昨天发烧服用了阿司匹林,并且还吃了牛黄清胃丸饭是吃了瓜烧白菜大便有点色浅): print(i) (3, (24, 发烧)) (11, (45, 阿司匹林)) (22, (56, 牛黄清胃丸)) (31, (1, 瓜烧白菜)) (31, (13, 白菜))六、参考链接ahocorasick使用 - 1直在路上1 - 博客园 (cnblogs.com)python ahocorasick介绍-CSDN博客Aho-Corasic多模匹配算法的学习、理解和应用Python环境下_ahocorasick.automaton()-CSDN博客# coding:utf-8 import ahocorasick def make_AC(AC, word_set): for word in word_set: AC.add_word(word, word) return AC def test_ahocorasick(): ahocorasick:自动机的意思可实现自动批量匹配字符串的作用即可一次返回该条字符串中命中的所有关键词 key_list [苹果, 香蕉, 梨, 橙子, 柚子, 火龙果, 柿子, 猕猴挑] # 建树 AC_KEY ahocorasick.Automaton() AC_KEY make_AC(AC_KEY, set(key_list)) AC_KEY.make_automaton() test_str_list [我最喜欢吃的水果有苹果、梨和香蕉,我也喜欢吃香蕉但是我不喜欢吃梨] for content in test_str_list: name_list set() # 将AC_KEY中每一项与content内容作比对若匹配则返回 # 快速匹配 for item in AC_KEY.iter(content): name_list.add(item[1]) name_list list(name_list) if len(name_list) 0: print(content, ----命中的关键词有,\t.join(name_list)) if __name__ __main__: test_ahocorasick() 我最喜欢吃的水果有苹果、梨和香蕉 ----命中的关键词有 梨 苹果 香蕉 我也喜欢吃香蕉但是我不喜欢吃梨 ----命中的关键词有 梨 香蕉
