算法课程设计中文分词程序设计与实现

1、辽 宁 科 技 大 学课程设计说明书设计题目： 中文分词程序设计与实现 学院、系： 装备制造学院 专业班级： 计算机09（1）班 学生姓名： 高 祥 指导教师： 迟呈英 成 绩： 2012年 3 月 2 日目 录一 需求分析随着国内互联网的迅猛发展，网络信息量急剧膨胀，如果完全由人工来整理如此繁多的信息，那是难以想象的工作量，同时也不现实的，如何有效、快速、准确的从大量的信息中找到我们所需要的信息，是摆在我们面前的一个重要和迫切的任务，为了解决这个难题，人们采用了中文分词技术，通过分词技术，就可以使得对海量信患的整理更准确更合理，使得检索结果更准确，效率也会大幅度地提高。所谓中文分词，就是把一

2、个汉语句子按照其中词的含义进行切分。随羞人们更深入熬研究，中文信息处理技术得到了广泛应用，并对中文分词技术的要求也越来越高。中文分词技术已经引起多方的关注，并成为中文信息处理的一个前沿课题l卜21。目前在自然语言处理技术中，中文处理技术远远落后于西文处理技术，许多西文的处理方法中文不能直接采用，就是因为中文必须进行分词处理。中文分词是其它中文信息处理的基础，搜索弓|擎只是中文分词的一个应用，其它应用比如机器翻译(mt)、语音合成、自动分类、自动摘要、自动校对、中文文献瘁全文检索等翻，都需要焉到分词。分词准确性对搜索弓|擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可

3、用的，因为搜索弓l擎需要处理数以亿诗的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求，中文分词技术要想更好的服务予更多的产品，需要更多的专业队伍投入到研究中来，因此，中文分词的研究还是一个相当长的探索过程。目前中文分词得到了很多现实的应用，主要体现在在信息检索、同音字和多音字方面的识别、文本校对、简体繁体的囱动转换、自动标引、自动文撬、视器翻译、语言文字研究、搜索弓|擎研究、自然语言理解和中文信息处哈尔滨二程大学硕七学位论文理等方面m，也是中文智能计算技术发展的前提和基础。随着对中文分词技术关注度的不断提高，大

4、量的学者都加入到了这一研究领域，使中文分词取得了丰硕的研究成果。近10年来，语言学界、人工智能领域和情报检索界的学者们，在中文分词与自动标引的研究与实践上进行了大量的研究，找到了许多解决中文分词的方法，目前关于中文分词研究方法主要有三个方面，即基于字符串匹配的分词方法、基于统计的分词方法和基于理解的分词方法。中文分词的研究，主要是从词层面进行的研究，这一问题很早就受到了广泛的关注。目前，各种分词系统也不断建立，分词系统在运行速度、准确度等方面已经具有了研究应用的价值，但是在句子中词该如何被界定，仍然是一个比较困难的问题，同时，在不同的应用领域由于应用需求的不同，需要达到的分词效果有很大区别。词

5、的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。在这一长期的研究和实践过程中，分词规范、歧义字段处理和未登录词识别成为困扰我们的主要技术难题，随着计算机技术和汉语语言研究的发展，中文分词技术将会有更大的突破。二 设计主要分为两大模块：一个建立一棵树，一个是查询。建树有三个层次，第一层一维数组，第二层是数组，用于二分查找使用，第三层是二叉树。查询分为直接查询第一层的一维数组，第二层用二分查找（第二层汉子相同的平均概率是26，一般第二字成词切相同），第三层直接顺序查找，以及查找句子中的数字和汉子标点。 输出：（1）建树 包括：以此字开头的词语有几个；在

6、一维数组中的中位置；结束 （2）查询 包括输出每个词的首字。然后输出分词后的结果。输入语句开始截取第一个字len2否len4否是第二层二分查找第三层 直接顺序查找打印词语结束三 编码与调试因为字符串比较所需的时间同字符串的长度成正比，对于较长的词条，这种现象尤为突出。为了消除这种冗余操作，我们提出将词典的词尾部分以自动机的形式来组织。为此，我们将组成单词的每个字以一种链表节点的形式存储，其抽象数据结构的定义如下：struct node3 string s; bool isword; node3 *l,*r; node3(string s = ,bool isword = 0, node3 *l

7、 = 0, node3 *r = 0): s(s),isword(isword),l(l),r(r);struct node2 string s; bool isword; node3 *child; node2(string s =,bool isword = 0, node3* child =0): s(s),isword(isword),child(child);struct node string s; vectorv;vectordic;int binarysearch(int x, string sec)/二分查找第二个字 int l = 0,r = dicx.v.size() -

8、 1; while (l 1; if (dicx.vmid.s = sec) return mid; else if (dicx.vmid.s s = cc) return p; else p = p-l; return 0;四 结果分析截取每一个词的第一个字讲一段话拆分成词的形式逐词遍历法将词典中的所有词按由长到短的顺序在文章中逐字搜索,直至文章结束。也就是说,不管文章有多短,词典有多大,都要将词典遍历一遍。这种方法效率比较低，大一点的系统一般都不使用。最大正向匹配法()通常简称为法。其基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字

9、典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。当然，最大匹配算法是一种基于分词词典的机械分词法，不能根据文档上下文的语义特征来切分词语，对词典的依赖性较大，所以在实际使用时，难免会造成一些分词错误，为了提高系统分词的准确度，可以采用正向最大匹配法和逆向最大匹配法相结合的分词方案（即双向匹配法，见（四）。）全切分要求获得

10、输入序列的所有可接受的切分形式，而部分切分只取得一种或几种可接受的切分形式，由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基础上的分词方法不管采取何种歧义纠正策略，都可能会遗漏正确的切分，造成分词错误或失败。而建立在全切分基础上的分词方法，由于全切分取得了所有可能的切分形式，因而从根本上避免了可能切分形式的遗漏，克服了部分切分方法的缺陷。全切分算法能取得所有可能的切分形式，它的句子覆盖率和分词覆盖率均为100%，但全切分分词并没有在文本处理中广泛地采用，原因有以下几点：1)全切分算法只是能获得正确分词的前提，因为全切分不具有歧义检测功能，最终分词结果的正确性和完全性依赖于独立的歧义处

