CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

经过了n长时间.有时候想放弃有时候.想继续断断续续的.终于写完了CQ分词的基本原型.目前实现了正向最大匹配.和正向最好匹配.全文全匹配取词等功能.希望大家能支持我.我一定会写出更好的分词的.

分词的速度.大家自己试去吧.我这里是300w字/s.估计我电脑好点吧嘿嘿

传统的分词方式有:
 整词二分法
结构：首字散列表、词索引表、词典正文
优点：数据结构简单、占用空间小。
缺点：全词匹配，效率相对来说不高。
 Tire索引树法
结构：首字散列表、Trie索引树结点
优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。
缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。
 逐字二分法
结构：同整词二分法
优点：查询采用逐字匹配，提高了一定的匹配效率。
缺点：由于词典结构未改变，效率的提高有限。

然后我们先了解一下双数组tire树.以下是双数组tire树的简介.

	本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。
	Trie树的空间复杂度为O(n)
	缺点：数据结构复杂，查询效率较低
	为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-Array Trie)
	两个数组：base[]、check[]
	base：数组中的每一个元素相当于trie树的一个节点。
	check：相当于当前状态的前一状态。
	对于从状态s到状态t的一个转移，必须满足：
		check[base[s]+c]=s
		base[s]+c=t
	其中c是输入变量。
	基本思想：
		对6763个常用汉字根据其内码相应的赋予从1－6763的序列码，放入base[1]-base[6763]。若首字序列码是i的词语有n个，设所有第二个字的序列码依次为a1,a2,a3,an,则这n个第二字在base数组中的位置依次为 base[i]+a1,base[i]+a2,…base[i]+an。依次类推第三字、第四字……第k字的位置。
		如果base[i]和check[i]同为0，表示该位置为空；	如果base[i]为负值，表示该状态为一个词语。
	数组构造
		对于每一个汉字，要确定其base[]值，使得对于所有以该汉字开头的词语都能在数组中放下。即要找到一个k=base[i]，使得base[k+a1],check[k+a1],base[k+a2],check[k+a2],…base[k+an],check[k+an]均为0，a1,a2…an是以i开头的词的第二字序列码。

基于双数组Trie的词典查询算法

	查询
	t := base[s] + c;
if check[t] = s then 
		next state := t 
	else fail 
	endif 

双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的


好了不说了这些都是抄来的.
如果有兴趣的朋友可以和我联系相互学习.
下面我来介绍下CQ分词的大体实现.至于词典的实现比较复杂在这里不多说了.如有需要我会放出源码的

目前实现的接口有两个

package love.cq.splitWord;

public interface GetWords {
	/**
	 * 正向最大取词
	 * @param str 传入的需要取词的句子
	 * @return
	 */
	public String maxFrontWords() ;
	/**
	 * 正向最小匹配取词
	 * @param str 传入的需要取词的句子
	 * @return 返还取得的一个词
	 */
	public String minFrontWords() ;
	/**
	 * 全文全词全匹配
	 * @param str 传入的需要分词的句子
	 * @return 返还分完词后的句子
	 */
	public String allWords() ;
}

这个接口负责从文章中取词.
比如”中华人民共和国万岁”
在allWords()方法取得的结果应该是.全文全匹配

中华
中华人民
中华人民共和国
华人
人民
人民共和国
共和
共和国
万岁

在maxFrontWords()方法取得的结果应该是.正向最大匹配

中华人民共和国
万岁

在minFrontWords()方法取得的结果应该是.正向最小匹配

中华
人民
共和
万岁

还有一个简单的文本分割.现在比较乱.我尽快生成api就好多了

package love.cq.splitWord;

public interface SplitWord {
	/**
	 * 正向最大标记
	 * @param str 传入的需要分词的句子
	 * @return
	 */
	public String tagMaxFront(String str) ;
	/**
	 * 正向最小匹配标记
	 * @param str 传入的需要分词的句子
	 * @return 返还分完词后的句子
	 */
	public String tagMinFront(String str) ;
	

}

对字符串进行简单的标记, 复杂的根据词性的可以自己扩展.

注意:

其中package love.cq.demo;包中存放了我做的两个简单的demo
大家有什么建议和意见就联系我吧..
在这里先放出代码鼓励鼓励呵呵..

