前言
繼上一篇HashMap實(shí)現(xiàn)中文分詞器后罩旋，對(duì)Trie Tree的好奇和二，又使用Trie Tree實(shí)現(xiàn)了下中文分詞器。效率比HashMap實(shí)現(xiàn)的分詞器更高携冤。
Trie Tree 簡(jiǎn)介
Trie Tree卵皂，又稱單詞字典樹秩铆、查找樹，是一種樹形結(jié)構(gòu)渐裂，是一種哈希樹的變種豺旬。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)柒凉。它的優(yōu)點(diǎn)是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高篓跛。
性質(zhì)
它有3個(gè)基本性質(zhì)：
- 根節(jié)點(diǎn)不包含字符膝捞，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
- 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)愧沟，路徑上經(jīng)過的字符連接起來蔬咬，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同沐寺。
Trie Tree 結(jié)構(gòu)
Trie Tree
Trie Tree分詞原理：
(1) 從根結(jié)點(diǎn)開始一次搜索林艘，比如搜索【北京】；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字符【北】混坞，并根據(jù)該字符選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索狐援；
(3) 在相應(yīng)的子樹上钢坦，取得要查找關(guān)鍵詞的第二個(gè)字符【京】,并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。
(4) 迭代過程……
(5) 在直到判斷樹節(jié)點(diǎn)的isEnd節(jié)點(diǎn)為true則查找結(jié)束（最小匹配原則）啥酱，然后發(fā)現(xiàn)【京】isEnd=true爹凹，則結(jié)束查找。
示例
下面用java簡(jiǎn)單實(shí)現(xiàn)
package cn.com.infcn.algorithm;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* jijs
* 正向最大匹配
*/
public class TrieTreeDemo {
static class Node {
//記錄當(dāng)前節(jié)點(diǎn)的字
char c;
//判斷該字是否詞語的末尾镶殷，如果是則為false
boolean isEnd;
//子節(jié)點(diǎn)
List<Node> childList;
public Node(char c) {
super();
this.c = c;
isEnd = false;
childList = new LinkedList<Node>();
}
//查找當(dāng)前子節(jié)點(diǎn)中是否保護(hù)c的節(jié)點(diǎn)
public Node findNode(char c){
for(Node node : childList){
if(node.c == c){
return node;
}
}
return null;
}
}
static class TrieTree{
Node root = new Node(' ');
//構(gòu)建Trie Tree
public void insert(String words){
char[] arr = words.toCharArray();
Node currentNode = root;
for (char c : arr) {
Node node = currentNode.findNode(c);
//如果不存在該節(jié)點(diǎn)則添加
if(node == null){
Node n = new Node(c);
currentNode.childList.add(n);
currentNode = n;
}else{
currentNode = node;
}
}
//在詞的最后一個(gè)字節(jié)點(diǎn)標(biāo)記為true
currentNode.isEnd = true;
}
//判斷Trie Tree中是否包含該詞
public boolean search(String word){
char[] arr = word.toCharArray();
Node currentNode = root;
for (int i=0; i<arr.length; i++) {
Node n = currentNode.findNode(arr[i]);
if(n != null){
currentNode = n;
//判斷是否為詞的尾節(jié)點(diǎn)節(jié)點(diǎn)
if(n.isEnd){
if(n.c == arr[arr.length-1]){
return true;
}
}
}
}
return false;
}
//最大匹配優(yōu)先原則
public Map<String, Integer> tokenizer(String words){
char[] arr = words.toCharArray();
Node currentNode = root;
Map<String, Integer> map = new HashMap<String, Integer>();
//記錄Trie Tree 從root開始匹配的所有字
StringBuilder sb = new StringBuilder();;
//最后一次匹配到的詞禾酱，最大匹配原則，可能會(huì)匹配到多個(gè)字绘趋，以最長的那個(gè)為準(zhǔn)
String word="";
//記錄記錄最后一次匹配坐標(biāo)
int idx = 0;
for (int i=0; i<arr.length; i++) {
Node n = currentNode.findNode(arr[i]);
if(n != null){
sb.append(n.c);
currentNode = n;
//匹配到詞
if(n.isEnd){
//記錄最后一次匹配的詞
word = sb.toString();
//記錄最后一次匹配坐標(biāo)
idx = i;
}
}else{
//判斷word是否有值
if(word!=null && word.length()>0){
Integer num = map.get(word);
if(num==null){
map.put(word, 1);
}else{
map.put(word, num+1);
}
//i回退到最后匹配的坐標(biāo)
i=idx;
//從root的開始匹配
currentNode = root;
//清空匹配到的詞
word = null;
//清空當(dāng)前路徑匹配到的所有字
sb = new StringBuilder();
}
}
//已匹配到最后一位
if(i==arr.length-1){
if(word!=null && word.length()>0){
Integer num = map.get(word);
if(num==null){
map.put(word, 1);
}else{
map.put(word, num+1);
}
}
}
}
return map;
}
}
public static void main(String[] args) {
TrieTree tree = new TrieTree();
tree.insert("北京");
tree.insert("海淀區(qū)");
tree.insert("中國");
tree.insert("中國人民");
tree.insert("中關(guān)村");
String word = "中國";
//查找該詞是否存在 Trid Tree 中
boolean flag = tree.search(word);
if(flag){
System.out.println("Trie Tree 中已經(jīng)存在【"+word+"】");
}else{
System.out.println("Trie Tree 不包含【"+word+"】");
}
//分詞
Map<String, Integer> map = tree.tokenizer("中國人民颤陶，中國首都是北京，中關(guān)村在海淀區(qū),中國北京天安門陷遮。中國人");
for (Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey()+":"+entry.getValue());
}
}
}
想了解更多精彩內(nèi)容請(qǐng)關(guān)注我的公眾號(hào)
