前言
目前做分词比较流行的是用深度学习来做，比如用循环神经网络和条件随机场，也有直接用条件随机场或隐马尔科夫模型的。前面也实现过上面几种，效果挺不错，基于隐马尔科夫模型的差一点，条件随机场的效果较好，而加入深度学习的效果最好。
而最最传统的分词做法很多都是基于字典的，然后通过最大匹配法匹配，效果比较一般。效果虽然一般，但我们还是看下怎么实现的吧。
Trie树结构
Trie 是一种搜索树，它的 key 都为字符串，通过 key 可以找到 value。能做到高效查询和插入，时间复杂度为O(k)，缺点是耗内存。它的核心思想就是减少没必要的字符比较，使查询高效率，即用空间换时间，再利用共同前缀来提高查询效率。
Trie树的根节点不包含字符，根节点到某节点的路径连起来的字符串为该节点对应的字符串，每个节点只包含一个字符，此外，任意节点的所有子节点的字符都不相同。
比如如下，将五个词语添加到Trie树中，最后的结构如图所示。
TrieTree tree = new TrieTree();
tree.put("美利坚");
tree.put("美丽");
tree.put("金币");
tree.put("金子");
tree.put("帝王");
Github
https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/segment/
效果
可以看到基于字典的分词效果是存在缺点的，需要用机器学习进一步优化。
DictSegment segment = new DictSegment();
System.out.println(segment.seg("我是中国人"));
System.out.println(segment.seg("人工智能是什么"));
System.out.println(segment.seg("北京互联网违法和不良信息举报中心"));
[我, 是, 中国人] [人工智能, 是, 什么] [北京, 互联网, 违法, 和不, 良, 信息, 举报中心]
简易实现
定义一个节点类代表Trie树节点，包含若干子节点、值和删除标记。getChild方法用于遍历该节点下的指定字符的子节点，allChildrenDeleted方法用于检测节点下的子节点是否已被删除了，setChild方法用于将子节点设置到某个节点上。
public class TrieNode {
private TrieNode[] children;
private String value;
private boolean deleted = false;
public TrieNode(String value) {
this.value = value == null ? null : value.intern();
}
public boolean isEmpty() {
return this.value == null && this.children == null;
}
public TrieNode[] getChildren() {
return children;
}
public TrieNode getChild(String word) {
if (children == null)
return null;
for (TrieNode c : children) {
if (c.getValue() == word.intern() && !c.deleted)
return c;
}
return null;
}
public boolean allChildrenDeleted() {
if (children == null)
return true;
for (TrieNode c : children) {
if (!c.deleted)
return false;
}
return true;
}
public void setChild(TrieNode child) {
if (children == null) {
children = new TrieNode[1];
children[0] = child;
} else {
TrieNode[] temp = children;
children = new TrieNode[temp.length + 1];
System.arraycopy(temp, 0, children, 0, temp.length);
children[children.length - 1] = child;
}
}
}
定义一个 TrieTree 类代表树对象，包含了树的根节点。put方法用于将字符串放到树结构中，需要先遍历检测是否已经有字符串前缀，没有则要创建对应的节点，然后添加到对应节点的子节点中。get和remove操作都需要针对树结构做处理，最终完成查询和删除，删除操作为了方便仅仅是设置下指定节点的删除标识。
public class TrieTree {
protected TrieNode root;
public TrieTree() {
this.root = new TrieNode(null);
}
public void put(String word) throws IllegalArgumentException {
if (word == null) {
throw new IllegalArgumentException();
}
TrieNode current = this.root;
for (String s : word.split("")) {
TrieNode child = current.getChild(s);
if (child == null) {
child = new TrieNode(s);
current.setChild(child);
}
current = child;
}
}
public TrieNode get(String word) throws IllegalArgumentException {
if (word == null) {
throw new IllegalArgumentException();
}
TrieNode current = this.root;
for (String s : word.split("")) {
TrieNode child = current.getChild(s);
if (child == null)
return null;
current = child;
}
return current;
}
public void remove(String word) {
if (word == null || word.length() <= 0) {
return;
}
for (int i = 0; i < word.length(); i++) {
String sub_word = word.substring(0, word.length() - i);
TrieNode current = this.root;
for (String s : sub_word.split("")) {
TrieNode child = current.getChild(s);
if (child != null && (child.getChildren() == null || child.allChildrenDeleted()))
child.setDeleted(true);
current = child;
}
}
}
}
seg为分词方法，它主要就是尝试进行最大字符串匹配，尽量匹配字典中最长词，其中查找是否存在字符串在teri树中查找。
public List<String> seg(String text) {
int flag = 0;
int delta = 1;
List<String> words = new ArrayList<String>();
while (flag + delta <= text.length()) {
String temp = text.substring(flag, flag + delta);
if (tree.get(temp) != null) {
if ((flag + delta) == text.length()) {
words.add(temp);
break;
}
delta++;
continue;
}
words.add(temp.substring(0, temp.length() - 1));
flag = flag + delta - 1;
delta = 1;
}
return words;
}
————-推荐阅读————
我的2017文章汇总——机器学习篇
我的2017文章汇总——Java及中间件
我的2017文章汇总——深度学习篇
我的2017文章汇总——JDK源码篇
我的2017文章汇总——自然语言处理篇
我的2017文章汇总——Java并发篇
跟我交流，向我提问：
公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等，可能有一款适合你的胃口。
为什么写《Tomcat内核设计剖析》
欢迎关注：