幾個月之前,在網上找到了一個中文詞庫素材(幾百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
18
/// 該中文詞語的權重。
19
20
public int Power
21
22
23
24
return _power;
25
26
27
28
29
/// 結構初始化。
30
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 //詞庫容器
/// <summary>
/// 記錄字元串出現在中文字典所錄中文詞語的前端的次數的字典類。如字元串“中”出現在“中國”的前端，則在字典中記錄一個次數。
/// </summary>
public class ChineseWordsHashCountSet
/// 記錄字元串在中文詞語中出現次數的Hashtable。鍵為特定的字元串，值為該字元串在中文詞語中出現的次數。
private Hashtable _rootTable;
/// 類型初始化。
public ChineseWordsHashCountSet()
_rootTable = new Hashtable();
/// 查詢指定字元串出現在中文字典所錄中文詞語的前端的次數。
/// <param name="s">指定字元串</param>
/// <returns>字元串出現在中文字典所錄中文詞語的前端的次數。若為-1，表示不出現。</returns>
public int GetCount(string s)
if (!this._rootTable.ContainsKey(s.Length))
return -1;
Hashtable _tempTable = (Hashtable)this._rootTable[s.Length];
if (!_tempTable.ContainsKey(s))
return (int)_tempTable[s];
39
/// 向次數字典中插入一個詞語。解析該詞語，插入次數字典。
40
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
52
/// 向次數字典中插入一個字元串的次數記錄。
53
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
64
65
_tempTable.Add(s,1);
66
67
else
68
69
_tempTable[s]=(int)_tempTable[s]+1;
70
71
72
ChineseParse.cs //分詞器
/// 中文分詞器。
public class ChineseParse
private static ChineseWordsHashCountSet _countTable;
static ChineseParse()
_countTable = new ChineseWordsHashCountSet();
InitFromFile("ChineseDictionary.txt");
/// 從指定的檔案中初始化中文詞語字典和字元串次數字典。
/// <param name="fileName">檔案名</param>
private static void InitFromFile(string fileName)
string path = Directory.GetCurrentDirectory() +@"\" + fileName;
if (File.Exists(path))
using (StreamReader sr = File.OpenText(path))
{
string s = "";
while ((s = sr.ReadLine()) != null)
{
ChineseWordUnit _tempUnit = InitUnit(s);
_countTable.InsertWord(_tempUnit.Word);
}
}
/// 将一個字元串解析為ChineseWordUnit。
/// <param name="s">字元串</param>
/// <returns>解析得到的ChineseWordUnit</returns>
private static ChineseWordUnit InitUnit(string s)
Regex reg = new Regex(@"\s+");
string[] temp = reg.Split(s);
if (temp.Length!=2)
throw new Exception("字元串解析錯誤："+s);
return new ChineseWordUnit(temp[0],Int32.Parse(temp[1]));
/// 分析輸入的字元串，将其切割成一個個的詞語。
/// <param name="s">待切割的字元串</param>
/// <returns>所切割得到的中文詞語數組</returns>
public static string[] ParseChinese(string s)
int _length = s.Length;
string _temp = String.Empty;
ArrayList _words = new ArrayList();
for(int i=0;i<s.Length;)
_temp = s.Substring(i,1);
if (_countTable.GetCount(_temp)>1)
int j=2;
for (;i+j<s.Length+1&&_countTable.GetCount(s.Substring(i,j))>0;j++)
_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年 出台 的 《 汽車 工業 産業 政策 》 中 ， 最 醒目 的 一條 就是 “ 逐漸 改變 以 行政 機關 、 團體 、 事業 機關 及 國有 企業 為主 的 公款 購買 、 使用 小汽車 的 消費 結構 ” 。 從 公款 購買 汽車 為主 到 汽車 逐漸 進入 家庭 ， 第一次 重大 轉型 給 人民 生活 品質 帶來 了 巨大 提升 。 這次 轉型 的 主要 推動力 是 态度 鮮明 的 産業 政策 、 持續 高速 增長 的 國民經濟 以及 蓬勃 發展 的 國内 汽車 工業 。 然而 ， 當 我們 快速 邁進 以 私人 汽車 為 主體 的 汽車 社會 的 時候 ， 也 面臨 着 新 的 形勢 、 新 的 考驗 ： 中央 強調 樹立 和 落實 科學 發展觀 ， 要求 國内 企業 提高 自主 創新 能力 ； 今年 “ 兩會 ” 期間 ， 中央 又 提出 建構 和諧 社會 和 節約型 社會 的 精神 ； 同時 ， 我國 汽車 社會 面臨 能源 緊缺 、 燃油 價格 上漲 、 土地 資源 有限 等 諸多 不利 因素 。 在 這樣 的 大 背景 下 ， 進行 第二次 重大 轉型 刻不容緩 。
我國 汽車 社會 第一 次 重大 轉型 曆經 十 多年 時間 。 在 1 9 9 4 年 出台 的 《 汽車 工業 産業 政策 》 中 ， 最 醒目 的 一條 就是 “ 逐漸 改變 以 行政 機關 、團體 、 事業 機關 及 國有 企業 為主 的 公款 購買 、 使用 小汽車 的 消費 結構 ”。 從 公款 購買 汽車 為主 到 汽車 逐漸 進入 家庭 ， 第一 次 重大 轉型 給 人民 生活 品質 帶來 了 巨大 提升 。 這次 轉型 的 主要 推動力 是 态度 鮮明 的 産業 政策 、 持續 高速 增長 的 國民經濟 以及 蓬勃 發展 的 國内 汽車 工業 。 然而 ， 當 我們 快速 邁進 以 私人 汽車 為主 體 的 汽車 社會 的 時候 ， 也 面臨 着 新 的 形勢 、 新 的 考驗 ： 中央 強調 樹立 和 落實 科學 發展觀 ， 要求 國内 企業 提高 自主 創新 能力 ； 今年 “ 兩會 ” 期間 ， 中央 又 提出 建構 和諧 社會 和 節約 型 社會 的 精神 ； 同時 ， 我國 汽車 社會 面臨 能源 緊缺 、 燃油 價格 上漲 、 土地 資源 有限 等 諸多不 利 因素 。 在 這樣 的 大 背景 下 ， 進行 第二 次 重大 轉型 刻不容緩 。
可以看出,ChineseParse不能智能處理"第一次","第二次"這種詞,對數字也沒識别能力,不過基本的分詞效果還是可以的.
(畢竟我3個小時就把程式搞定了,怎麼能和别人十年積累的比呢?)
性能測試(迅馳1.5M): 每秒鐘67.7萬字
程式優化有應該更高.
五、小結
進一步應該做的:
1,能識别簡單的外語,數字
2,具備簡單智能
3,擴充詞庫
然後就有實用價值了.
注:前幾個月寫的大多都是諸如此類簡單的中文處理小程式,如繁簡轉換,自動排版,批量替換,中文分詞,有時間的話我會把這些程式集中起來打包成一個實用的中文處理工具.不知道大家還有什麼需求,不防說說.
本文轉自xiaotie部落格園部落格，原文連結http://www.cnblogs.com/xiaotie/archive/2005/08/28/224626.html如需轉載請自行聯系原作者
xiaotie 集異璧實驗室(GEBLAB)