文档章节

Trie树使用实例

go4it
 go4it
发布于 2017/08/23 22:29
字数 267
阅读 41
收藏 0

本文简单介绍下apache collection4中的PatriciaTrie的使用。

Trie树

Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构。

  • 应用 经常被搜索引擎系统用于文本词频统计。同时,它也是很多算法和复杂数据结构的基础,如后缀树,AC自动机等
  • 优点 最大限度地减少无谓的字符串比较,查询效率比哈希表高。
  • 缺点 如果系统中存在大量字符串且这些字符串基本没有公共前缀,则相应的trie树将非常消耗内存,这也是trie树的一个缺点。

maven

        <dependency>
			<groupId>org.apache.commons</groupId>
			<artifactId>commons-collections4</artifactId>
			<version>4.1</version>
		</dependency>

使用

@Test
    public void testContains(){
        PatriciaTrie<Double> t = new PatriciaTrie<Double>();

        t.put("ronak", 100.0);
        t.put("ronald", 90.0);
        t.put("rat", 50.0);
        t.put("robert", 200.0);
        t.put("bat", 44.0);
        t.put("batman", 440.0);


        System.out.println(t.containsKey("ronak"));
        System.out.println(t.selectKey("ro"));
        System.out.println(t.prefixMap("r"));
        System.out.println(t.prefixMap("ro"));
        System.out.println(t.prefixMap("ron"));
    }

输出

true
robert
{rat=50.0, robert=200.0, ronak=100.0, ronald=90.0}
{robert=200.0, ronak=100.0, ronald=90.0}
{ronak=100.0, ronald=90.0}

doc

© 著作权归作者所有

go4it
粉丝 90
博文 1126
码字总数 1057866
作品 0
深圳
私信 提问
使用level-compression tire树来实现快速IP路由查找(http://www.csc.kth.se/~snilsson/fast-routing/#fig)

IP地址查找 IP协议以包的形式来发送数据。每个包头中除了其他东西外,都有一个目的地址。IPv4中该地址是一个32位的数字。而在IPv6中,位数将增加到128位。 当一个包通过Internet来发送时,它...

我是*李世民*
2012/06/18
169
0
TypeScript:Aho–Corasick算法实现敏感词过滤

敏感词过滤应该是许多后端同事经常会遇到的需求,无论是评论、弹幕、文章,都需要做敏感词过滤处理来规避风险。在前端开发中,使用replace函数来替换字符串是我们的常规操作,在这之前我思考...

ZheLin
06/07
0
0
LeetCode 208. Implement Trie (Prefix Tree) (实现Trie树)

原题 Implement a trie with , , and methods. Example: Note: You may assume that all inputs are consist of lowercase letters . All inputs are guaranteed to be non-empty strings. R......

dby_freedom
2018/12/03
0
0
算法 | 动画+解析,轻松理解「Trie树」

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。 此外 Trie 树也称前缀树(因为某节点...

AI科技大本营
01/06
0
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-Trie字典树

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
03/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部