热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

双数组Trie树与AC自动机简要总结

这部分的内容比较多,面面俱到不太现实,所以这里只是简单的概要描述,对需要了解的详细细节的

这部分的内容比较多,面面俱到不太现实,所以这里只是简单的概要描述,对需要了解的详细细节的可以去看下文中推荐的链接。每个细节都去讲到又需要很多时间,但又想要总结一下。于是有了本文。

Trie 树

又称单词查找树,Trie 树,是一种树形结构,是一种哈希树的变种。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,能在常数时间 O(len)内实现插入和查询操作,是一种以空间换取时间的数据结构,广泛用于词频统计和输入统计领域。

Trie 树的结构一般如下图:

关于单数组 Trie 树的实现方式这里不再多讲,只需要知道在 Trie 树单数组实现过程中,每个节点均需要一个数组来存储 next 节点,非常占用存储空间,空间复杂度大。一般不予选用。而双数组 Trie 树很好地解决了这个问题,这也是我们主要要讲的。

双数组 Trie (Double-Array Trie)结构由日本人 JUN-ICHI AOE 于 1989 年提出的,是 Trie 结构的压缩形式,仅用两个线性数组来表示 Trie 树,该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的 Trie 空间结构紧凑的特点。双数组 Trie 的本质是一个确定有限状态自动机(DFA),每个节点代表自动机的一个状态,根据变量不同,进行状态转移,当到达结束状态或无法转移时,完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示,不仅提高了检索速度,而且省去了链式结构中使用的大量指针,节省了存储空间。虽然双数组 Trie 树能高速 O(n)完成单串匹配,并且内存消耗可控,但是软肋在于多模式匹配,如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配,这样一份文本要回退扫描多遍,性能极低。

使用两个数组 base 和 check 来维护 Trie 树,base 负责记录状态,check 负责检查各个字符串是否是从同一个状态转移而来,当 check[i]为负值时,表示此状态为字符串的结束。关于双数组 Trie 树的实现,这里也不准备讲太多,java 版开源的实现可以看下:https://github.com/komiya-atsushi/darts-java,有兴趣深入学习的可以去翻一翻这篇博客,会有不少惊喜:http://www.hankcs.com/program/java/双数组trie树doublearraytriejava实现.html

AC 自动机

AC 自动机能高速完成多模式匹配,然而具体实现聪明与否决定最终性能高低。大部分实现都是一个 Map了事,无论是 TreeMap 的对数复杂度,还是 HashMap 的巨额空间复杂度与哈希函数的性能消耗,都会降低整体性能。一般的做法是基于 Trie 树来实现 AC 自动机。

如果想看具体实现分析,可以翻翻这篇:http://www.hankcs.com/program/algorithm/implementation-and-analysis-of-aho-corasick-algorithm-in-java.html,里面有详细的讲解。

这里我们主要看一下一个开源 AC 自动机实现的介绍,开源地址为:https://github.com/robert-bor/aho-corasick

大多数自由文本搜索都基于类似于 Lucene 的方法,其中,搜索文本被解析成其各个组成部分。对于每个关键字,都会进行查找以查看其发生位置。当寻找几个关键字时,这种方法很棒,但是当搜索 100,000 个单词时,这种方法非常慢(例如,检索字典)。

查找多个单词时,Aho-Corasick 算法会发光。它使用所有关键字来构建 Trie 结构,而不是将搜索文本切碎。Aho-Corasick 的关键组件包括:

  • goto 表

  • fail 表

  • output 表

遇到的每个字符都会呈现给 goto 结构内的一个状态对象 。如果存在匹配状态,则将其提升到新的当前状态。

但是,如果没有匹配状态,该算法将发出失败信号(fail 表), 并退回到深度较小的状态(即匹配时间较短),然后从那里继续进行,直到找到匹配状态或达到根状态为止。

只要达到与整个关键字匹配的状态,就会将其发送到输出集(output 表),在整个扫描完成后可以读取该输出集。

该算法为 O(n)。不管给出多少个关键字,或者搜索文本有多大,性能都会线性下降。

Aho-Corasick 算法可以帮助:

  • 在文本中找到要链接到或重点强调的单词;

  • 在纯文本中添加语义;

  • 检查字典以查看是否存在语法错误。

关于 AC 自动机的详细实现,强烈推荐:http://www.hankcs.com/program/algorithm/implementation-and-analysis-of-aho-corasick-algorithm-in-java.html




推荐阅读
  • 【转】强大的矩阵奇异值分解(SVD)及其应用
    在工程实践中,经常要对大矩阵进行计算,除了使用分布式处理方法以外,就是通过理论方法,对矩阵降维。一下文章,我在 ... [详细]
  • H5技术实现经典游戏《贪吃蛇》
    本文将分享一个使用HTML5技术实现的经典小游戏——《贪吃蛇》。通过H5技术,我们将探讨如何构建这款游戏的两种主要玩法:积分闯关和无尽模式。 ... [详细]
  • 菜鸟物流用户增长部现正大规模招聘P6及以上级别的JAVA工程师,提供年后入职选项。 ... [详细]
  • 线段树详解与实现
    本文详细介绍了线段树的基本概念及其在编程竞赛中的应用,并提供了一个具体的线段树实现代码示例。 ... [详细]
  • 在Java开发中,保护代码安全是一个重要的课题。由于Java字节码容易被反编译,因此使用代码混淆工具如ProGuard变得尤为重要。本文将详细介绍如何使用ProGuard进行代码混淆,以及其基本原理和常见问题。 ... [详细]
  • WPF MVVM: 动态添加控件与数据绑定的最佳实践
    本文介绍如何在WPF应用程序中使用MVVM模式动态添加控件并进行数据绑定。通过示例展示如何创建一个虚拟键盘,其中包含多个按键。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 探讨在内核中集成头文件的可行性与好处,特别是在处理外部模块和BPF应用时的作用。 ... [详细]
  • Python正则表达式(Python RegEx)
    Python正则表达式快速参考常用函数:re.match():从字符串的起始位置匹配一个正则表达式。re.search():扫描整个字符串并返回第一个成功的匹配。re.s ... [详细]
  • 本文详细介绍如何在华为鲲鹏平台上构建和使用适配ARM架构的Redis Docker镜像,解决常见错误并提供优化建议。 ... [详细]
  • 编译原理中的语法分析方法探讨
    本文探讨了在编译原理课程中遇到的复杂文法问题,特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略,包括递归下降解析、运算符优先级解析等,并提供了相关示例。 ... [详细]
  • 本打算教一步步实现koa-router,因为要解释的太多了,所以先简化成mini版本,从实现部分功能到阅读源码,希望能让你好理解一些。希望你之前有读过koa源码,没有的话,给你链接 ... [详细]
  • 本文介绍了 Oracle SQL 中的集合运算、子查询、数据处理、表的创建与管理等内容。包括查询部门号为10和20的员工信息、使用集合运算、子查询的注意事项、数据插入与删除、表的创建与修改等。 ... [详细]
  • centos 7.0 lnmp成功安装过程(很乱)
    下载nginx[rootlocalhostsrc]#wgethttp:nginx.orgdownloadnginx-1.7.9.tar.gz--2015-01-2412:55:2 ... [详细]
  • 本文介绍了 Confluence 6 中使用的其他 Cookie,这些 Cookie 主要用于存储产品的基本持久性和用户偏好设置,以提升用户体验。 ... [详细]
author-avatar
吻过彩虹的脸_378
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有