1、Trie树概述
概念
字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。
基本性质
1）根节点不包含字符，除根节点外的每一个子节点都包含一个字符
2）从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
3）每个节点的所有子节点包含的字符都不相同
应用场景
典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。
优点
利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。
2、代码实现
定义Trie树节点
Trie树节点包含四个关键的属性，分别是由根至该节点组成的字符串模式出现的次数，所有的儿子节点(儿子节点也是字典树节点)，是否是最后一个节点以及节点的值。
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 class Trie {
private int SIZE = 26;
private TrieNode root;// 字典树的根
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=letters.length;i<len;i++){
int pos = letters[i] - 'a';
if(node.son[pos] == null){
node.son[pos] = new TrieNode();
node.son[pos].val = letters[I];
}
else{
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();
int len = letters.length;
for(int i =0;i<len;i++){
int pos = letters[i] - 'a';
if(node.son[pos] == null){
return 0;
}
node = node.son[pos];
}
return node.num;
}
遍历经过此节点的单词
// 遍历经过此节点的单词.
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;i<letters.length;i++){
int pos = letters[i] - 'a';
if(node.son[pos]==null){
return false;
}
node = node.son[pos];
}
return node.isEnd;
}
前序遍历
public void preTraverse(TrieNode node){
if(node==null)
return;
else{
System.out.print(node.val + "-");
for(TrieNode child:node.son){
preTraverse(child);
}
}
}
3、完整实例
import java.io.*;
import java.util.*;
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=letters.length;i<len;i++){
int pos = letters[i] - 'a';
if(node.son[pos] == null){
node.son[pos] = new TrieNode();
node.son[pos].val = letters[I];
}
else{
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();
int len = letters.length;
for(int i =0;i<len;i++){
int pos = letters[i] - 'a';
if(node.son[pos] == null){
return 0;
}
node = node.son[pos];
}
return node.num;
}
// 打印指定前缀的单词
public void hasPrefix(String prefix){
if(prefix == null || prefix.length() == 0){
return;
}
TrieNode node = root;
char[] letters = prefix.toCharArray();
for(int i=0;i<letters.length;i++){
int pos = letters[i] - 'a';
if(node.son[pos]==null)
return;
node = node.son[pos];
}
preTraverse(node,prefix);
}
// 遍历经过此节点的单词.
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;i<letters.length;i++){
int pos = letters[i] - 'a';
if(node.son[pos]==null){
return false;
}
node = node.son[pos];
}
return node.isEnd;
}
//前序遍历
public void preTraverse(TrieNode node){
if(node==null)
return;
else{
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="/Users/meituan_sxw/IdeaProjects/ccc/src/main/java/sourceFile.txt";
File file=new File(filePath);
System.out.println(file.isFile() && file.exists());
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文件内容为：
程序执行结果为：
