ASP NET 简单中文分词算法

ASP NET 简单中文分词算法 ASP.NET简单中文分词算法2010-05-10 09:26几个月之前,在网上找到了一个中文词库素材(几百K),当时便想写一个分词程序了.我对汉语分词没有什么研究,也就凭自己臆想而写.若有相关方面专家,还请多给意见. 一、词库 词库大概有5万多词语(google能搜到,类似的词库都能用),我摘要如下: 地区82重要81新华社80技术80会议80自己79干部78职工78群众77没有77今天76同志76部门75加强75组织75第一列是词,第二列是权重.我写的这个分词算法目前并未利用权重. 二、 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思路 算法简要描述: 对一个字符串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 9public string Word 10{11 get 12{13 return _word; 14}15}16 17/*////summary 18///该中文词语的权重。19////summary 20 25}26}27 public int Power 21{22 get 23{24 return _power; 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 4public class ChineseWordsHashCountSet 5{6/*////summary 7///记录字符串在中文词语中出现次数的Hashtable。键为特定的字符串，值 为该字符串在中文词语中出现的次数。8////summary 9private 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 4public class ChineseParse 5{6 private static ChineseWordsHashCountSet _countTable; 7 8static 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 ;60 ArrayList int _length=s.Length;59 string _temp=String.Empty_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 99 4年出台的《汽车工业产业政策》中，最醒目的一条就是"逐步改变以行政机关、团体、事业单位及国有企业为主的公款购买、使用小汽车的消费结构"。从公款购买汽车为主到汽车逐渐进入家庭，第一次重大转型给人民生活质量带来了巨大提升。这次转型的主要推动力是态度鲜明的产业政策、持续高速增长的国民经济以及蓬勃发展的国内汽车工业。然而，当我们快速迈进以私人汽车为主体的汽车社会的时候，也面临着新的形势、新的考验:中央强调树立和落实科学发展观，要求国内企业提高自主创新能力;今年"两会"期间，中央又提出构建和谐社会和节约型社会的精神;同时，我国汽车社会面临能源紧缺、燃油价格上涨、土地资源有限等诸多不利因素。在这样的大背景下，进行第二次重大转型刻不容缓。 可以看出,ChineseParse不能智能处理"第一次","第二次"这种词,对数字也没识别能力,不过基本的分词效果还是可以的. (毕竟我3个小时就把程序搞定了,怎么能和别人十年积累的比呢?) 性能测试(迅驰1.5M):每秒钟67.7万字 程序优化有应该更高. 五、小结 进一步应该做的:1,能识别简单的外语,数字2,具备简单智能3,扩充词库 然后就有实用价值了. 注:前几个月写的大多都是诸如此类简单的中文处理小程序,如繁简转换,自动排版,批量替换,中文分词,有时间的话我会把这些程序集中起来打包成一个实用的中文处理工具.不知道大家还有什么需求,不防说说. 2010-05-10 13:45|