字典树（Trie树）实现与应用

阅读目录

一、概述
二、构建过程
三、简单应用
四、参考资料

一、概述

1、基本概念

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

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;} 完整代码：package com.xj.test;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）{Trie tree=new Trie（）;String[]strs= {"banana","band","bee","absolute","acm",};String[]prefix= {"ba","b","band","abc",};for（String str:strs）{tree.insert（str）;}System.out.println（tree.has（"abc"））;tree.preTraverse（tree.getRoot（））;System.out.println（）;//tree.printAllWords（）;for（String pre:prefix）{int num=tree.countPrefix（pre）;System.out.println（pre+"数量:"+num）;}}} 执行结果截图：

三、简单应用

下面讲一个简单的应用，问题是这样的：现在有一个英文字典（每个单词都是由小写的a-z组成），单词量很大，而且还有很多重复的单词。此外，我们还有一些Document，每个Document包含一些英语单词。下面是问题：（问题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文件内容为：程序执行结果为： 本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/133588.htm