C语言实现搜索引擎技术之中文分词

搜索引擎技术在码农眼里一直是比较高大上,其中文分词是中文自然语言处理领域的基础研究,也是中文搜索引擎的核心模块之一,现在我们来用C语言简单实现一下中文搜索引擎中文分词.

目前而言的分词系统绝大多数都是基于中文词典的匹配算法,其中,最为常见的是最大匹配算法(Maximum Matching,以下简称MM算法),而MM算法有三种:一种正向最大匹配、一种逆向最大匹配和双向匹配,本文以正向最大匹配算法为例介绍其基本思想和实现.

一、基本思想

(1)假设词典中最长的词语字数为w(一般设置为8个字符,即4个汉字).

(2)判断带分词语句长度是否大于w个字,如果大于w则跳到(3),如果小于w则跳到(6).

(3）取待分词语句的前w个字。

(4）在词典中查找w,如果存在,则从语句中去掉w,从语句中w后的词开始重复上面过程.

(5）如果不存在,就去掉这w个字的最后一个字.

(6）检查是否是单字或者空,如果是,则退出.

(7）如果不是,则继续判断词库中是否存在这个词,如此反复循环,直到输出一个词.

(8）继续取短语的前w个字反复循环,这样就可以将一个语句分成词语的组合了.

二、简单实现,代码如下:

1. #include<stdio.h>
2. #include<string>
3. #include<set>
4. usingnamespacestd;
5. set<string>g_setWordDictionary;
7. intconstruct()
8. {
9. g_setWordDictionary.insert("中国");
10. g_setWordDictionary.insert("中国人");
11. g_setWordDictionary.insert("纽约");
12. g_setWordDictionary.insert("北京");
13. }
15. boolmatch(string&word)
16. {
17. set<string>::iteratoritor=g_setWordDictionary.find(word);
18. if(itor==g_setWordDictionary.end())
19. {
20. returnfalse;
21. }
23. returntrue;
24. }
26. voidforward_maximum_matching(stringcontent,set<string>&keywords)
27. {
28. #defineMAX_LEN12//词库中最长词语(utf-8一个汉字3个字节)
29. #defineMIN_LEN3//单字(原理同上)
30. intlen=content.length();
31. intright_len=len;
32. intstart_pos=0;
33. boolret=false;
34. stringkw_value="";
35. intkw_len=0;
36. intkw_pos=0;
37. //单字或空串
38. while(right_len>MIN_LEN)
39. {
40. //语句大于词库中最长词语
41. if(right_len>=MAX_LEN)
42. {
43. kw_value=content.substr(start_pos,MAX_LEN);
44. }
45. //语句小于词库中最长词语
46. else
47. {
48. kw_value=content.substr(start_pos,right_len);
49. }
51. //词库匹配
52. ret=match(kw_value);
53. kw_len=kw_value.length();
54. kw_pos=0;
55. while(!ret&&kw_len>2*MIN_LEN)
56. {
57. //去掉候选词右边一个汉字
58. kw_len-=MIN_LEN;
59. kw_value=kw_value.substr(kw_pos,kw_len);
60. //继续匹配
61. ret=match(kw_value);
62. }
64. //匹配到词
65. if(ret)
66. {
67. keywords.insert(kw_value);
68. //从语句中去掉匹配到的词
69. start_pos+=kw_len;
70. right_len=len-start_pos;
71. }
72. //未匹配到词，下移一个字
73. else
74. {
75. start_pos+=MIN_LEN;
76. right_len=len-start_pos;
77. }
78. }//while(right_len>MIN_LEN)
79. }
81. intmain()
82. {
83. //构造词库
84. construct();
86. //切分词库
87. stringcontent="我是中国人，我是来自中国北京的中国人，在纽约工作";
88. set<string>keywords;
89. forward_maximum_matching(content,keywords);
90. set<string>::iteratoritor;
92. //输出分词
93. for(itor=keywords.begin();itor!=keywords.end();++itor)
94. {
95. printf("result:%sn",(*itor).c_str());
96. }//phpfensi.com
98. return0;
99. }