938
編寫簡單的中文分詞程序
幾個月之前,在網上找到了一個中文詞庫素材(幾百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,擴充詞庫
然後就有實用價值了.
注:前幾個月寫的大多都是諸如此類簡單的中文處理小程序,如繁簡轉換,自動排版,批量替換,中文分詞,有時間的話我會把這些程序集中起來打包成一個實用的中文處理工具.不知道大家還有什麼需求,不防說說.
最後更新：2017-04-02 00:06:27