Trie树分析

Trie树

Trie树介绍

Trie,又称单词查找树或键树,是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

它有3个基本性质:

1.根节点不包含字符,除根节点外每一个节点都只包含一个字符。

2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

Trie中每个节点有一个特殊标记作为结束符号,通过该标记可以判断当前节点是否是一个字符串的终结节点。

下图是一个Trie树的例子,记录了to,tea,ted,ten,a,i,in,inn这些words(以蓝色结尾)。

个人总结了如下方法:

Trie树的节点类

class Node{
     //节点字符值
     private char val;
     
     //节点的子节点,即以根节点到该节点的值组成的字符串为前缀的字符串构建的节点
     private Map<Character,Node> childrens=new HashMap<Character,Node>();
     
     //是否为结束节点,即一个字符串是否到达末尾节点   当end>0时表示结束节点
     private int end=0;
     //从根节点到该结束节点组成的字符串的重复数量  即单词列表中每个单词的词频
     private int dumpliNum=0;
     
     //以到达该节点组成的子串为前缀的字符串数量
     private int prexNum=0;


    /**
     * @return the dumpliNum
     */
    public int getDumpliNum() {
        return dumpliNum;
    }


    /**
     * @param dumpliNum the dumpliNum to set
     */
    public void setDumpliNum(int dumpliNum) {
        this.dumpliNum = dumpliNum;
    }


    /**
     * @return the prexNum
     */
    public int getPrexNum() {
        return prexNum;
    }


    /**
     * @param prexNum the prexNum to set
     */
    public void setPrexNum(int prexNum) {
        this.prexNum = prexNum;
    }


    /**
     * @return the val
     */
    public char getVal() {
        return val;
    }


    /**
     * @param val the val to set
     */
    public void setVal(char val) {
        this.val = val;
    }


    /**
     * @return the childrens
     */
    public Map<Character, Node> getChildrens() {
        return childrens;
    }


    /**
     * @param childrens the childrens to set
     */
    public void setChildrens(Map<Character, Node> childrens) {
        this.childrens = childrens;
    }


    /**
     * @return the end
     */
    public int getEnd() {
        return end;
    }


    /**
     * @param end the end to set
     */
    public void setEnd(int end) {
        this.end = end;
    }
 }

Trie树的初始化

public class Trie {

    //待构建的字符串列表
    private String words[];
    private Node root;

    public Trie(String[] words){
        this.root=new Node();
        this.words=words;
  }
}

Trie树的插入

//插入方法
   public void insert(String word){
        if(word==""||word==null){
            return;
        }
        Node cur=root;
        char [] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            //如果不存在该值,则创建新节点
            char val=chars[i];
            if(!cur.getChildrens().containsKey(val)){
                Node newNode=new Node();
                newNode.setVal(val);
                cur.getChildrens().put(val,newNode);
            }
            //如果已经存在则pass
            cur=cur.getChildrens().get(val);
            cur.setPrexNum(cur.getPrexNum()+1);
        }

        cur.setEnd(1);
        cur.setDumpliNum(cur.getDumpliNum()+1);
    }

Trie树的构建

public Node builtTrie(){
        for (int i=0;i<words.length;i++){
            insert(words[i]);
        }
        return root;
}

Trie树的查找

public boolean search(String word){
        boolean flag=true;
        Node cur=root;
        char[] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            if(!cur.getChildrens().containsKey(chars[i])){
               returnfalse;
            }
           cur=cur.getChildrens().get(chars[i]);//更新游标
         }
        return flag&&cur.getEnd()>0;//并且字符串最后一个字符必须是结束节点
}

Trie树中是否包某个前缀

    //以某个字符串开头  比如字符串列表中有[abb,abbb],则ab返回true
    public boolean startWith(String word){
        boolean flag=true;
        Node cur=root;
        char[] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            if(!cur.getChildrens().containsKey(chars[i])){
               return false;
            }
           cur=cur.getChildrens().get(chars[i]);//更新游标
         }
        //return flag&&cur.getEnd()>0;//并且该节点是结束节点
        return flag;//和查找相比去掉了字符串最后一个字符要是结束节点

}