11、理方法，如果评测有误，也会造成错误的结果。2)全切分的切分结果个数随句子长度的增长呈指数增长，一方面将导致庞大的无用数据充斥于存储数据库；另一方面当句长达到一定长度后，由于切分形式过多,造成分词效率严重下降。并行分词方法：这种分词方法借助于一个含有分词词库的管道进行,比较匹配过程是分步进行的,每一步可以对进入管道中的词同时与词库中相应的词进行比较,由于同时有多个词进行比较匹配,因而分词速度可以大幅度提高。这种方法涉及到多级内码理论和管道的词典数据结构。（详细算法可以参考吴胜远的并行分词方法的研究。）五 参考文献1 国家技术监督局信息处理用现代汉语分词规范，中华人民共和国国家标准gbt13715

12、92中国标准出版社，19932 硕士学位论文.中文自动分词系统的研究与实现. 周程远 200911013硕士学位论文 .基于条件随机场的中文分词研究与应用, 颜军 200904014 网络文章中文分词入门之最大匹配法 发表于 2009年01月12号 由 52nlp 5一种基于自动机的分词方法.鞍山科技大学.计算机学院,东北大学.信息学院 迟呈英，战学刚, 姚天顺6种中文分词算法优劣比较，http：wwwhtmldatacn?p=248六 总结分词是中文自然语言处理的基础，在现实中已经得到广泛应用。比如，google的chrome浏览器就内置了中文分词功能。如上图，我们可以注意到，在chrome

13、中双击无链接文本时，chrome选中的不是一个字，也不是一句话，而是一个词。当然，中文分词在数据挖掘等方面的应用就更加明显了。掌握自然语言处理的基本知识，已经成为it行业对计算机专业学生的基本要求。虽然我曾经系统学习过算法数据结构等基础课程，但编写程序时仍然遇到了很多问题，仅在汉字编码的问题上就纠缠了很久。幸而在很多细致的文档论文的帮助下，使我对分词程序有了更深的了解。也懂得了算法也需要团结合作才能效率更高。加深了我对各种算法的了解，增强了我的功底。自然语言处理是一个正在快速发展的学科，但愿我有朝一日能在这个领域大显身手。七 附录（程序源代码）#include #include #includ

14、e #include using namespace std;const int start1 = 0xb0,start2 = 0xa1, end1 = 0xf8,end2 = 0xff;const int maxwordlen = 48;ifstream fin(segdict.txt);ofstream out(out1.txt);/- 建树部分-struct node3 string s; bool isword; node3 *l,*r; node3(string s = ,bool isword = 0, node3 *l = 0, node3 *r = 0): s(s),iswor

15、d(isword),l(l),r(r);struct node2 string s; bool isword; node3 *child; node2(string s =,bool isword = 0, node3* child =0): s(s),isword(isword),child(child);struct node string s; vectorv;vectordic;const range =(end1 - start1)*(end2 - start2);/一维数组范围int arrayrange;/一维数组代替哈希表void begin() /初始化 for (int i

16、 = 0; i l != 0) last = last-l; if (last-s != t) last-l = new node3(t,(len = 2),0, 0); last = last-l; if (len 2) buildtree(s.substr(2,maxwordlen),last-r);void dictionary() /构造整个结构 begin(); string s; int n,k = 0; while(fin s) node n; n.s = s.substr(0,2); int m1 = (unsigned char)s0 - start1)*(unsigned

17、char)s1 - start2)+(unsigned char)s0 - start1; arraym1 = k+; out s arraym1 n; out n endl; for (int i = 0; i s; out s 0 & n.vsize-1.s != t) n.v.push_back(node2(t, (len = 4),0); size = n.v.size(); if (len 4) buildtree(s.substr(4,maxwordlen),n.vsize-1.child); dic.push_back(n); out end array endl endl;/-

18、查询部分-vectordest;int binarysearch(int x, string sec)/二分查找第二个字 int l = 0,r = dicx.v.size() - 1; while (l 1; if (dicx.vmid.s = sec) return mid; else if (dicx.vmid.s s = cc) return p; else p = p-l; return 0;unsigned chartoint(char c) return unsigned(unsigned char)c) ;bool iscc(char c) unsigned val= char

19、toint(c); return val = start1 & val end1;bool isec(char c) unsigned val= chartoint(c); return val 0x80;void findnum(string src, vector&dest, int &starpos,int &endpos) int strlen = src.length(); while (endpos starpos) dest.push_back(src.substr(starpos,endpos-starpos); starpos = endpos; void segment(s

20、tring src, vector&dest) int strlen = src.length(); int startpos = 0, endpos; while (startpos = strlen) return ; unsigned seglen = 2; string headcc = src.substr(startpos, 2); cout headcc endl = 0); string seccc = src.substr(startpos + 2,2); if (seccc.length() 0 & iscc(seccc0) int b2 = binarysearch(headindex,seccc); if (b2=0) if (dicheadindex.vb2.isword) seglen += 2; endpos = startpos + 4; node3 *p =