深入双数组Trie（Double-Array Trie）

最新推荐文章于 2024-03-09 15:32:49 发布
VIP文章 最新推荐文章于 2024-03-09 15:32:49 发布
阅读量2.3w 收藏 9
点赞数 2
分类专栏： C/C++（win32和linux） 算法研究(数据挖掘、机器学习、自然语言、深度学习、搜索引擎) 文章标签： 数据结构 apple 存储 struct c 算法
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/zhoubl668/article/details/6957830
版权
 

什么是Double Array Trie

  • Double Array Trie是TRIE树的一种变形，它是在保证TRIE树检索速度的前提下，提高空间利用率而提出的一种数据结构，本质上是一个确定有限自动机(deterministic finite automaton，简称DFA)。
  • 所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符，它都能根据事先给定的转移函数转移到下一个状态。
  • 对于Double Array Trie（以下简称DAT），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。
最低0.47元/天 解锁文章
beck_zhou
关注
  • 2
    点赞
  • 踩
  • 9
    收藏
    觉得还不错? 一键收藏
  • 4
    评论
专栏目录
双数组 DoubleArray Trie树的数组实现 双数组字典
10-26
Trie树是搜索树的一种，来自英文单词"Retrieval"的简写，可以建立有效的数据检索组织结构，是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态。在词典中这种状态包括＂词前缀＂，＂已成词＂等。 双数组Trie（Double-ArrayTrie）是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。设数组下标为i,如果base[i],check[i]均为0,表示该位置为空。如果base[i]为负值，表示该状态为词语。Check[i]表示该状态的前一状态，t=base[i]+a,check[t]=i
DoubleArrayTrie(双数组Trie树)
10-22
关于本源码更详细的解释说明，请参见：http://blog.csdn.net/lemon_tree12138/article/details/49281865
双数组Trie树原理理解以及具体示例
samoyan的博客,记录技术成长~
02-22 946
双数组Trie树是Trie树的一种高效实现方式，它使用两个数组来表示Trie树的结构，通常这两个数组分别称为BASE和CHECK。双数组Trie树的优势在于它能够在保持Trie树快速检索的同时，大幅减少内存的使用，并且提高了缓存的利用率。当我们要查找一个字符串时，从根节点开始，对于字符串中的每一个字符，都会使用BASE和CHECK数组进行计算和验证，以确定下一步的跳转位置。相比于传统的Trie树，双数组Trie树在内存使用上更加紧凑，因为它避免了指针的使用，并且数组的连续性有利于CPU缓存的优化。
双数组Trie树 (Double-array Trie) 及其应用
weixin_33939843的博客
01-09 198
双数组Trie树（Double-array Trie, DAT）是由三个日本人提出的一种Trie树的高效实现 [1]，兼顾了查询效率与空间存储。Ansj便是用DAT（虽然作者宣称是三数组Trie树，但本质上还是DAT）构造词典用作初次分词，极大地节省了内存占用。本文将简要地介绍DAT，并实现了基于DAT的前向最大匹配的中文分词算法。 1. Trie树 两种实现 Trie树（也称为字典树、前缀树）是...
DoubleArrayTrie: 高性能字符串查找算法实现
最新发布
gitblog_00003的博客
03-09 321
DoubleArrayTrie: 高性能字符串查找算法实现 DoubleArrayTrie 是一个高性能的字符串查找算法实现，基于双数组字典树（Double Array Trie）。它的设计目的是在大量的字符串集合中进行快速高效的查找操作。 什么是 DoubleArrayTrie？ DoubleArrayTrie 是一种字符串查找数据结构，基于双数组字典树（Double Array Trie）的...
双数组Trie树 Double-arrayTrie
hunyxv的博客
02-24 711
Tire 树结构存在较大的数据稀疏，造成了空间浪费。Double-array结合了array查询效率高、list节省空间的优点，可以有效降低空间浪费，具体是通过两个数组base、check来实现。Trie树可以等同于一个自动机，状态为树节点的编号，边为字符。 base数组中每个元素对应trie中的一个节点即状态； check数组表示的事某个状态的前驱状态，用来验证转移的有效性； 两个数组满足如下...
双数组字典树DoubleArrayTrie
懒猫的脚印
01-26 1516
双数组Tire树
Double Array Trie(一)
[email protected]
10-17 560
DoubleArrayTrie实现 　　Tire树终究是一颗树形结构，树形结构的两个重要要素便是前驱和后继，把Tire树压缩到双数组中，只需要保持能查询到每个节点的前驱和后继即可。Tire树中几个重要的概念。 STATE：状态，实际为在数组中的下标 CODE ： 状态转移值，实际为转移字符的 ASCII码, java中使用(int)(char c)和(char)(int i)互相转 BASE ...
DoubleArrayTrie 的原理理解和实现
不想做咸鱼的咸鱼的专栏
12-15 1301
平时使用双数组字典树的场景蛮多的，但是一直没有明白它的构建过程，再次，通过各位大佬的文章，终于终结出自己理解的双数组字典树的构造过程。 具体参考如下： https://blog.csdn.net/u013300579/article/details/78869742 https://blog.csdn.net/zhoubl668/article/details/6957830 https://gi...
深入浅出双数组字典树Double-arrayTrie（附代码）
qq_51652222的博客
02-24 397
今天NLP课上学习了双数组字典树的知识，听懂了但没完全懂，故总结一下。
什么是Double Array Trie
Java技术专栏
08-28 1234
什么是Double Array TrieDouble Array Trie是TRIE树的一种变形，它是在保证TRIE树检索速度的前提下，提高空间利用率而提出的一种数据结构，本质上是一个确定有限自动机(deterministic finite automaton，简称DFA)。 所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母
trie4j:PATRICIA，双数组，LOUDS Trie Java实现
04-30
Trie4J-Java的各种trie实现。 Trie4J是各种trie实现的集合。 您可以使用Maven获取二进制文件： < groupId>com.github.takawitter</ groupId> < artifactId>trie4j < version>0.9.8 或从 即将发布：无计划。...
双数组 Trie源码
09-21
darts, Double-Array Trie System. ver 0.32. Linux/Unix.
DoubleArrayTrie:高级结构双数组Trie树（DoubleArrayTrie） java实现
05-05
DoubleArrayTrie Java编写的DoubleArrayTrie介绍用法// construct and buildDoubleArrayTrie dat = new DoubleArrayTrie(); for(String word: words) { dat.Insert(word); } System.out.println(dat.Base.length);...
双数组trie树的基本构造及简单优化
最实用的Linux博客
10-14 2300
原贴：http://hunteagle.javaeye.com/blog/118550 双数组trie树的基本构造及简单优化 关键字:   trie 双数组     双数组trie树的基本构造及简单优
双数组AC自动机(doubleArrayTrie)的实现
hit_fantasy的专栏
12-13 4822
按照PPT上的描述写了个最简单的版本，没敢测大数据。 主要是几个表的构建： 首先构建next,base,check表。 根据失效函数的定义：父状态的失效函数输入当前字符，可得出每个状态的失效函数(要转移到的状态) 可以发现每个状态要转移到的状态是一定的，如下图： 所以可以构造一个fail表，由上述三个表来构建。 为了输出方便，又构造了一个output表。 代码如下： #incl
Trie树；双数组trie树
An_person的博客
07-16 277
将原来需要多个数组才能表示的Trie树，使用两个数组就可以存储下来，可以极大的减小空间复杂度。由于用base和check两个数组构成，又称为双数组字典树。具体来说就是使用两个数组base[]和check[]来维护Trie树，base[]负责记录状态，check[]用于检验状态转移的正确性，当check[i]为负值时，表示此状态为字符串的结束。
双数组树过程理解(Double-arrayTrie)
天涯的博客
04-26 1127
目录简介双数组的定义双数组树的构建理解参考资料 简介 双数组字典树由日本人Jun-Ichi Aoe在1989年提出，它由base和check两个数组组成，状态转移的复杂度为常数。这两个数组里面存在的内容为链接数组的下标，但是为了节约空间，在数据定义以及存储上各有千秋，除非看最原始的实现方式，否则各个博客中或者教程中的版本各有那么一点的不同，而本节就是其中的一种方式。 双数组的定义 原始的双数组定义...
帮我写一段用java实现的双数组Trie树匹配敏感词的算法例子
05-31
好的，以下是一个简单的基于双数组Trie树的敏感词过滤算法的Java实现： ```java import java.util.*; public class DoubleArrayTrie { private int[] base; // base数组 private int[] check; // check数组 ...

“相关推荐”对你有帮助么？

  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
提交
评论 4
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值