探索AC自动机：多关键词搜索的原理与应用案例-电子发烧友网

引言

目前，大多数自由文本搜索威廉希尔官方网站采用类似于Lucene的策略，通过解析搜索文本为各个组成部分来定位关键词。这种方法在处理少量关键词时表现良好。但当搜索的关键词数量达到10万个或更多时，这种方法的效率会显著下降，尤其是在需要与词典进行详尽对比的场景中。本文将介绍的Aho-Corasick（AC）自动机作为多模式匹配中的经典算法，不仅能够处理大规模文本数据，还能确保搜索过程的实时性和准确性。

AC自动机：文本搜索的革命性工具

AC自动机可以被形象地比喻为一个超级找词机器。想象你手头有一本内容繁多的书籍和一份包含多个词语的列表，你的任务是快速找出所有这些词语在书中出现的位置。如果采用传统方法，即逐个词进行查找，工作量将会非常巨大。而AC自动机通过构建一种特殊的树状结构——前缀树或Trie，来极大地提升搜索效率。

AC自动机构建与搜索机制

构建前缀树（Trie）

AC自动机首先会根据所有关键词构建一个前缀树。这种树状结构的每个节点代表一个字母，并且每个字母都指向下一个可能的字母，从而形成一个连续的路径，表示一个或多个关键词的前缀

图片来源网络

失配指针（Fail指针）

在搜索过程中，如果当前路径上无法找到匹配的关键词，AC自动机会利用失配指针进行快速回溯。这些指针预先设置在树的每个节点上，指向其他可能的匹配路径，从而避免了从头开始搜索的低效性

图片来源网络

实时搜索与高效报告

AC自动机在读取文本的同时，能够快速地遍历前缀树结构。一旦发现关键词出现在文本中，它能够立即报告这个词及其出现的位置。这种能力使得AC自动机能够一次性高效完成大量关键词的搜索任务

图片来源网络

算法核心组件与复杂度

核心组件：

•goto（转跳）：每个遇到的字符都会被提交给goto结构中的状态对象，以确定新的当前状态

•fail（失败转移）：如果没有找到匹配状态，算法会触发fail并回溯至深度更浅的状态，从那里继续搜索

•output（输出）：每当达到与整个关键词相匹配的状态时，该状态会被发送到输出集合中，完成扫描后即可读取这些匹配项

时间复杂度：

Aho-Corasick算法的时间复杂度为O(n)，其中n是文本的长度。这意味着无论提供多少关键词，搜索的性能都将呈线性下降，与关键词的数量无关。

AC自动机的应用

AC自动机在多种场景下都能发挥重要作用，包括：

•在文本中查找并链接或突出显示关键词，提高信息的可检索性

•为纯文本添加语义，使文本内容更加丰富和有层次

•检查文本中的语法错误，通过与词典的对比来识别和纠正错误

应用案例：使用Aho-Corasick算法来识别和高亮HTML文本中的关键词

本Java程序将演示如何使用Aho-Corasick自动机库来搜索和高亮HTML文本中的关键词。程序首先构建一个自动状态机，该状态机被训练识别一系列中文关键词。然后，程序将处理HTML文档，查找这些关键词的出现，并用标签将它们包裹起来，以实现加粗显示的效果。

第一步：Maven依赖配置，引入Aho-Corasick自动机库

< dependency >
    < groupId >org.ahocorasick< /groupId >
    < artifactId >ahocorasick< /artifactId >
    < version >0.6.3< /version >
< /dependency >

第二步：代码实现

public class HighlightKeywordsInHtml {

