热门标签 | 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




推荐阅读
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 当前物联网领域十大核心技术解析:涵盖哪些关键技术?
    经过近十年的技术革新,物联网已悄然渗透到日常生活中,对社会产生了深远影响。本文将详细解析当前物联网领域的十大核心关键技术,包括但不限于:1. 军事物联网技术,该技术通过先进的感知设备实现战场环境的实时监测与数据传输,提升作战效能和决策效率。其他关键技术还包括传感器网络、边缘计算、大数据分析等,这些技术共同推动了物联网的快速发展和广泛应用。 ... [详细]
  • C++ 开发实战:实用技巧与经验分享
    C++ 开发实战:实用技巧与经验分享 ... [详细]
  • Presto:高效即席查询引擎的深度解析与应用
    本文深入解析了Presto这一高效的即席查询引擎,详细探讨了其架构设计及其优缺点。Presto通过内存到内存的数据处理方式,显著提升了查询性能,相比传统的MapReduce查询,不仅减少了数据传输的延迟,还提高了查询的准确性和效率。然而,Presto在大规模数据处理和容错机制方面仍存在一定的局限性。本文还介绍了Presto在实际应用中的多种场景,展示了其在大数据分析领域的强大潜力。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • 计算机视觉领域介绍 | 自然语言驱动的跨模态行人重识别前沿技术综述(上篇)
    本文介绍了计算机视觉领域的最新进展,特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点,为读者提供了全面的概述。 ... [详细]
  • REST与RPC:选择哪种API架构风格?
    在探讨REST与RPC这两种API架构风格的选择时,本文首先介绍了RPC(远程过程调用)的概念。RPC允许客户端通过网络调用远程服务器上的函数或方法,从而实现分布式系统的功能调用。相比之下,REST(Representational State Transfer)则基于资源的交互模型,通过HTTP协议进行数据传输和操作。本文将详细分析两种架构风格的特点、适用场景及其优缺点,帮助开发者根据具体需求做出合适的选择。 ... [详细]
  • 本文探讨了Nginx在处理静态和动态URL时的配置与优化技巧。通过示例展示了如何将复杂的动态URL重写为简洁的静态URL,如将`http://test.dev/televisionSearch?searchword=20&a`转换为`http://test.dev/search_sw_20_p_1.html`。此外,还介绍了如何利用Nginx的重写规则和缓存机制,提高网站性能和用户体验。 ... [详细]
  • 本文详细介绍了如何安全地手动卸载Exchange Server 2003,以确保系统的稳定性和数据的完整性。根据微软官方支持文档(https://support.microsoft.com/kb833396/zh-cn),在进行卸载操作前,需要特别注意备份重要数据,并遵循一系列严格的步骤,以避免对现有网络环境造成不利影响。此外,文章还提供了详细的故障排除指南,帮助管理员在遇到问题时能够迅速解决,确保整个卸载过程顺利进行。 ... [详细]
  • 能够感知你情绪状态的智能机器人即将问世 | 科技前沿观察
    本周科技前沿报道了多项重要进展,包括美国多所高校在机器人技术和自动驾驶领域的最新研究成果,以及硅谷大型企业在智能硬件和深度学习技术上的突破性进展。特别值得一提的是,一款能够感知用户情绪状态的智能机器人即将问世,为未来的人机交互带来了全新的可能性。 ... [详细]
  • 深入探讨:Java 8 中 HashMap 链表为何选择红黑树而非 AVL 树
    深入探讨:Java 8 中 HashMap 链表为何选择红黑树而非 AVL 树 ... [详细]
  • 投融资周报 | Circle 达成 4 亿美元融资协议,唯一艺术平台 A 轮融资超千万美元 ... [详细]
  • 本文深入探讨了使用Puppet进行软件包分发与管理的方法。首先介绍了fpm这一跨平台的软件包制作工具,其简便的操作流程使得软件包的创建变得轻松快捷。fpm的项目地址为:https://github.com/jordansissel/fpm。通过结合Puppet和fpm,可以实现高效、可靠的软件包管理和部署。 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • 通过纯CSS技术,可以轻松创建精致的小圆点和三角形图形。本文详细介绍了如何利用CSS的伪元素、边框和背景属性,实现这些图形的高效绘制,并提供了多种应用场景和示例代码,帮助开发者在网页设计中增添更多视觉效果。 ... [详细]
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社区 版权所有