正向最大匹配中文分词算法

中文分词一直都是中文自然语言处理领域的基础研究。目前，网络上流行的很多中文分词软件都可以在付出较少的代价的同时，具备较高的正确率。而且不少中文分词软件支持Lucene扩展。但不管实现如何，目前而言的分词系统绝大多数都是基于中文词典的匹配算法。

在这里我想介绍一下中文分词的一个最基础算法：最大匹配算法 (Maximum Matching，以下简称MM算法) 。MM算法有两种：一种正向最大匹配，一种逆向最大匹配。

● 算法思想

正向最大匹配算法：从左到右将待分词文本中的几个连续字符与词表匹配，如果匹配上，则切分出一个词。但这里有一个问题：要做到最大匹配，并不是第一次匹配到就可以切分的。我们来举个例子：

待分词文本： content[]={"中"，"华"，"民"，"族"，"从"，"此"，"站"，"起"，"来"，"了"，"。"}

词表： dict[]={"中华"， "中华民族" ， "从此"，"站起来"}

(1) 从content[1]开始，当扫描到content[2]的时候，发现"中华"已经在词表dict[]中了。但还不能切分出来，因为我们不知道后面的词语能不能组成更长的词(最大匹配)。

(2) 继续扫描content[3]，发现"中华民"并不是dict[]中的词。但是我们还不能确定是否前面找到的"中华"已经是最大的词了。因为"中华民"是dict[2]的前缀。

(3) 扫描content[4]，发现"中华民族"是dict[]中的词。继续扫描下去：

(4) 当扫描content[5]的时候，发现"中华民族从"并不是词表中的词，也不是词的前缀。因此可以切分出前面最大的词——"中华民族"。

由此可见，最大匹配出的词必须保证下一个扫描不是词表中的词或词的前缀才可以结束。

● 算法实现

词表的内存表示：很显然，匹配过程中是需要找词前缀的，因此我们不能将词表简单的存储为Hash结构。在这里我们考虑一种高效的字符串前缀处理结构——Trie树《Trie Tree 串集合查找》。这种结构使得查找每一个词的时间复杂度为O(word.length)，而且可以很方便的判断是否匹配成功或匹配到了字符串的前缀。

下图是我们建立的Trie结构词典的部分，(词语例子："中华"，"中华名族"，"中间"，"感召"，"感召力"，"感受")。

(1) 每个结点都是词语中的一个汉字。

(2) 结点中的指针指向了该汉字在某一个词中的下一个汉字。这些指针存放在以汉字为key的hash结构中。

(3) 结点中的"#"表示当前结点中的汉字是从根结点到该汉字结点所组成的词的最后一个字。

TrieNode源代码如下：

Java代码

import java.util.HashMap;
/**
* 构建内存词典的Trie树结点
*
* @author single(宋乐)
* @version 1.01, 10/11/2009
*/
public class TrieNode {
/**结点关键字，其值为中文词中的一个字*/
public char key=(char)0;
/**如果该字在词语的末尾，则bound=true*/
public boolean bound=false;
/**指向下一个结点的指针结构，用来存放当前字在词中的下一个字的位置*/
public HashMap<Character,TrieNode> childs=new HashMap<Character,TrieNode>();
public TrieNode(){
}
public TrieNode(char k){
this.key=k;
}
}

这套分词代码的优点是：

(1) 分词效率高。纯内存分词速度大约240.6ms/M，算上IO读取时间平均1.6s/M。测试环境：Pentium(R) 4 CPU 3.06GHZ、1G内存。

(2) 传统的最大匹配算法需要实现确定一个切分的最大长度maxLen。如果maxLen过大，则大大影响分词效率。而且超过maxLen的词语将无法分出来。但本算法不需要设置maxLen。只要词表中有的词，不管多长，都能够切分。

