Trie树使用实例

bingchen 发布于2019-08-16 10:40 / 1546人阅读

摘要：序本文简单介绍下中的的使用。树树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构。应用经常被搜索引擎系统用于文本词频统计。使用输出数据结构之树

序

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

Trie树

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

应用
经常被搜索引擎系统用于文本词频统计。同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等

优点
最大限度地减少无谓的字符串比较，查询效率比哈希表高。

缺点
如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。

maven

        
            org.apache.commons
            commons-collections4
            4.1

使用

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

        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

数据结构之Trie树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70226.html

javascript 前缀Trie

摘要：很容易看出，前缀最坏情况下的查找也快过二叉搜索树。这种压缩后的被唤作前缀压缩，或直接叫前缀树，字典树。最长公共前缀和的最长公共前缀是，遍历字典树到字母时，此时这些单词的公共前缀是。引子前缀Trie, 又叫字符Tire, trie来自单词retrieval, 一开始念作tree，后来改念try，毕竟它与树是不一样的东西。网上许多文章都搞混了trie与树。 trie是通过边来储存字符...

xiaochao 2019-08-22 14:05 评论0 收藏0
Trie树 php 实现敏感词过滤

摘要：在树中，每个节点表示一个状态，每条边表示一个字符，从根节点到叶子节点经过的边即表示一个词条。查找一个词条最多耗费的时间只受词条长度影响，因此的查找性能是很高的，跟哈希算法的性能相当。 Last-Modified: 2019年5月10日15:25:35 参考文章 c++ 使用map实现Trie树关键词过滤扩展，用于检查一段文本中是否出现敏感词，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 评论0 收藏0
208-实现 Trie (前缀树)

摘要：前言前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是参考教程的思路去解答，希望可以给大家一个参考。下面是原题目实现一个前缀树，包含和这三个操作。前言前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于LeetCode中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是...

antyiwei 2019-08-19 10:50 评论0 收藏0
[Leetcode] Implement Trie 实现前缀树

摘要：压缩前缀树其实就是将所有只有一个子节点的节点合并成一个，以减少没有意义的类似链表式的链接。然后我们开始遍历这个前缀树。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

jsliang 2019-08-14 12:28 评论0 收藏0
如何快速实现高并发短文检索

摘要：问龙哥，还有什么更好，更轻量级的方案么龙哥用树，数据会膨胀文档数标题长度这么多，标题越长，文档数越多，内存占用越大。一、需求缘起某并发量很大，数据量适中的业务线需要实现一个标题检索的功能：（1）并发量较大，每秒20w次（2）数据量适中，大概200w数据（3）是否需要分词：是（4）数据是否实时更新：否二、常见潜在解决方案及优劣（1）数据库搜索法具体方法：将标题数据存放在数据库中，使用...

URLOS 2019-06-28 13:51 评论0 收藏0