Trie树前序遍历

  // 前序遍历,获取从指定节点开始,到所有结束节点组成的字符串
    Map<String, Node> preTraversal(Nodenode,String word){
        Map<String, Node> m=new HashMap<String,Node>();
        if(node!=null){
            if(node!=root&&node.getEnd()>0){
              m.put(word, node);
            }
            for(Map.Entry<Character, Node>entry:node.getChildrens().entrySet()){
                Node cur=entry.getValue();
                String temp=word+String.valueOf(cur.getVal());
               m.putAll(preTraversal(cur,temp));
             }

        }
        return m;
}

获取指定前缀出现次数

   //获取指定前缀出现次数
    int countPrefix(String prefix){
        Node cur =root;
        char[] chars=prefix.toCharArray();
        while(cur.getChildrens().size()>0){
            for(int i=0;i<chars.length;i++){
                if(cur.getChildrens().containsKey(chars[i])){
                   cur=cur.getChildrens().get(chars[i]);
                }
            }
            return cur.getPrexNum();
        }
        return 0;
}

获取含有指定前缀的所有单词

    //获取含有指定前缀的所有单词
    Map<String,Node>containPrefixOfwords(String prefix){
        Map<String,Node> m=newHashMap<String,Node>();
        //找到前缀的最后一个单词的所在节点
        Node cur=root;
        char[] chars=prefix.toCharArray();
        while(cur.getChildrens().size()>0){
            for(int i=0;i<chars.length;i++){
                if(cur.getChildrens().containsKey(chars[i])){
                   cur=cur.getChildrens().get(chars[i]);
                }else{
                    return null;
                }
            }
            break;
        }
        m.putAll(preTraversal(cur,prefix));
        return m;
}

全部代码和测试类

package trie;


import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
 * 
 *Trie
 * Trie树
 *@author: 汤高
 *@date: :2018-1-8 下午4:33:44
 *@version 1.0
 */
public class Trie {
    //待构建的字符串列表
    private String words[];
    private Node root;
    
