专栏首页开发架构二三事双数组Trie树与AC自动机简要总结

双数组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

本文分享自微信公众号 - 开发架构二三事(gh_d6f166e26398),作者:两个小灰象

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • kotlin整合spring cglib问题分析

    此时在浏览器中访问:http://localhost:8080/api/test/list的方法栈如下:

    开发架构二三事
  • shiro实战之改造成token格式的无状态restful api

    通过调用context.setSessionCreationEnabled(false)表示不创建会话;如果之后调用Subject.getSession()将抛...

    开发架构二三事
  • netty源码分析之三Bootstrap初始化

    可以看到childGroup也就是group方法传入的workerGroup是赋值给ServerBootstrap的childGroup属性的。我们进入 sup...

    开发架构二三事
  • 现场|从新一代TPU到Google.ai,详解谷歌I/O首日人工智能五大亮点

    机器之心原创 记者:CZ、Tony Peng 当地时间 5 月 17 日,谷歌在山景城开启了本年度的谷歌 I/O 开发者大会。昨日机器之心对此次大会上将出现的有...

    机器之心
  • 【Go 语言社区】Go worker线程池

    Worker Pools package main import "fmt" import "time" // 使用goroutine 开启大小为3的线程池 ...

    李海彬
  • 6年做BPM的实施、开发、推广应用的一个小结

    晚上加班整理了一下这些年(从2010年就开始使用了)FlowPortal.Net BPM的使用情况,希望能从用户、流程、申请、效率、价值等角度做一些可视化的分析...

    崔文远TroyCui
  • 基于数组越界的缓冲区溢出

    上一篇文章说了函数调用时候的堆栈变化,这里就基于这个内容来验证一下基于数组越界的缓冲区溢出。

    无心的梦呓
  • Activiti开发学习笔记2

    前面章节,讲述了 Activiti 的配置,根据这些配置,可以创建相应的流提供了多种创建流程引擎的方式供研发人员选择,可以通过 ProcessEng的 buil...

    程序源代码
  • 认识工作流-Activiti

    一、什么是工作流(wrokflow)? 对于工作流,其实大家不太陌生,其实生活中到处会存在流程这个概念。比如 :在公司单位要请假,我们首先要找到...

    程序源代码
  • 姜奇平解读“互联网+”改变产业生态(二)

    2015年5月12日晚,腾讯研究院与TechWeb联合主办的“互联网前沿沙龙第11期如期举行。中国社会科学院信息化研究中心秘书长、《互联网周刊》主编姜奇平就“...

    腾讯研究院

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动