Trie Tree 实现中文分词器

前言

继上一篇HashMap实现中文分词器后，对Trie Tree的好奇，又使用Trie Tree实现了下中文分词器。效率比HashMap实现的分词器更高。

Trie Tree 简介

Trie Tree，又称单词字典树、查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

性质

它有3个基本性质：
1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

Trie Tree 结构

Trie Tree分词原理：

(1) 从根结点开始一次搜索，比如搜索【北京】；
(2) 取得要查找关键词的第一个字符【北】，并根据该字符选择对应的子树并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字符【京】,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在直到判断树节点的isEnd节点为true则查找结束（最小匹配原则），然后发现【京】isEnd=true，则结束查找。

示例

下面用java简单实现

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 {//记录当前节点的字char c;//判断该字是否词语的末尾，如果是则为falseboolean isEnd;//子节点List childList;public Node(char c) {super();this.c = c;isEnd = false;childList = new LinkedList();}//查找当前子节点中是否保护c的节点public Node findNode(char c){for(Node node : childList){if(node.c == c){return node;}}return null;}}static class TrieTree{Node root = new Node(' ');//构建Trie Treepublic void insert(String words){char[] arr = words.toCharArray();Node currentNode = root;for (char c : arr) {Node node = currentNode.findNode(c);//如果不存在该节点则添加if(node == null){Node n = new Node(c);currentNode.childList.add(n);currentNode = n;}else{currentNode = node;}}//在词的最后一个字节点标记为truecurrentNode.isEnd = true;}//判断Trie Tree中是否包含该词public boolean search(String word){char[] arr = word.toCharArray();Node currentNode = root;for (int i=0; iif(n != null){currentNode = n;//判断是否为词的尾节点节点if(n.isEnd){if(n.c == arr[arr.length-1]){return true;}}}}return false;}//最大匹配优先原则public Map tokenizer(String words){char[] arr = words.toCharArray();Node currentNode = root;Map map = new HashMap();//记录Trie Tree 从root开始匹配的所有字StringBuilder sb = new StringBuilder();;//最后一次匹配到的词，最大匹配原则，可能会匹配到多个字，以最长的那个为准String word="";//记录记录最后一次匹配坐标int idx = 0;for (int i=0; iif(n != null){sb.append(n.c);currentNode = n;//匹配到词if(n.isEnd){//记录最后一次匹配的词word = sb.toString();//记录最后一次匹配坐标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回退到最后匹配的坐标i=idx;//从root的开始匹配currentNode = root;//清空匹配到的词word = null;//清空当前路径匹配到的所有字sb = new StringBuilder();}}if(i==arr.length-2){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("海淀区");tree.insert("中国");tree.insert("中国人民");tree.insert("中关村");String word = "中国";//查找该词是否存在 Trid Tree 中boolean flag = tree.search(word);if(flag){System.out.println("Trie Tree 中已经存在【"+word+"】");}else{System.out.println("Trie Tree 不包含【"+word+"】");}//分词Map map = tree.tokenizer("中国人民，中国首都是北京，中关村在海淀区,中国北京天安门。中国人");for (Entry entry : map.entrySet()) {System.out.println(entry.getKey()+":"+entry.getValue());}}
}

想了解更多精彩内容请关注我的公众号

本人简书blog地址：http://www.jianshu.com/u/1f0067e24ff8    
点击这里快速进入简书

GIT地址：http://git.oschina.net/brucekankan/
点击这里快速进入GIT

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！