字典树-Trie树

字典树的实现与使用

Trie树

1、基本概念

字典树 ，又称为单词查找树， Tire数 ，是一种树形结构，它是一种哈希树的变种。

时间复杂度分析:

假设建立了有N个单词的每个单词的最大长度是L的字典Trie树，那么插入一个单词的最坏时间复杂度是O(L)，所以 建树的总的时间复杂度是O(NL)

查询一个单词前缀的单词个数最坏时间复杂度是O(L).

2、基本性质

根节点不包含字符，除根节点外的每一个子节点都包含一个字符

从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串

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

3、应用场景

典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。

4、优点

利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。

二、构建过程

1、节点定义

class TrieNode // 字典树节点
    {
        private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
        private TrieNode[] son;// 所有的儿子节点
        private boolean isEnd;// 是不是最后一个节点
        private char val;// 节点的值

        TrieNode()
        {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }

2、构造函数

Trie() // 初始化字典树
    {
        root = new TrieNode();
    }

3、建立字典树

// 建立字典树
    public void insert(String str) // 在字典树中插入一个单词
    {
        if (str == null || str.length() == 0)
        {
            return;
        }
        TrieNode node = root;
        char[] letters = str.toCharArray();//将目标单词转换为字符数组
        for (int i = 0, len = str.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)  //如果当前节点的儿子节点中没有该字符，则构建一个TrieNode并复值该字符
            {
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[i];
            } 
            else   //如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
            {
                node.son[pos].num++;
            }
            node = node.son[pos];
        }
        node.isEnd = true;
    }

4、 查找是否完全匹配一个指定的字符串

// 在字典树中查找一个完全匹配的单词.
    public boolean has(String str)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        //走到这一步，表明可能完全匹配，也可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
        return node.isEnd;
    }

5、前序遍历字典树

// 前序遍历字典树.
    public void preTraverse(TrieNode node)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
            for(TrieNode child:node.son)
            {
                preTraverse(child);
            }
        }
    }

6、计算单词前缀的数量

// 计算单词前缀的数量
    public int countPrefix(String prefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(int i=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

结果：

三、应用

(问题1)请你选择合适的数据结构，将所有的英文单词生成一个字典Dictionary？

(问题2)给定一个单词，判断这个单词是否在字典Dictionary中，如果在单词库中，输出这个单词出现总共出现的次数，否则输出NO？

package com.xj.test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Trie
{
    private int SIZE = 26;
    private TrieNode root;// 字典树的根

    class TrieNode // 字典树节点
    {
        private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
        private TrieNode[] son;// 所有的儿子节点
        private boolean isEnd;// 是不是最后一个节点
        private char val;// 节点的值

        TrieNode()
        {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }
    Trie() // 初始化字典树
    {
        root = new TrieNode();
    }
    

    // 建立字典树
    public void insert(String str) // 在字典树中插入一个单词
    {
        if (str == null || str.length() == 0)
        {
            return;
        }
        TrieNode node = root;
        char[] letters = str.toCharArray();//将目标单词转换为字符数组
        for (int i = 0, len = str.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)  //如果当前节点的儿子节点中没有该字符，则构建一个TrieNode并复值该字符
            {
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[i];
            } 
            else   //如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
            {
                node.son[pos].num++;
            }
            node = node.son[pos];
        }
        node.isEnd = true;
    }

    // 计算单词前缀的数量
    public int countPrefix(String prefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(int i=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

    // 打印指定前缀的单词
    public String hasPrefix(String prefix)
    {
        if (prefix == null || prefix.length() == 0)
        {
            return null;
        }
        TrieNode node = root;
        char[] letters = prefix.toCharArray();
        for (int i = 0, len = prefix.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)
            {
                return null;
            }
            else
            {
                node = node.son[pos];
            }
        }
        preTraverse(node, prefix);
        return null;
    }

    // 遍历经过此节点的单词.
    public void preTraverse(TrieNode node, String prefix)
    {
        if (!node.isEnd)
        {
            for (TrieNode child : node.son)
            {
                if (child != null)
                {
                    preTraverse(child, prefix + child.val);
                }
            }
            return;
        }
        System.out.println(prefix);
    }

    // 在字典树中查找一个完全匹配的单词.
    public boolean has(String str)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        //走到这一步，表明可能完全匹配，可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
        return node.isEnd;
    }

    // 前序遍历字典树.
    public void preTraverse(TrieNode node)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
            for(TrieNode child:node.son)
            {
                preTraverse(child);
            }
        }
    }
    public TrieNode getRoot()
    {
        return this.root;
    }
    public static void main(String[]args) throws IOException
    {
        Trie tree=new Trie();
        String[] dictionaryData= {"hello","student","computer","sorry","acm","people","experienced","who","reminds","everyday","almost"};
        //构建字典
        for(String str:dictionaryData)
        {
            tree.insert(str);
        }
        String filePath="C:\\Users\\Administrator\\Desktop\\sourceFile.txt";
        File file=new File(filePath);
        if(file.isFile() && file.exists())
        { 
            InputStreamReader read = new InputStreamReader(new FileInputStream(file));
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineTxt = null;
            Map<String,Integer> countMap=new HashMap<String,Integer>();
            while((lineTxt = bufferedReader.readLine())!= null)
            {
                if(tree.has(lineTxt))
                {
                    if(countMap.containsKey(lineTxt))
                    {
                        countMap.put(lineTxt, countMap.get(lineTxt)+1);
                    }
                    else
                    {
                        countMap.put(lineTxt, 1);
                    }
                }
                else
                {
                    System.out.println(lineTxt+"不在字典中！");
                }
            }
            for(String s:countMap.keySet())
            {
                System.out.println(s+"出现的次数"+countMap.get(s));
            }
            read.close();
        }
    }   
    
}

text文件内容：

结果：