搜索引擎技術在碼農眼里一直是比較高大上,其中文分詞是中文自然語言處理領域的基礎研究,也是中文搜索引擎的核心模塊之一,現在我們來用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.  
7. int construct() 
8. { 
9.     g_setWordDictionary.insert("中國"); 
10.     g_setWordDictionary.insert("中國人"); 
11.     g_setWordDictionary.insert("紐約"); 
12.     g_setWordDictionary.insert("北京"); 
13. } 
14.  
15. bool match(string &word) 
16. { 
17.     set<string>::iterator itor = g_setWordDictionary.find(word); 
18.     if (itor == g_setWordDictionary.end()) 
19.     { 
20.         return false; 
21.     } 
22.  
23.     return true; 
24. } 
25.  
26. void forward_maximum_matching(string content, set<string> &keywords)     
27. { 
28.     #define MAX_LEN 12      //詞庫中最長詞語(utf-8一個漢字3個字節) 
29.     #define MIN_LEN 3       //單字(原理同上) 
30.     int len = content.length(); 
31.     int right_len = len; 
32.     int start_pos = 0; 
33.     bool ret = false; 
34.     string kw_value = ""; 
35.     int kw_len = 0; 
36.     int kw_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.         } 
50.  
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.         } 
63.  
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. } 
80.  
81. int main() 
82. { 
83.     //構造詞庫 
84.     construct(); 
85.  
86.     //切分詞庫 
87.     string content = "我是中國人，我是來自中國北京的中國人，在紐約工作"; 
88.     set<string> keywords; 
89.     forward_maximum_matching(content, keywords); 
90.     set<string>::iterator itor; 
91.  
92.     //輸出分詞 
93.     for (itor=keywords.begin(); itor!=keywords.end(); ++itor) 
94.     { 
95.         printf("result: %sn", (*itor).c_str()); 
96.     }  //Vevb.com 
97.  
98.     return 0; 
99. }