   public static void main(String[] args) {
        // 定义HTML内容的字符串，包含了南京大学的介绍
        String htmlContent = createHtmlContentForNanjingUniversity();
        // 创建Aho-Corasick Trie的构建器实例
        Trie trie = buildAhoCorasickTrie();
        // 使用Trie实例处理HTML文本，获取匹配的Token集合
        Collection< Token > tokens = trie.tokenize(htmlContent);
        // 使用StringBuilder构建最终的HTML字符串，用于输出高亮的关键词
        StringBuilder html = new StringBuilder();
        html.append("< html >

< p >"); // 遍历Token集合 for (Token token : tokens) { // 如果Token匹配关键词，则添加标签以实现加粗效果 if (token.isMatch()) { html.append(""); } // 添加Token对应的文本片段 html.append(token.getFragment()); // 如果Token匹配关键词，结束标签 if (token.isMatch()) { html.append(""); } } // 完成HTML字符串的构建 html.append("< /p >< /body >< /html >"); // 打印最终的HTML字符串，其中包含高亮显示的关键词 System.out.println(html); } private static String createHtmlContentForNanjingUniversity() { // 此处添加创建南京大学HTML内容的方法实现 String speech = """ < !DOCTYPE html > < html lang="zh-CN" > < head > < meta charset="UTF-8" > < meta name="viewport" content="width=device-width, initial-scale=1.0" > < title >南京大学简介< /title > < style > body { font-family: "微软雅黑", "宋体", Arial, sans-serif; line-height: 1.6; color: #333; } .university-intro { text-align: justify; margin-bottom: 2em; padding: 1rem; background-color: #f5f5f5; border-radius: 5px; } < /style > < /head > < section class="university-intro" > < h1 >南京大学：百年名校，学术卓越< /h1 > < p >南京大学，简称“南大”，位于中国江苏省南京市，是中国最顶尖的高等学府之一，拥有百年的办学历史和深厚的文化底蕴。作为中国教育部直属的全国重点大学，南大以其卓越的学术成就和教育质量闻名于世。< /p > < p >南京大学以其强大的师资力量和学术研究而著称，提供多元化的学科教育，包括自然科学、人文社会科学、工程威廉希尔官方网站等多个领域。学校注重培养学生的创新能力和国际视野，为国家和社会培养了大量杰出人才。< /p > < p >南大校园环境优美，历史与现代交融，是学术研究和知识探索的理想场所。学校在计算机科学、地球科学、化学等学科领域具有国际领先水平，并在推动科学威廉希尔官方网站进步和文化传承方面发挥着重要作用。< /p > < /section > < /body > < /html > """; return speech; } private static Trie buildAhoCorasickTrie() { return Trie.builder() .ignoreOverlaps() // 设置不捕获重叠的关键词 .onlyWholeWords() // 仅匹配完整的单词 .ignoreCase() // 忽略关键词的大小写 .addKeywords(Arrays.asList("南京大学", "南大", "地球科学")) .build(); // 构建Trie实例 } }

第三步：运行程序，符合预期

< html >

< p >< !DOCTYPE html > < html lang="zh-CN" > < head > < meta charset="UTF-8" > < meta name="viewport" content="width=device-width, initial-scale=1.0" > < title >南京大学简介< /title > < style > body { font-family: "微软雅黑", "宋体", Arial, sans-serif; line-height: 1.6; color: #333; } .university-intro { text-align: justify; margin-bottom: 2em; padding: 1rem; background-color: #f5f5f5; border-radius: 5px; } < /style > < /head > < section class="university-intro" > < h1 >南京大学：百年名校，学术卓越< /h1 > < p >南京大学，简称“南大”，位于中国江苏省南京市，是中国最顶尖的高等学府之一，拥有百年的办学历史和深厚的文化底蕴。作为中国教育部直属的全国重点大学，南大以其卓越的学术成就和教育质量闻名于世。< /p > < p >南京大学以其强大的师资力量和学术研究而著称，提供多元化的学科教育，包括自然科学、人文社会科学、工程威廉希尔官方网站等多个领域。学校注重培养学生的创新能力和国际视野，为国家和社会培养了大量杰出人才。< /p > < p >南大校园环境优美，历史与现代交融，是学术研究和知识探索的理想场所。学校在计算机科学、地球科学、化学等学科领域具有国际领先水平，并在推动科学威廉希尔官方网站进步和文化传承方面发挥着重要作用。< /p > < /section > < /body > < /html > < /p >< /body >< /html >

本文对Aho-Corasick（AC）自动机算法进行了抛砖引玉，揭示了其在处理大规模文本数据方面的卓越性能和应用潜力。若你渴望深入挖掘AC算法的精髓，进一步探索其高级应用和实现细节，建议参考以下的参考资料进行进一步的学习与挖掘。

参考资料

1. http://cr.yp.to/bib/1975/aho.pdf

2. https://github.com/robert-bor/aho-corasick

审核编辑黄宇

声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表电子发烧友网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。举报投诉

算法

算法

+关注

关注
23

文章
4608

浏览量
92845
自动机

自动机

+关注

关注
1

文章
28

浏览量
9261

[讨论]提高网站关键词排名的28个SEO小技巧

提高网站关键词排名的28个SEO小技巧关键词位置、密度、处理 URL中出现关键词（英文）网页标题中出现关键词（1-3个） 关键词标签中出现

发表于 12-01 17:08

亚马逊代运营 amazon Search term 关键词填写的“神技”

恰好包含这些单词，那么就可以自动匹配出这个关键词，这样你产品的搜索排名就不会差到哪里去，但如果缺少其中一个单词，那么搜索排名就有很大变化了。结论就是：不要只是将短语式的

发表于 06-05 15:41

HanLP关键词提取算法分析详解

l 参考论文：《TextRank: Bringing Order into Texts》l TextRank算法提取关键词的Java实现l TextRank算法自动摘要的Java实现这篇文章中作者

发表于 11-05 10:41

关键词优化有哪些实用的方法

我们在做关键词优化排名的时候，有经验的seo人员都会有自己的一套关于关键词应该怎么去优化排名的方法，但是对于一些刚接触seo的新手来说就会比较迷茫，不知道应该怎么去做好关键词的排名，大部分新手都主要

发表于 08-11 01:19

#2023，你的 FPGA 年度关键词是什么? #

FPGA 年度关键词，我的想法是“标准化”；今年的工作中遇到了不少同事的issues，本身都是小问题或者很细节的东西但是却反复出现问题，目前想到的最好的办法是做好设计规则的标准化才能避免，不知道大家有没有更好的建议？

发表于 12-06 20:31

2010年10大流行搜索关键词 Facebook居首

2010年10大流行搜索关键词 Facebook居首据国外媒体报道，调研公司Hitwise数据显示，2009年Facebook超越Myspace成为最流行的搜索关

发表于 02-25 10:39 •922次阅读

[自动机与自动线].李绍炎.扫描版

本书结合目前国内自动机械行业的现状，从应用的角度系统介绍了自动机械的模块化结构及工作原理、设计选型方法、装配调试及维护要领等。主要内容包括：自动机械的结构组成、输

发表于 09-17 16:02 •0次下载

自动机械设计

《自动机械设计》以自动机械的四大结构组成部分为主要内容展开，深入阐述了自动机械设计中普遍性的理论问题。在例举实例中侧重现代农业自动机械，力求做到理论联系实际，突出专业特色和现代科学威廉希尔官方网站

发表于 08-02 08:54 •0次下载

基于盲GDH签名的无记忆模糊关键词搜索

在云计算中，用户在计算过程中的数据安全问题已经成为制约云计算发展的一个瓶颈。本文针对云计算中的加密搜索问题，提出一个有效的加密搜索方案。在搜索过程中，为保证用户的数据安全，用户需要隐藏搜索

发表于 12-14 14:14 •0次下载

基于自动关键词抽取方法

自动关键词抽取是从文本或文本集合中自动抽取主题性或重要性的词或短语，是文本检索、文本摘要等许多文本挖掘任务的基础性和必要性的工作．探讨了关键词

发表于 12-26 16:47 •2次下载

对加密电子医疗记录的关键词的搜索

被称为MCKS I的简单的多域连接关键词搜索（MCKS）方案，该方案仅支持连接相等查询，为了实现更加灵活而复杂的多域关键词连接查询，例如子集查询和范围查询，又提出了被称为MCKS II的提高方案．该方案利用了分层属性的矢量表示

发表于 01-14 10:42 •0次下载

基于统计的AC自动机空间优化

针对高级Aho-Corasick （AC）自动机为提高串匹配速度而造成的空间浪费问题，研究发现数据流对自动机节点的访问规律，据此提出基于数据访问特征的混合自动机构建算法HybridFA

发表于 03-13 16:47 •0次下载

一种改变标准的谷歌关键词搜索的新方式

昨天，谷歌发布“Talk to Books”（撩书？？）和一个名为Semantris的游戏。这两项都是基于自然语言文本理解，用户能够凭语义而非关键词来实现搜索功能。

发表于 04-17 11:28 •6807次阅读

自动机终结字查找算法实现优化综述

自动机的秩与工业自动化中的部件定向器设计问题和理论计算机科学中的 Cerny-pin猜想密切相关。计算自动机的秩可以归结于查找自动机的终结字。 Rystsoⅴ于1992年提出了一个时间

发表于 04-28 15:49 •3次下载

ADI年度关键词曝光，这些你肯定搜索过！

大数据时代，每个人的搜索框在某种程度上都代表着这个人的所思所想。如果将时间放长，样本量放大，那么一份年度搜索关键词就会呈现出了这个世界上绝大部分人是如何走过这一年的搜索产品型号与

发表于 12-30 00:05 •852次阅读