中文分词一直都是中文自然语言处理领域的基础研究。目前,网络上流行的很多中文分词软件都可以在付出较少的代价的同时,具备较高的正确率。而且不少中文分词软件支持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源代码如下:
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结构的空间代价?
下面是我实现的基于Trie词典结构的正向最大匹配算法的源代码包和分词词表,可供大家学习下载。但绝对不允许任何商业性质的传播,违者必究。
分享到:
相关推荐
这是我自己写的最经典的分词算法:正向最大匹配算法 ,有兴趣的朋友可以拿去看看
MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配算法。 本程序还可以从我的github上面下载:https://github.com/Zehua-Zeng/Maximum-Matching-Algorithm
中文分词一直都是中文自然语言处理领域的基础研究。目前,网络上流行的很多中文分词软件都可以在付出较少的代价的同时...MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配算法。
分词匹配算法:正向最大匹配和反向最大匹配
运用正向最大匹配算法进行分析,同时也实现了逆向最大匹配,内有分词词典。
Java实现分词(正向最大匹配和逆向最大匹配)两种方法实现
里面包含完整代码,有词典,解压后是vs2017的工程文件,可直接运用测试。
perl 写的正向最大匹配分词模块。 # #正向最大分词 #eg: my $seg = new Segmenter($list); # my $list_arrref = $seg->segment($line); #
中文分词应用很广泛,网上也有很多开源项目,下面这篇文章主要给大家介绍了关于java中文分词之正向最大匹配法的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考借鉴,下面随着小编来一起学习学习吧。
基于分词的正向最大匹配和反向最大匹配算法 字典和算法都在代码中
使用正向最大匹配FMM分词 以及逆向最大匹配BMM分词 但不是同时使用
本程序是北京师范大学学生根据一个中文字库对所给的文章进行分词。...采用的算法是正向最大匹配算法和反向最大匹配算法。主要实现屏幕分词和文件分词两项功能。因为对毕业设计有所帮助,所以我要分高一点哈~勿怪偶~
在一个已经语料库的基础上,进行词频统计,然后根据统计的词用正向和反向最大匹配算法进行中文分词。
在正向最大匹配的基础上增加一个交集型歧义字段处理模块一次来提高分词效率
MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了反向最大匹配算法。 本程序还可以从我的github上面下载:https://github.com/Zehua-Zeng/Reverse-Maximum-Matching-Algorithm
读取词表,按照最大正向匹配法给中文分词。然后么,大家都懂的。只是一个课程练习。大家不要太当真
正向最大匹配算法
分别使用了正向最大匹配算法和KNN算法。分词速度平均153295词/秒,189100字符/秒。文本分类使用tf-idf计算单词权重进行特征选择,我测试时选择前100个特征词,根据k的不同取值,分类的准确度平均为75%。