前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Trie树使用实例

Trie树使用实例

作者头像
code4it
发布2018-09-17 14:52:16
1.2K0
发布2018-09-17 14:52:16
举报
文章被收录于专栏:码匠的流水账

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

Trie树

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

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

maven

代码语言:javascript
复制
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-collections4</artifactId>
            <version>4.1</version>
        </dependency>

使用

代码语言:javascript
复制
@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"));
    }

输出

代码语言:javascript
复制
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

  • 数据结构之Trie树
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码匠的流水账 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Trie树
  • maven
  • 使用
  • doc
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档