幾個月之前,在網路上找到了一個中文詞庫素材(幾百K),當時便想寫一個分詞程序了.我對漢語分詞沒有什麼研究,也就憑自己臆想而寫.若有相關方面專家,還請多給意見.
一、詞庫
詞庫大概有5萬多詞語(google能搜到,類似的詞庫都能用),我摘要如下:
地區 82
重要 81
新華社 80
技術 80
會議 80
自己 79
幹部 78
勞工 78
群眾 77
沒有 77
今天 76
同志 76
部門 75
加強 75
組織 75
第一列是詞,第二列是權重.我寫的這個分詞算法目前並未利用權重.
二、設計思路
算法簡要描述:
對一個字符串S,從前到後掃描,對掃描的每個字,從詞庫中尋找最長匹配.例如假設S="我是中華人民共和國公民",詞庫中有"中華人民共和國","中華","公民","人民","共和國"... ....等字。當掃描到"中"字,那麼從中字開始,向後分別取1,2,3,......個字("中","中華","中華人" ,"中華人民","中華人民共","中華人民共和","中華人民共和國",,"中華人民共和國公"),詞庫中的最長匹配字符串是"中華人民共和國",那麼就此切分開,掃描器推進到"公"字.
資料結構:
選擇什麼樣的資料結構對效能影響很大.我採用Hashtable _rootTable記錄詞庫.鍵值對為(鍵,插入次數).對每一個詞語,如果該詞語有N個字,則將該詞語的1,1~2,1~3,......1~N個字作為鍵,插入_rootTable中.而同一個鍵如果重複插入,則後面的值遞增.
三、程式
具體程式如下(程式中包含權重,插入次數等要素,目前的演算法並沒有利用這些.可以藉此寫出更有效的分詞演算法):
ChineseWordUnit.cs // struct--(詞語,權重)對
1 public struct ChineseWordUnit
2 {
3 private string _word;
4 private int _power;
5
6 /**//// <summary>
7 /// 中文詞語單元所對應的中文詞。
8 /// </summary>
9 public string Word
10 {
11 get
12 {
13 return _word;
14 }
15 }
16
17 /**//// <summary>
18 /// 該中文詞語的權重。
19 /// </summary>
20 public int Power
21 {
22 get
23 {
24 return _power;
25 }
26 }
27
28 /**//// <summary>
29 /// 結構初始化。
30 /// </summary>
31 /// <param name="word">中文詞語</param>
32 /// <param name="power">該詞語的權重</param>
33 public ChineseWordUnit(string word, int power)
34 {
35 this._word = word;
36 this._power = power;
37 }
38 }
ChineseWordsHashCountSet.cs //詞庫容器
1 /**//// <summary>
2 /// 記錄字串出現在中文字典所錄中文詞語的前端的次數的字典類別。如字串「中」出現在「中國」的前端，則在字典中記錄一個次數。
3 /// </summary>
4 public class ChineseWordsHashCountSet
5 {
6 /**//// <summary>
7 /// 記錄字串在中文字詞中出現次數的Hashtable。鍵為特定的字串，值為該字串在中文詞語中出現的次數。
8 /// </summary>
9 private Hashtable _rootTable;
10
11 /**//// <summary>
12 /// 型別初始化。
13 /// </summary>
14 public ChineseWordsHashCountSet()
15 {
16 _rootTable = new Hashtable();
17 }
18
19 /**//// <summary>
20 /// 查詢指定字串出現在中文字典所錄中文詞語的前端的次數。
21 /// </summary>
22 /// <param name="s">指定字串</param>
23 /// <returns>字串出現在中文字典所錄中文字詞的前端的次數。若為-1，表示不出現。 </returns>
24 public int GetCount(string s)
25 {
26 if (!this._rootTable.ContainsKey(s.Length))
27 {
28 return -1;
29 }
30 Hashtable _tempTable = (Hashtable)this._rootTable[s.Length];
31 if (!_tempTable.ContainsKey(s))
32 {
33 return -1;
34 }
35 return (int)_tempTable[s];
36 }
37
38 /**//// <summary>
39 /// 插入一個字詞給次數字典。解析該詞語，插入次數字典。
40 /// </summary>
41 /// <param name="s">所處理的字串。 </param>
42 public void InsertWord(string s)
43 {
44 for(int i=0;i<s.Length;i++)
45 {
46 string _s = s.Substring(0,i+1);
47 this.InsertSubString(_s);
48 }
49 }
50
51 /**//// <summary>
52 /// 向次數字典插入一個字串的次數記錄。
53 /// </summary>
54 /// <param name="s">所插入的字串。 </param>
55 private void InsertSubString(string s)
56 {
57 if (!_rootTable.ContainsKey(s.Length)&&s.Length>0)
58 {
59 Hashtable _newHashtable = new Hashtable();
60 _rootTable.Add(s.Length,_newHashtable);
61 }
62 Hashtable _tempTable = (Hashtable)_rootTable[s.Length];
63 if (!_tempTable.ContainsKey(s))
64 {
65 _tempTable.Add(s,1);
66 }
67 else
68 {
69 _tempTable[s]=(int)_tempTable[s]+1;
70 }
71 }
72 }
ChineseParse.cs //分詞器
1 /**//// <summary>
2 /// 中文分詞器。
3 /// </summary>
4 public class ChineseParse
5 {
6 private static ChineseWordsHashCountSet _countTable;
7
8 static ChineseParse()
9 {
10 _countTable = new ChineseWordsHashCountSet();
11 InitFromFile("ChineseDictionary.txt");
12 }
13
14 /**//// <summary>
15 /// 從指定的檔案初始化中文詞語字典和字串次數字典。
16 /// </summary>
17 /// <param name="fileName">檔名</param>
18 private static void InitFromFile(string fileName)
19 {
20 string path = Directory.GetCurrentDirectory() +@" " + fileName;
21 if (File.Exists(path))
22 {
23 using (StreamReader sr = File.OpenText(path))
24 {
25 string s = "";
26 while ((s = sr.ReadLine()) != null)
27 {
28 ChineseWordUnit _tempUnit = InitUnit(s);
29 _countTable.InsertWord(_tempUnit.Word);
30 }
31 }
32 }
33 }
34
35 /**//// <summary>
36 /// 將字串解析為ChineseWordUnit。
37 /// </summary>
38 /// <param name="s">字串</param>
39 /// <returns>解析得到的ChineseWordUnit</returns>
40 private static ChineseWordUnit InitUnit(string s)
41 {
42 Regex reg = new Regex(@"s+");
43 string[] temp = reg.Split(s);
44 if (temp.Length!=2)
45 {
46 throw new Exception("字串解析錯誤："+s);
47 }
48 return new ChineseWordUnit(temp[0],Int32.Parse(temp[1]));
49 }
50
51 /**//// <summary>
52 /// 分析輸入的字串，將其切割成一個個的詞語。
53 /// </summary>
54 /// <param name="s">待切割的字串</param>
55 /// <returns>所切割得到的中文詞語陣列</returns>
56 public static string[] ParseChinese(string s)
57 {
58 int _length = s.Length;
59 string _temp = String.Empty;
60 ArrayList _words = new ArrayList();
61
62 for(int i=0;i<s.Length;)
63 {
64 _temp = s.Substring(i,1);
65 if (_countTable.GetCount(_temp)>1)
66 {
67 int j=2;
68
69 for (;i+j<s.Length+1&&_countTable.GetCount(s.Substring(i,j))>0;j++)
70 {
71 }
72 _temp = s.Substring(i,j-1);
73 i = i + j - 2;
74 }
75 i++;
76 _words.Add(_temp);
77 }
78
79 string[] _tempStringArray = new string[_words.Count];
80 _words.CopyTo(_tempStringArray);
81 return _tempStringArray;
82 }
83 }
四、測試
和海量分詞演示程序對比測試:
Case 1: 新浪體育訊在被尤文淘汰之後，皇馬主帥博斯克拒絕接受媒體對球隊后防線的批評，同時還為自己排出的首發陣容進行了辯護。 「失利是全隊的責任，而不僅僅是後防線該受指責，」博斯克說，「我並不認為我們踢得一塌糊塗。」「我們進入了半決賽，而且在晉級的道路上一路奮戰。即使是今天的比賽我們也有幾個翻身的機會，但我們面對的對手非常強大，他們踢得非常好。 」博斯克還說。對於博斯克在首發中排出了久疏戰陣的坎比亞索，賽後有記者提出了質疑，認為完全應該將隊內的另一名球員帕文派遣上場以加強後衛線。對於這一疑議，博斯克拒絕承擔所謂的“責任”，認為球隊的先發沒有問題。 「我們按照整個賽季以來的方式做了，對於人員上的變化我沒有什麼可說的。」對於球隊在本賽季的前景，博斯克表示皇馬還有西甲聯賽的冠軍作為目標。 「皇家馬德里在冠軍盃中戰鬥到了最後，我們在聯賽中也將這麼做。」
海量分詞結果:
新浪體育訊在被尤文淘汰之後， 皇馬主帥博斯克拒絕接受媒體對球隊後防線的批評， 同時也為自己排出的先發陣容進行了辯護。 「 失利是全隊的責任， 而不僅僅是後防線該受指責， 」 博斯克說， 「 我並不認為我們踢得一塌糊塗。」 「 我們進入了半決賽， 而且在晉級的道路上一路奮戰。即使是今天的比賽我們也有幾個翻身的機會， 但我們面對的對手非常強大， 他們踢得非常好。 」 博斯克還說。 對於博斯克在首發中排出了久疏戰陣的坎比亞索， 賽後有記者提出了質疑， 認為完全應該將隊內的另一名球員帕文派遣上場以加強後衛線。 對於這一疑議， 博斯克拒絕承擔所謂的「 責任」 ， 認為球隊的先發沒有問題。 「 我們按照整個賽季以來的方式做了， 對於人員上的變化我沒有什麼可說的。」 對於球隊在本賽季的前景， 博斯克表示皇馬還有西甲聯賽的冠軍作為目標。 「 皇家馬德里在冠軍盃中戰鬥到了最後， 我們在聯賽中也將這麼做。」
ChineseParse 分詞結果:
新浪體育訊在被尤文淘汰之後， 皇馬主帥博斯克拒絕接受媒體對球隊后防線的批評， 同時也為自己排出的先發陣容進行了辯護。 「 失利是全隊的責任， 而不僅僅是後防線該受指責， 」 博斯克說， 「 我並不認為我們踢得一塌糊塗。 」 「 我們進入了半決賽， 而且在晉級的道路上一路奮戰。即使是今天的比賽我們也有幾個翻身的機會， 但我們面對的對手非常強大， 他們踢得非常好。 」 博斯克還說。對於博斯克在首發中排出了久疏戰陣的坎比亞索， 賽後有記者提出了質疑， 認為完全應該將隊內的另一名球員帕文派遣上場以加強後衛線。 對於這一疑議， 博斯克拒絕承擔所謂的「 責任」 ， 認為球隊的先發沒有問題。 「 我們按照整個賽季以來的方式做了， 對於人員上的變化我沒有什麼可說的。 」 對於球隊在本賽季的前景， 博斯克表示皇馬還有西甲聯賽的冠軍作為目標。 「 皇家馬德里在冠軍盃中戰鬥到了最後， 我們在聯賽中也將這麼做。 」
因為沒有體育專業詞庫和人名專業詞庫,所以ChineseParse不能認識這些專業詞.
Case 2: 我國汽車社會第一次重大轉型歷經十多年時間。在1994年推出的《汽車工業產業政策》中，最醒目的一條就是「逐步改變以行政機關、團體、事業單位及國營企業為主的公款購買、使用小型汽車的消費結構」。從公款購買汽車為主到汽車逐漸進入家庭，第一次重大轉型為人民生活品質帶來了巨大提升。這次轉型的主要動力是態度鮮明的產業政策、持續高速成長的國民經濟以及蓬勃發展的國內汽車產業。 然而，當我們快速邁進以私人汽車為主體的汽車社會的時候，也面臨著新的形勢、新的考驗：中央強調樹立和落實科學發展觀，要求國內企業提高自主創新能力；今年「兩會」期間，中央又提出建構和諧社會和節約型社會的精神；同時，我國汽車社會面臨能源緊缺、燃油價格上漲、土地資源有限等諸多不利因素。在這樣的大背景下，進行第二次重大轉型刻不容緩。
海量分詞結果:
我國汽車社會第一次重大轉型歷經十多年時間。 在1994年推出的《 汽車工業產業政策》 中， 最醒目的一條就是「 逐步改變以行政機關、 團體、 事業單位及國營企業為主的公款購買、 使用小汽車的消費結構」 。 從公款購買汽車為主到汽車逐漸進入家庭， 第一次重大轉型為人民生活品質帶來了巨大提升。 這次轉型的主要動力是態度鮮明的產業政策、 持續高速成長的國民經濟以及蓬勃發展的國內汽車產業。 然而， 當我們快速邁進以私人汽車為主體的汽車社會的時候， 也面臨著新的形勢、 新的考驗： 中央強調樹立和落實科學發展觀， 要求國內企業提高自主創新能力； 今年“ 兩會” 期間， 中央又提出建構和諧社會和節約型社會的精神； 同時， 我國汽車社會面臨能源緊缺、 燃油價格上漲、 土地資源有限等諸多不利因素。 在這樣的大背景下， 進行第二次重大轉型刻不容緩。
ChineseParse分詞結果:
我國汽車社會第一次重大轉型歷經十多年時間。 在1 9 9 4 年推出的《 汽車工業產業政策》 中， 最醒目的一條就是「 逐步改變以行政機關、團體、 事業單位及國有企業為主的公款購買、 使用小汽車的消費結構」。 從公款購買汽車為主到汽車逐漸進入家庭， 第一次重大轉型為人民生活品質帶來了巨大提升。 這次轉型的主要動力是態度鮮明的產業政策、 持續高速成長的國民經濟以及蓬勃發展的國內汽車產業。 然而， 當我們快速邁進以私人汽車為主體的汽車社會的時候， 也面臨著新的形勢、 新的考驗： 中央強調樹立和落實科學發展觀， 要求國內企業提高自主創新能力； 今年“ 兩會” 期間， 中央又提出建構和諧社會和節約型社會的精神； 同時， 我國汽車社會面臨能源緊缺、 燃油價格上漲、 土地資源有限等諸多不利因素。 在這樣的大背景下， 進行第二次重大轉型刻不容緩。
可以看出,ChineseParse不能智能處理"第一次","第二次"這種詞,對數字也沒識別能力,不過基本的分詞效果還是可以的.
(畢竟我3個小時就把程式搞定了,怎麼能和別人十年累積的比呢?)
效能測試(迅馳1.5M): 每秒鐘67.7萬字
程式優化有應該更高.
五、小結
進一步應該做的:
1,能辨識簡單的外語,數字
2,具備簡單智能
3,擴充詞庫
然後就有實用價值了.
註:前幾個月寫的大多都是諸如此類簡單的中文處理小程序,如繁簡轉換,自動排版,批量替換,中文分詞,有時間的話我會把這些程式集中起來打包成一個實用的中文處理工具.不知道大家還有什麼需求,不防說說.