通过ahocorasick快速构建一棵actree（AC自动机）

青旅半醒 2023-07-17 04:53 4阅读 0赞

参考自文章：[https://www.cnblogs.com/always-fight/p/10895984.html][https_www.cnblogs.com_always-fight_p_10895984.html]

### 1. 作用 ###

本质上说就是字符串匹配，比如根据一句话我们可以从字典树中快速匹配出字符串交集（快速指的是只遍历一遍字典树，比KMP算法要快），通常应用在问答系统中用于提取语句的关键词。

### 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, '子宫小')

建树的过程如下：

import ahocorasick
    actree=ahocorasick.Automaton()
    for index,word in enumetate(wordlist):
        actree.add_word(word,(index,word))
    actree.make_automaton()

快速匹配：

for i in actree.iter('昨天发烧，服用了阿司匹林，并且还吃了牛黄清胃丸，饭是吃了瓜烧白菜，
                                                                        大便有点色浅')
        print(i)

这样客户输入一个字符串，我们能够快速的从之前的列表中匹配出相应的实体元素：

![format_png][]

print(wordlist[11188])
    print(wordlist[41305])
    print(wordlist[43198])
    print(wordlist[18263])

果然我们通过查看索引，与上图结果一致：

![format_png 1][]

**思考：**

存在一个问题，从上面的客户输入看，客户输入了瓜烧白菜，但是匹配出了白菜和瓜烧白菜，我们从客户输入看，客户是想输入瓜烧白菜，白菜我们并不想匹配出来

region_wds = []
    for i in actree.iter('昨天发烧，服用了阿司匹林,并且还吃了牛黄清胃丸，饭是吃了瓜烧白菜，大便有点色浅'):
        wd = i[1][1]
        region_wds.append(wd)
     
    stop_wds = []
    for wd1 in region_wds:
        for wd2 in region_wds:
            if wd1 in wd2 and wd1 != wd2:
                print(wd1, wd2)
                stop_wds.append(wd1)
                 
    final_wds = [ i for i in region_wds if i not in stop_wds ]
         
    print(region_wds)
    print(stop_wds)
    print(final_wds)

上面作者的这个思路就是在所有匹配出的字符串中，如果有短的词语存在长度词语中，那么去掉短的词语，这也算是一个trick吧。

![format_png 2][]

我们过滤掉了白菜，虽然白菜存在于列表元素中，显然它不是客户想表达的。

[https_www.cnblogs.com_always-fight_p_10895984.html]: https://www.cnblogs.com/always-fight/p/10895984.html
[format_png]: /images/20230528/e35d20c80a8c409994627c6801452ad1.png
[format_png 1]: /images/20230528/2823209b7da44f489d682a79d06f3130.png
[format_png 2]: /images/20230528/cee07c734c5042c980746d2fd1ee34d4.png