经过了n长时间.有时候想放弃有时候.想继续断断续续的.终于写完了CQ分词的基本原型.目前实现了正向最大匹配.和正向最好匹配.全文全匹配取词等功能.希望大家能支持我.我一定会写出更好的分词的. 分词的速度.大家自己试去吧.我这里是300w字/s.估计我电脑好点吧嘿嘿 传统的分词方式有:
整词二分法
结构：首字散列表、词索引表、词典正文
优点：数据结构简单、占用空间小。
缺点：全词匹配，效率相对来说不高。
Tire索引树法
结构：首字散列表、Trie索引树结点
优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。
缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。
逐字二分法
结构：同整词二分法
优点：查询采用逐字匹配，提高了一定的匹配效率。
缺点：由于词典结构未改变，效率的提高有限。 然后我们先了解一下双数组tire树.以下是双数组tire树的简介. Java代码
1. 本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。
2. Trie树的空间复杂度为O(n)
3. 缺点：数据结构复杂，查询效率较低
4. 为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-Array Trie)
5. 两个数组：base[]、check[]
6. base：数组中的每一个元素相当于trie树的一个节点。
7. check：相当于当前状态的前一状态。
8. 对于从状态s到状态t的一个转移，必须满足：
9. check[base[s]+c]=s
10. base[s]+c=t
11. 其中c是输入变量。
12. 基本思想：
13. 对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字的位置。
14. 如果base[i]和check[i]同为0，表示该位置为空； 如果base[i]为负值，表示该状态为一个词语。
15. 数组构造
16. 对于每一个汉字，要确定其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开头的词的第二字序列码。
本质是一个确定的有限状态自动机（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的词典查询算法 Java代码
1. 查询
2. t := base[s] + c;
3.if check[t] = s then
4. next state := t
5. else fail
6. endif
查询
t := base[s] + c;
if check[t] = s then
next state := t
else fail
endif 双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的
好了不说了这些都是抄来的.
如果有兴趣的朋友可以和我联系相互学习.
下面我来介绍下CQ分词的大体实现.至于词典的实现比较复杂在这里不多说了.如有需要我会放出源码的 目前实现的接口有两个 Java代码
1.package love.cq.splitWord;
2.
3.public interface GetWords {
4. /**
5. * 正向最大取词
6. * @param str 传入的需要取词的句子
7. * @return
8. */
9. public String maxFrontWords() ;
10. /**
11. * 正向最小匹配取词
12. * @param str 传入的需要取词的句子
13. * @return 返还取得的一个词
14. */
15. public String minFrontWords() ;
16. /**
17. * 全文全词全匹配
18. * @param str 传入的需要分词的句子
19. * @return 返还分完词后的句子
20. */
21. public String allWords() ;
22.}
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()方法取得的结果应该是.全文全匹配 Java代码
1.中华
2.中华人民
3.中华人民共和国
4.华人
5.人民
6.人民共和国
7.共和
8.共和国
9.万岁
中华
中华人民
中华人民共和国
华人
人民
人民共和国
共和
共和国
万岁在maxFrontWords()方法取得的结果应该是.正向最大匹配 Java代码
1.中华人民共和国
2.万岁
中华人民共和国
万岁
Java代码
1.
在minFrontWords()方法取得的结果应该是.正向最小匹配 Java代码
1.中华
2.人民
3.共和
4.万岁
中华
人民
共和
万岁
还有一个简单的文本分割.现在比较乱.我尽快生成api就好多了 Java代码
1.package love.cq.splitWord;
2.
3.public interface SplitWord {
4. /**
5. * 正向最大标记
6. * @param str 传入的需要分词的句子
7. * @return
8. */
9. public String tagMaxFront(String str) ;
10. /**
11. * 正向最小匹配标记
12. * @param str 传入的需要分词的句子
13. * @return 返还分完词后的句子
14. */
15. public String tagMinFront(String str) ;
16.
17.
18.}
package love.cq.splitWord;public interface SplitWord {
/**
* 正向最大标记
* @param str 传入的需要分词的句子
* @return
*/
public String tagMaxFront(String str) ;
/**
* 正向最小匹配标记
* @param str 传入的需要分词的句子
* @return 返还分完词后的句子
*/
public String tagMinFront(String str) ;
}对字符串进行简单的标记, 复杂的根据词性的可以自己扩展. 注意: Java代码
1.其中package love.cq.demo;包中存放了我做的两个简单的demo
2.大家有什么建议和意见就联系我吧..
3.在这里先放出代码鼓励鼓励呵呵..
4.
5.联系方式
6.msn:[email protected]
7.Qq:5144694
8.
9.还有特别鸣谢我的女朋友芹菜.没有她的帮助我肯定写不了这么快..
10.各位这个是要给我女朋友看的.朋友们拍砖时手下留情啊.在这里拜谢了!
其中package love.cq.demo;包中存放了我做的两个简单的demo
大家有什么建议和意见就联系我吧..
在这里先放出代码鼓励鼓励呵呵..联系方式
msn:[email protected]
Qq:5144694还有特别鸣谢我的女朋友芹菜.没有她的帮助我肯定写不了这么快..
各位这个是要给我女朋友看的.朋友们拍砖时手下留情啊.在这里拜谢了!
昏..附件没法传.....去我je里面下载吧哎http://ansjsun.javaeye.com/blog/417398
整词二分法
结构：首字散列表、词索引表、词典正文
优点：数据结构简单、占用空间小。
缺点：全词匹配，效率相对来说不高。
Tire索引树法
结构：首字散列表、Trie索引树结点
优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。
缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。
逐字二分法
结构：同整词二分法
优点：查询采用逐字匹配，提高了一定的匹配效率。
缺点：由于词典结构未改变，效率的提高有限。 然后我们先了解一下双数组tire树.以下是双数组tire树的简介. Java代码
1. 本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。
2. Trie树的空间复杂度为O(n)
3. 缺点：数据结构复杂，查询效率较低
4. 为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-Array Trie)
5. 两个数组：base[]、check[]
6. base：数组中的每一个元素相当于trie树的一个节点。
7. check：相当于当前状态的前一状态。
8. 对于从状态s到状态t的一个转移，必须满足：
9. check[base[s]+c]=s
10. base[s]+c=t
11. 其中c是输入变量。
12. 基本思想：
13. 对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字的位置。
14. 如果base[i]和check[i]同为0，表示该位置为空； 如果base[i]为负值，表示该状态为一个词语。
15. 数组构造
16. 对于每一个汉字，要确定其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开头的词的第二字序列码。
本质是一个确定的有限状态自动机（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的词典查询算法 Java代码
1. 查询
2. t := base[s] + c;
3.if check[t] = s then
4. next state := t
5. else fail
6. endif
查询
t := base[s] + c;
if check[t] = s then
next state := t
else fail
endif 双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的
好了不说了这些都是抄来的.
如果有兴趣的朋友可以和我联系相互学习.
下面我来介绍下CQ分词的大体实现.至于词典的实现比较复杂在这里不多说了.如有需要我会放出源码的 目前实现的接口有两个 Java代码
1.package love.cq.splitWord;
2.
3.public interface GetWords {
4. /**
5. * 正向最大取词
6. * @param str 传入的需要取词的句子
7. * @return
8. */
9. public String maxFrontWords() ;
10. /**
11. * 正向最小匹配取词
12. * @param str 传入的需要取词的句子
13. * @return 返还取得的一个词
14. */
15. public String minFrontWords() ;
16. /**
17. * 全文全词全匹配
18. * @param str 传入的需要分词的句子
19. * @return 返还分完词后的句子
20. */
21. public String allWords() ;
22.}
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()方法取得的结果应该是.全文全匹配 Java代码
1.中华
2.中华人民
3.中华人民共和国
4.华人
5.人民
6.人民共和国
7.共和
8.共和国
9.万岁
中华
中华人民
中华人民共和国
华人
人民
人民共和国
共和
共和国
万岁在maxFrontWords()方法取得的结果应该是.正向最大匹配 Java代码
1.中华人民共和国
2.万岁
中华人民共和国
万岁
Java代码
1.
在minFrontWords()方法取得的结果应该是.正向最小匹配 Java代码
1.中华
2.人民
3.共和
4.万岁
中华
人民
共和
万岁
还有一个简单的文本分割.现在比较乱.我尽快生成api就好多了 Java代码
1.package love.cq.splitWord;
2.
3.public interface SplitWord {
4. /**
5. * 正向最大标记
6. * @param str 传入的需要分词的句子
7. * @return
8. */
9. public String tagMaxFront(String str) ;
10. /**
11. * 正向最小匹配标记
12. * @param str 传入的需要分词的句子
13. * @return 返还分完词后的句子
14. */
15. public String tagMinFront(String str) ;
16.
17.
18.}
package love.cq.splitWord;public interface SplitWord {
/**
* 正向最大标记
* @param str 传入的需要分词的句子
* @return
*/
public String tagMaxFront(String str) ;
/**
* 正向最小匹配标记
* @param str 传入的需要分词的句子
* @return 返还分完词后的句子
*/
public String tagMinFront(String str) ;
}对字符串进行简单的标记, 复杂的根据词性的可以自己扩展. 注意: Java代码
1.其中package love.cq.demo;包中存放了我做的两个简单的demo
2.大家有什么建议和意见就联系我吧..
3.在这里先放出代码鼓励鼓励呵呵..
4.
5.联系方式
6.msn:[email protected]
7.Qq:5144694
8.
9.还有特别鸣谢我的女朋友芹菜.没有她的帮助我肯定写不了这么快..
10.各位这个是要给我女朋友看的.朋友们拍砖时手下留情啊.在这里拜谢了!
其中package love.cq.demo;包中存放了我做的两个简单的demo
大家有什么建议和意见就联系我吧..
在这里先放出代码鼓励鼓励呵呵..联系方式
msn:[email protected]
Qq:5144694还有特别鸣谢我的女朋友芹菜.没有她的帮助我肯定写不了这么快..
各位这个是要给我女朋友看的.朋友们拍砖时手下留情啊.在这里拜谢了!
昏..附件没法传.....去我je里面下载吧哎http://ansjsun.javaeye.com/blog/417398
解决方案 »
免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货