联系方式
msn:[e-mail]
Qq:5144694

还有特别鸣谢我的女朋友芹菜.没有她的帮助我肯定写不了这么快..
各位这个是要给我女朋友看的.朋友们拍砖时手下留情啊.在这里拜谢了!

评论

15 楼 fyland 2010-05-31  

如果是用C写的就好了

14 楼 ThinkingInAll 2009-08-06  

加油

如果能加上词性标注就更好了

希望能增加准确率和召回率以及性能

13 楼 ansjsun 2009-08-01  

viMory 写道

努力，爱的力量真大啊，呵呵，

严重感谢..cq生日快乐
现在已经和lucence整合了。并且能分出。英文。数字。。正在做。。用户自定义词典。。和分量词。。
等这些完了出个版本。字典也放出来。。然后做姓名和。机构名称的识别。。新词的发现（算法已经写了有思路了呵呵）
报告完毕
尽快啦呵呵。。。

12 楼 viMory 2009-08-01  

努力，爱的力量真大啊，呵呵，

11 楼 ansjsun 2009-07-26  

visualcatsharp 写道

精确度和召回率太差了。
n百w/s的分词速度不能作为卖点，在我们这些应用中，n10w/s已经完全满足需要了。

如果是给搜索引擎和关键字标记来用的话..我觉得..多和快事重要的..不过还是谢谢你的意见..最近公司有些变动..没心情弄这个了..等好点了我会努力让他健全的...等我的第二版吧..不会让大家失望的

10 楼 visualcatsharp 2009-07-23  

精确度和召回率太差了。
n百w/s的分词速度不能作为卖点，在我们这些应用中，n10w/s已经完全满足需要了。

9 楼 ansjsun 2009-07-22  

ansjsun 写道

HuangSui.cn 写道

请问下LZ，怎么添加新词，用户自定义词典
还有就是array.dic的生成的效率问题，可不可以放出源码

生成效率也是有问题的...没人关注..放源码的心都没了..
我尽快..整合到lucence中..在对分词和自定义词典做一些优化后方出代码谢谢你的关注

30w左右大的数组..3个.两个int一个byte...大约5m左右吧...

8 楼 ansjsun 2009-07-22  

HuangSui.cn 写道

请问下LZ，怎么添加新词，用户自定义词典
还有就是array.dic的生成的效率问题，可不可以放出源码

生成效率也是有问题的...没人关注..放源码的心都没了..
我尽快..整合到lucence中..在对分词和自定义词典做一些优化后方出代码谢谢你的关注

7 楼 jenlp520 2009-07-15  

2W个关键词的tree占用多大内存?

6 楼 HuangSui.cn 2009-07-13  

请问下LZ，怎么添加新词，用户自定义词典
还有就是array.dic的生成的效率问题，可不可以放出源码

5 楼 ansjsun 2009-07-05  

fxsjy 写道

在你的代码中好像没有看到library/charHash.dic是怎么生成的，有了构造程序，用户才能自行添加新词。


PS:
如果你把CQ分词作成一个google code或sf.net上的正规开源项目，相信会引起更多人的注意。

charHash.dic是生成不是问题..直接就是字符编码的hash...排序了下..只是为了缩小字典的大小而已..
至于.array.dic生成比较麻烦..我看到都没人关注..下一步放源码的心都没有了哎..我打算进一步和另一个分词做总合..用户就能简单的自定义词典了...速度上难免会有下降...和更精确地分词..谢谢楼上的关注

4 楼 fxsjy 2009-07-02  

在你的代码中好像没有看到library/charHash.dic是怎么生成的，有了构造程序，用户才能自行添加新词。


PS:
如果你把CQ分词作成一个google code或sf.net上的正规开源项目，相信会引起更多人的注意。

3 楼 ansjsun 2009-07-01  

在做全文全匹配测试的时候结果如下..大家看速度吧...哈哈

中华人名共和国万岁数
10w 32ms
100w 265ms
1000w 2672ms

你好我叫孙建凑够十个
1000w 1203ms

2 楼 ansjsun 2009-07-01  

wwwwzk 写道

研究下先！

研究吧..嘿嘿

1 楼 wwwwzk 2009-07-01  

研究下先！