閱讀目錄
字典樹，又稱為單詞查找樹，Tire數，是一種樹形結構，它是一種哈希樹的變種。
典型應用是用於統計，排序和保存大量的字符串(不僅限於字符串)，經常被搜索引擎系統用於文本詞頻統計。
利用字符串的公共前綴來減少查詢時間，最大限度的減少無謂的字符串比較，查詢效率比哈希樹高。
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 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 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文件內容為：
程序執行結果為：
