一、概述
1、字典树（Trie Tree）
又称单词查找树。哈希树的变种，常用于统计、查找搜索引擎中用于分词，词频统计（TF/IDF）,自动补全机制等。
查找效率高：其核心思想是利用公共前缀来减少查询时间。
字典树
2、基本性质
- 根结点不包含字符,除根结点外的每一个子结点都包含一个字符。
- 从根结点到某一结点，路径上经过的字符连接起来，就是该结点对应的字符串。
- 每个节点的所有的子节点包含的字符都不相同。
3、应用场景
典型应用是用于统计、排序和保存大量的字符串（不仅限于字符串），经常常用于统计、查找搜索引擎中用于分词，词频统计（TF/IDF）,自动补全机制等。
4、优点
利用字符串的公共前缀来减少查询时间，最大限度的减少无畏的字符串比较，查询效率比哈希树高。
二、构建过程
- 思考：1000w个单词，让你去找某一个词是否在这1000w中。
假设，机器：1台，2G配置
Hash表，时间复杂度：0(1)，机器的配置能存下？
分布式任务，但这里已经假定。
用什么方式？ => 字典树 （Tire树，中文的变种）
1、构建一个字典树
构建字典树
2、具体实现代码
- 字典树结点定义
/**
* @version: V1.0
* @author: hejianhui
* @className: TrieTree
* @packageName: com.nuih.algorithm
* @description: 字典树结点定义
* @data: 2018-12-08 23:12
**/
public class TreeNode{
// 26个单词
final static int MAX_SZIE = 26;
// 表示当前结点存的字母
char data;
// 表示是否为叶子结点
boolean isEnd = true;
// 表示子节点
TreeNode[] childs;
public TreeNode() {
this.isEnd = false;
// 因为英文最多26个字母
this.childs = new TreeNode[MAX_SZIE];
}
}
- 创建字典树
在此之前先回忆一下Ascii代码
Ascii
/**
* 创建字典树
* @param node 字典树结点
* @param str 单词(单词全部转成小写)
*/
public static void createTrieTree(TreeNode node,String str){
// ascii A => 65 ，a => 97, (97- 97 => 0)
// a ->0, b ->1, c ->2
char d[] = str.toCharArray();
for (int i=0; i<d.length; i++){
// 转成0~25之间的数字了，这里是一个小技巧
int loc = d[i] - 'a';
if(node.childs[loc] == null){
node.childs[loc] = new TreeNode();
node.childs[loc].data = d[i];
}
node = node.childs[loc];
}
node.isEnd = true;
}
- 在字典树中查找是否完全匹配一个指定的字符串
/**
* 字典树查找
* @param node 字典树
* @param str 单词
* @return
*/
public static boolean find(TreeNode node, String str){
char d[] = str.toCharArray();
for (int i=0; i<d.length; i++){
int loc = d[i] - 'a';
if(node.childs[loc] != null){
node = node.childs[loc];
}else{
return false;
}
}
return node.isEnd;
}
- 验证
public static void main(String[] args){
String s[] = {"css", "php", "python", "java", "js", "vue"};
TreeNode root = new TreeNode();
for (String ss : s){
createTrieTree(root, ss);
}
System.out.println("插入完成===>");
System.out.println(find(root,"java"));
// 找前缀就是自动补全
System.out.println(find(root,"jav"));
}
输出结果
- 完整代码
package com.nuih.algorithm;
/**
* @version: V1.0
* @author: hejianhui
* @className: TrieTree
* @packageName: com.nuih.algorithm
* @description: 字典树（Trie)
* @data: 2018-12-08 23:12
**/
public class TrieTree {
/**
* 创建字典树
* @param node 字典树结点
* @param str 单词(单词全部转成小写)
*/
public static void createTrieTree(TreeNode node,String str){
// ascii A => 65 ，a => 97, (97- 97 => 0)
// a ->0, b ->1, c ->2
char d[] = str.toCharArray();
for (int i=0; i<d.length; i++){
// 转成0~25之间的数字了，这里是一个小技巧
int loc = d[i] - 'a';
if(node.childs[loc] == null){
node.childs[loc] = new TreeNode();
node.childs[loc].data = d[i];
}
node = node.childs[loc];
}
node.isEnd = true;
}
/**
* 字典树查找
* @param node 字典树
* @param str 单词
* @return
*/
public static boolean find(TreeNode node, String str){
char d[] = str.toCharArray();
for (int i=0; i<d.length; i++){
int loc = d[i] - 'a';
if(node.childs[loc] != null){
node = node.childs[loc];
}else{
return false;
}
}
return node.isEnd;
}
public static void main(String[] args){
String s[] = {"css", "php", "python", "java", "js", "vue"};
TreeNode root = new TreeNode();
for (String ss : s){
createTrieTree(root, ss);
}
System.out.println("插入完成===>");
System.out.println(find(root,"java"));
// 找前缀就是自动补全
System.out.println(find(root,"jav"));
}
}
/**
* @version: V1.0
* @author: hejianhui
* @className: TreeNode
* @packageName: com.nuih.algorithm
* @description: 字典树结点定义
* @data: 2018-12-08 23:12
**/
class TreeNode{
// 26个单词
final static int MAX_SZIE = 26;
// 表示当前结点存的字母
char data;
// 表示是否为叶子结点
boolean isEnd = true;
// 表示子节点
TreeNode[] childs;
public TreeNode() {
this.isEnd = false;
// 因为英文最多26个字母
this.childs = new TreeNode[MAX_SZIE];
}
}