(3) 对非汉字的未登录词具备一定的切分能力。比如英文单词[happy, steven]，产品型号[Nokia-7320]，网址[http://www.sina.com]等。

缺点也很明显：

(1) 暂时无词性标注功能，对中文汉字的未登录词无法识别，比如某个人名。

(2) 内存占用稍大，目前词表为86725个词。如果继续扩展词表，很有可能内存Trie树将非常庞大。

代码的进一步优化方案：

(1) 想在内存占用空间上降低代价。实际上Trie树主要的空间消耗在每个结点的指针HashMap上。我使用的是JDK中的HashMap，其加载因子为 loadFactor= 0.75，初始化空间大小为DEFAULT_INITIAL_CAPACITY= 16。每次存储数据量超过 loadFactor*DEFAULT_INITIAL_CAPACITY的时候，整个Map空间将翻倍。因此会照成一定的空间浪费。

但目前还没有想到很好的办法，即能够随机定位到下一个结点的指针，又降低Hash结构的空间代价？

转自：http://hxraid.iteye.com/blog/667134

【串和序列处理 3】Trie Tree 串集合查找

文章分类:综合技术

Trie 树， 又称字典树，单词查找树。它来源于retrieval(检索)中取中间四个字符构成(读音同try)。用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。

Trie 有三种结构：标准trie (standard trie)、压缩trie、后缀trie(suffix trie) 。最后一种将在《字符串处理4：后缀树》中详细讲，这里只将前两种。

1. 标准Trie (standard trie)

标准 Trie树的结构 ：所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了存在于串集合中的所有公共前缀。假如有这样一个字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的标准Trie树如下图：

上图（蓝色圆形结点为内部结点，红色方形结点为外部结点），我们可以很清楚的看到字符串集合X构造的Trie树结构。其中从根结点到红色方框叶子节点所经历的所有字符组成的串就是字符串集合X中的一个串。

注意这里有一个问题：如果X集合中有一个串是另一个串的前缀呢？比如，X集合中加入串bi。那么上图的Trie树在绿色箭头所指的内部结点i 就应该也标记成红色方形结点。这样话，一棵树的枝干上将出现两个连续的叶子结点(这是不合常理的)。

也就是说字符串集合X中不存在一个串是另外一个串的前缀。如何满足这个要求呢？我们可以在X中的每个串后面加入一个特殊字符$(这个字符将不会出现在字母表中)。这样，集合X{bear$、bell$、.... bi$、bid$}一定会满足这个要求。

总结：一个存储长度为n，来自大小为d的字母表中s个串的集合X的标准trie具有性质如下：

(1) 树中每个内部结点至多有d个子结点。

(2) 树有s个外部结点。

(3) 树的高度等于X中最长串的长度。

(4) 树中的结点数为O(n)。

标准 Trie树的查找

对于英文单词的查找，我们完全可以在内部结点中建立26个元素组成的指针数组。如果要查找a，只需要在内部节点的指针数组中找第0个指针即可(b=第1个指针，随机定位)。时间复杂度为O(1)。

查找过程：假如我们要在上面那棵Trie中查找字符串bull (b-u-l-l)。

(1) 在root结点中查找第('b'-'a'=1)号孩子指针，发现该指针不为空，则定位到第1号孩子结点处——b结点。

(2) 在b结点中查找第('u'-'a'=20)号孩子指针，发现该指针不为空，则定位到第20号孩子结点处——u结点。

(3) ... 一直查找到叶子结点出现特殊字符'$'位置，表示找到了bull字符串

如果在查找过程中终止于内部结点，则表示没有找到待查找字符串。

效率：对于有n个英文字母的串来说，在内部结点中定位指针所需要花费O(d)时间，d为字母表的大小，英文为26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式，因此时间复杂度降为了O(1)。但是如果是中文字，下面在实际应用中会提到。因此我们在这里还是用O(d)。查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为O(d*n)。

但是，当查找集合X中所有字符串两两都不共享前缀时，trie中出现最坏情况。除根之外，所有内部结点都自由一个子结点。此时的查找时间复杂度蜕化为O(d*(n^2))

标准 Trie树的Java代码实现：

Java代码

package net.hr.algorithm.stroper;
import java.util.ArrayList;
enum NodeKind{LN,BN};
/**
* Trie结点
*/
class TrieNode{
char key;
TrieNode[] points=null;
NodeKind kind=null;
}
/**
* Trie叶子结点
*/
class LeafNode extends TrieNode{
LeafNode(char k){
super.key=k;
super.kind=NodeKind.LN;
}
}
/**
* Trie内部结点
*/
class BranchNode extends TrieNode{
BranchNode(char k){
super.key=k;
super.kind=NodeKind.BN;
super.points=new TrieNode[27];
}
}
/**
* Trie树
* @author heartraid
*/
public class StandardTrie {
private TrieNode root=new BranchNode(' ');
/**
* 想Tire中插入字符串
*/
public void insert(String word){
//System.out.println("插入字符串："+word);
//从根结点出发
TrieNode curNode=root;
//为了满足字符串集合X中不存在一个串是另外一个串的前缀
word=word+"$";
//获取每个字符
char[] chars=word.toCharArray();
//插入
for(int i=0;i<chars.length;i++){
//System.out.println(" 插入"+chars[i]);
if(chars[i]=='$'){
curNode.points[26]=new LeafNode('$');
// System.out.println(" 插入完毕,使当前结点"+curNode.key+"的第26孩子指针指向字符：$");
}
else{
int pSize=chars[i]-'a';
if(curNode.points[pSize]==null){
curNode.points[pSize]=new BranchNode(chars[i]);
// System.out.println(" 使当前结点"+curNode.key+"的第"+pSize+"孩子指针指向字符: "+chars[i]);
curNode=curNode.points[pSize];
}
else{
// System.out.println(" 不插入，找到当前结点"+curNode.key+"的第"+pSize+"孩子指针已经指向字符: "+chars[i]);
curNode=curNode.points[pSize];
}
}
}
}
/**
* Trie的字符串全字匹配
*/
public boolean fullMatch(String word){
//System.out.print("查找字符串："+word+"/n查找路径：");
//从根结点出发
TrieNode curNode=root;
//获取每个字符
char[] chars=word.toCharArray();
for(int i=0;i<chars.length;i++){
if(curNode.key=='$'){
System.out.println('&');
// System.out.println(" 【成功】");
return true;
}else{
System.out.print(chars[i]+" -> ");
int pSize=chars[i]-'a';
if(curNode.points[pSize]==null){
// System.out.println(" 【失败】");
return false;
}else{
curNode=curNode.points[pSize];
}
}
}
// System.out.println(" 【失败】");
return false;
}
/**
* 先根遍历Tire树
*/
private void preRootTraverse(TrieNode curNode){
if(curNode!=null){
System.out.print(curNode.key+" ");
if(curNode.kind==NodeKind.BN)
for(TrieNode childNode:curNode.points)
preRootTraverse(childNode);
}
}
/**
* 得到Trie根结点
*/
public TrieNode getRoot(){
return this.root;
}
/**
* 测试
*/
public static void main(String[] args) {
StandardTrie trie=new StandardTrie();
trie.insert("bear");
trie.insert("bell");
trie.insert("bid");
trie.insert("bull");
trie.insert("buy");
trie.insert("sell");
trie.insert("stock");
trie.insert("stop");
trie.preRootTraverse(trie.getRoot());
trie.fullMatch("stoops");
}
}