搜索引擎技术在码农眼里一直是比较高大上,其中文分词是中文自然语言处理领域的基础研究,也是中文搜索引擎的核心模块之一,现在我们来用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. using namespace std;
5. set<string> g_setWordDictionary;
6. int construct()
7. {
8. g_setWordDictionary.insert("中国");
9. g_setWordDictionary.insert("中国人");
10. g_setWordDictionary.insert("纽约");
11. g_setWordDictionary.insert("北京");
12. }
13. bool match(string &word)
14. {
15. set<string>::iterator itor = g_setWordDictionary.find(word);
16. if (itor == g_setWordDictionary.end())
17. {
18. return false;
19. }
20. return true;
21. }
22. void forward_maximum_matching(string content, set<string> &keywords)
23. {
24. #define MAX_LEN 12 //词库中最长词语(utf-8一个汉字3个字节)
25. #define MIN_LEN 3 //单字(原理同上)
26. int len = content.length();
27. int right_len = len;
28. int start_pos = 0;
29. bool ret = false;
30. string kw_value = "";
31. int kw_len = 0;
32. int kw_pos = 0;
33. //单字或空串
34. while (right_len > MIN_LEN)
35. {
36. //语句大于词库中最长词语
37. if (right_len >= MAX_LEN)
38. {
39. kw_value = content.substr(start_pos, MAX_LEN);
40. }
41. //语句小于词库中最长词语
42. else
43. {
44. kw_value = content.substr(start_pos, right_len);
45. }
46. //词库匹配
47. ret = match(kw_value);
48. kw_len = kw_value.length();
49. kw_pos = 0;
50. while (!ret && kw_len > 2*MIN_LEN)
51. {
52. //去掉候选词右边一个汉字
53. kw_len -= MIN_LEN;
54. kw_value = kw_value.substr(kw_pos, kw_len);
55. //继续匹配
56. ret = match(kw_value);
57. }
58. //匹配到词
59. if (ret)
60. {
61. keywords.insert(kw_value);
62. //从语句中去掉匹配到的词
63. start_pos += kw_len;
64. right_len = len - start_pos;
65. }
66. //未匹配到词，下移一个字
67. else
68. {
69. start_pos += MIN_LEN;
70. right_len = len - start_pos;
71. }
72. }//while (right_len > MIN_LEN)
73. }
74. int main()
75. {
76. //构造词库
77. construct();
78. //切分词库
79. string content = "我是中国人，我是来自中国北京的中国人，在纽约工作";
80. set<string> keywords;
81. forward_maximum_matching(content, keywords);
82. set<string>::iterator itor;
83. //输出分词
84. for (itor=keywords.begin(); itor!=keywords.end(); ++itor)
85. {
86. printf("result: %sn", (*itor).c_str());
87. } //phpfensi.com
88. return 0;
89. }