    public Trie(String[] words){
        this.root=new Node();
        this.words=words;
    }
    public Node builtTrie(){
        int index=0;
        for (int i=0;i<words.length;i++){
            insert(words[i],++index);
        }
        return root;
        
    }
    //插入方法
    public void insert(String word){
        if(word==""||word==null){
            return;
        }
        Node cur=root;
        char [] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            //如果不存在该值,则创建新节点
            char val=chars[i];
            if(!cur.getChildrens().containsKey(val)){
                Node newNode=new Node();
                newNode.setVal(val);
                cur.getChildrens().put(val, newNode);
            }
            //如果已经存在则pass
            cur=cur.getChildrens().get(val);
            cur.setPrexNum(cur.getPrexNum()+1);
        }
        cur.setEnd(1);
        cur.setDumpliNum(cur.getDumpliNum()+1);
    }
    
    //插入方法
    public void insert(String word,int index){
        if(word==""||word==null){
            return;
        }
        Node cur=root;
        char [] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            //如果不存在该值,则创建新节点
            char val=chars[i];
            if(!cur.getChildrens().containsKey(val)){
                Node newNode=new Node();
                newNode.setVal(val);
                cur.getChildrens().put(val, newNode);
            }
            //如果已经存在则pass
            cur=cur.getChildrens().get(val);
            cur.setPrexNum(cur.getPrexNum()+1);
        }
        cur.setEnd(index);
        cur.setDumpliNum(cur.getDumpliNum()+1);
        
    }
    
    //查找方法
    public boolean search(String word){
        boolean flag=true;
        Node cur=root;
        char[] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            if(!cur.getChildrens().containsKey(chars[i])){
               return false;
            }
            cur=cur.getChildrens().get(chars[i]);//更新游标
         }
       
        return flag&&cur.getEnd()>0;//并且字符串最后一个字符必须是结束节点
    }
    
    //以某个字符串开头  比如 字符串列表中有[abb,abbb],则ab返回true
    public boolean startWith(String word){
        boolean flag=true;
        Node cur=root;
        char[] chars=word.toCharArray();
        for(int i=0;i<chars.length;i++){
            if(!cur.getChildrens().containsKey(chars[i])){
               return false;
            }
            cur=cur.getChildrens().get(chars[i]);//更新游标
         }
        //return flag&&cur.getEnd()>0;//并且该节点是结束节点
        return flag;//和查找相比去掉了 字符串最后一个字符要是结束节点
    }
    
    //前序遍历
    Map<String, Node> preTraversal(Node node,String word){
        Map<String, Node> m=new HashMap<String, Node>();
        if(node!=null){
            if(node!=root&&node.getEnd()>0){
              m.put(word, node);
            }
            for(Map.Entry<Character, Node> entry:node.getChildrens().entrySet()){
                Node cur=entry.getValue();
                String temp=word+String.valueOf(cur.getVal());
                m.putAll(preTraversal(cur,temp));
             }
        }
        return m;
    }
    
    //获取指定前缀出现次数
    int countPrefix(String prefix){
        Node cur =root;
        char[] chars=prefix.toCharArray();
        while(cur.getChildrens().size()>0){
            for(int i=0;i<chars.length;i++){
                if(cur.getChildrens().containsKey(chars[i])){
                    cur=cur.getChildrens().get(chars[i]);
                }
            }
            return cur.getPrexNum();
        }
        return 0;
    }
    
    //获取含有指定前缀的所有单词
    Map<String,Node> containPrefixOfwords(String prefix){
        Map<String,Node> m=new HashMap<String,Node>();
        //找到前缀的最后一个单词的所在节点
        Node cur=root;
        char[] chars=prefix.toCharArray();
        while(cur.getChildrens().size()>0){
            for(int i=0;i<chars.length;i++){
                if(cur.getChildrens().containsKey(chars[i])){
                    cur=cur.getChildrens().get(chars[i]);
                }else{
                    return null;
                }
            }
            break;
        }
        m.putAll(preTraversal(cur,prefix));
        return m;
    }
    
    String getMax(){
        String result="";
        Stack<Node> stack=new Stack<Node>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node node=stack.pop();
            if(node.getEnd()>0||node==root){
                if(node!=root){
                    String word= this.words[node.getEnd()-1];
                    if(word.length()>result.length()||
                            word.length()==result.length()&&result.compareTo(word)>0){//最长的且具有最小字典序的word
                       
                        result=word;
                    }
                }
                for(Node n:node.getChildrens().values()){//拿到子节点
                    stack.push(n);
                }
            }
        }
        return result;
        
    }
    
    class Node{
     //节点字符值
     private char val;
     
     //节点的子节点,即以根节点到该节点的值组成的字符串为前缀的字符串构建的节点
     private Map<Character,Node> childrens=new HashMap<Character,Node>();
     
     //是否为结束节点,即一个字符串是否到达末尾节点   当end>0时表示结束节点
     private int end=0;
     //从根节点到该结束节点组成的字符串的重复数量  即单词列表中每个单词的词频
     private int dumpliNum=0;
     
     //以到达该节点组成的子串为前缀的字符串数量
     private int prexNum=0;


    /**
     * @return the dumpliNum
     */
    public int getDumpliNum() {
        return dumpliNum;
    }


    /**
     * @param dumpliNum the dumpliNum to set
     */
    public void setDumpliNum(int dumpliNum) {
        this.dumpliNum = dumpliNum;
    }


    /**
     * @return the prexNum
     */
    public int getPrexNum() {
        return prexNum;
    }


    /**
     * @param prexNum the prexNum to set
     */
    public void setPrexNum(int prexNum) {
        this.prexNum = prexNum;
    }


    /**
     * @return the val
     */
    public char getVal() {
        return val;
    }


    /**
     * @param val the val to set
     */
    public void setVal(char val) {
        this.val = val;
    }


    /**
     * @return the childrens
     */
    public Map<Character, Node> getChildrens() {
        return childrens;
    }


    /**
     * @param childrens the childrens to set
     */
    public void setChildrens(Map<Character, Node> childrens) {
        this.childrens = childrens;
    }


    /**
     * @return the end
     */
    public int getEnd() {
        return end;
    }


    /**
     * @param end the end to set
     */
    public void setEnd(int end) {
        this.end = end;
    }
 }
    
    public static void main(String[] args) {
       String[] words=new String[]{"ab","abb","ab","abbc","b","ba","bdd"};
      
        Trie t=new Trie(words);
        Node root=t.builtTrie();//构建trie树
            
        System.out.println("trie树包含bdd吗?  "+t.search("bdd"));
        System.out.println("trie树包含bd吗?  "+t.search("bd"));


        System.out.println("trie树包含bd前缀吗?"+t.startWith("bd"));
        System.out.println("trie树包含bdX前缀吗?"+t.startWith("bdX"));
        
        System.out.println("根节点前序遍历,获取所有单词和它出现的次数");
        for(Map.Entry<String, Node> en:t.preTraversal(root, "").entrySet()){
            System.out.println(en.getKey()+"出现几次:"+en.getValue().dumpliNum);
        }
        
        System.out.println("以ab开头的前缀出现几次:"+t.countPrefix("ab"));
        
        System.out.println("包含ab为前缀的所有单词");
        for(Map.Entry<String, Node> en:t.containPrefixOfwords("ab").entrySet()){
            System.out.println(en.getKey()+"单词出现几次:"+en.getValue().dumpliNum);
        }
    }
}

测试结果

trie树包含bdd吗?  true

trie树包含bd吗?  false

trie树包含bd前缀吗?true

trie树包含bdX前缀吗?false

根节点前序遍历,获取所有单词和它出现的次数

abb出现几次:1

b出现几次:1

ba出现几次:1

bdd出现几次:1

abbc出现几次:1

ab出现几次:2

以ab开头的前缀出现几次:4

包含ab为前缀的所有单词

abb单词出现几次:1

ab单词出现几次:2

abbc单词出现几次:1

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏破晓之歌

JAVA入门3-1 原

在程序开发中字符串无处不在,如用户登陆时输入的用户名、密码等使用的就是字符串。其实,在前面的章节中我们就已经使用了字符串,例如我们在控制台中输出的 "Hello...

1194
来自专栏好好学java的技术栈

“面试不败计划”:集合知识整体总结

1373
来自专栏郭耀华‘s Blog

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法 ArrayList 和Vector是采用...

3878
来自专栏小灰灰

JDK容器学习之LinkedHashMap (一):底层存储结构分析

LinkedHashMap 底层存储结构分析 HashMap 是无序的kv键值对容器,TreeMap 则是根据key进行排序的kv键值对容器,而LinkedH...

1985
来自专栏java学习

Java每日一练(2017/7/19)

本期题目: (单选题) 1、设int x=1,float y=2,则表达式x/y的值是:() A 0 B 1 C 2 D 以上都不是 ---- (单选题)2、若...

2918
来自专栏石奈子的Java之路

原 java数据结构与算法之数组篇

2044
来自专栏noteless

-1-3 java集合框架基础 java集合体系结构 Collection 常用java集合框架 如何选择集合 迭代器 泛型 通配符概念 Properties 集合 迭代器

                        数组可以是基本类型,也可以是引用类型

1242
来自专栏Golang语言社区

Go语言单链表实现方法

////////// //单链表 -- 线性表 package singlechain //定义节点 type Node struct { Data in...

3056
来自专栏每日一篇技术文章

Swift3.0 - 枚举

782
来自专栏技术碎碎念

LeetCode-66-Plus One

Given a non-negative number represented as an array of digits, plus one to the n...

3406

扫码关注云+社区

领取腾讯云代金券