算法课程设计

辽宁科技大学。

课程设计说明书。

设计题目：中文分词程序设计与实现

学院、系：装备制造学院。

专业班级： 09计算机二班。

学生姓名：吴坤鹏。

指导教师：迟呈英。

成绩。2023年 10 月 29 日。

一．需求分析。

随着国内互联网的迅猛发展，网络信息量急剧膨胀，如果完全由人工来整理如此繁多的信息，那是难以想象的工作量，同时也不现实的，如何有效、快速、准确的从大量的信息中找到我们所需要的信息，是摆在我们面前的一个重要和迫切的任务，为了解决这个难题，人们采用了中文分词技术，通过分词技术，就可以使得对海量信患的整理更准确更合理，使得检索结果更准确，效率也会大幅度地提高。所谓中文分词，就是把一个汉语句子按照其中词的含义进行切分。随羞人们更深入熬研究，中文信息处理技术得到了广泛应用，并对中文分词技术的要求也越来越高。

中文分词技术已经引起多方的关注，并成为中文信息处理的一个前沿课题l卜21。目前在自然语言处理技术中，中文处理技术远远落后于西文处理技术，许多西文的处理方法中文不能直接采用，就是因为中文必须进行分词处理。中文分词是其它中文信息处理的基础，搜索弓|擎只是中文分词的一个应用，其它应用比如机器翻译(mt)、语音合成、自动分类、自动摘要、自动校对、中文文献瘁全文检索等翻，都需要焉到分词。

分词准确性对搜索弓|擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索弓l擎需要处理数以亿诗的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求，中文分词技术要想更好的服务予更多的产品，需要更多的专业队伍投入到研究中来，因此，中文分词的研究还是一个相当长的探索过程。

目前中文分词得到了很多现实的应用，主要体现在在信息检索、同音字和多音字方面的识别、文本校对、简体繁体的囱动转换、自动标引、自动文撬、视器翻译、语言文字研究、搜索弓|擎研究、自然语言理解和中文信息处哈尔滨]二程大学硕七学位**理等方面m，也是中文智能计算技术发展的前提和基础。随着对中文分词技术关注度的不断提高，大量的学者都加入到了这一研究领域，使中文分词取得了丰硕的研究成果。近10年来，语言学界、人工智能领域和情报检索界的学者们，在中文分词与自动标引的研究与实践上进行了大量的研究，找到了许多解决中文分词的方法，目前关于中文分词研究方法主要有三个方面，即基于字符串匹配的分词方法、基于统计的分词方法和基于理解的分词方法。

中文分词的研究，主要是从词层面进行的研究，这一问题很早就受到了广泛的关注。目前，各种分词系统也不断建立，分词系统在运行速度、准确度等方面已经具有了研究应用的价值，但是在句子中词该如何被界定，仍然是一个比较困难的问题，同时，在不同的应用领域由于应用需求的不同，需要达到的分词效果有很大区别。词的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。

在这一长期的研究和实践过程中，分词规范、歧义字段处理和未登录词识别成为困扰我们的主要技术难题，随着计算机技术和汉语语言研究的发展，中文分词技术将会有更大的突破。

二．设计。

主要分为两大模块：

一个建立一棵树，一个是查询。建树有三个层次，第一层一维数组，第二层是数组，用于二分查找使用，第三层是二叉树。查询分为直接查询第一层的一维数组，第二层用二分查找（第二层汉子相同的平均概率是26，一般第二字成词切相同），第三层直接顺序查找，以及查找句子中的数字和汉子标点。

输出：（1）建树包括：以此字开头的词语有几个；在一维数组中的中位置；结束。

2）查询包括输出每个词的首字。然后输出分词后的结果。

三．编码与调试。

因为字符串比较所需的时间同字符串的长度成正比，对于较长的词条，这种现象尤为突出。为了消除这种冗余操作，我们提出将词典的词尾部分以自动机的形式来组织。为此，我们将组成单词的每个字以一种链表节点的形式存储，其抽象数据结构的定义如下：

struct node3

string s;

bool isword;

node3 *l,*r;

node3(string s = bool isword = 0, node3 *l = 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 = dic[x]. 1;

while (l <=r)

return -1;

node3* remainsearch(node3*p, string cc) /顺序查找剩下的字。

while (p !=0)

return 0;

四．结果分析。

截取每一个词的第一个字。

讲一段话拆分成词的形式。

逐词遍历法将词典中的所有词按由长到短的顺序在文章中逐字搜索，直至文章结束。也就是说，不管文章有多短，词典有多大，都要将词典遍历一遍。这种方法效率比较低，大一点的系统一般都不使用。

最大正向匹配法通常简称为ｍｍ法。其基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。

若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理……如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。

当然，最大匹配算法是一种基于分词词典的机械分词法，不能根据文档上下文的语义特征来切分词语，对词典的依赖性较大，所以在实际使用时，难免会造成一些分词错误，为了提高系统分词的准确度，可以采用正向最大匹配法和逆向最大匹配法相结合的分词方案（即双向匹配法，见（四）。）

全切分要求获得输入序列的所有可接受的切分形式，而部分切分只取得一种或几种可接受的切分形式，由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基础上的分词方法不管采取何种歧义纠正策略，都可能会遗漏正确的切分，造成分词错误或失败。而建立在全切分基础上的分词方法，由于全切分取得了所有可能的切分形式，因而从根本上避免了可能切分形式的遗漏，克服了部分切分方法的缺陷。

全切分算法能取得所有可能的切分形式，它的句子覆盖率和分词覆盖率均为100%，但全切分分词并没有在文本处理中广泛地采用，原因有以下几点：

1)全切分算法只是能获得正确分词的前提，因为全切分不具有歧义检测功能，最终分词结果的正确性和完全性依赖于独立的歧义处理方法，如果评测有误，也会造成错误的结果。

2)全切分的切分结果个数随句子长度的增长呈指数增长，一方面将导致庞大的无用数据充斥于存储数据库；另一方面当句长达到一定长度后，由于切分形式过多，造成分词效率严重下降。

并行分词方法：这种分词方法借助于一个含有分词词库的管道进行，比较匹配过程是分步进行的，每一步可以对进入管道中的词同时与词库中相应的词进行比较，由于同时有多个词进行比较匹配，因而分词速度可以大幅度提高。这种方法涉及到多级内码理论和管道的词典数据结构。

（详细算法可以参考吴胜远的《并行分词方法的研究》。）

五．参考文献。

1 国家技术监督局．信息处理用现代汉语分词规范，中华人民共和国国家标准gb／t13715．92．中国标准出版社，1993

2 硕士学位**。中文自动分词系统的研究与实现。周程远 20091101

3硕士学位** .基于条件随机场的中文分词研究与应用，颜军 20090401

4 网络文章中文分词入门之最大匹配法发表于 2023年01月12号由 52nlp

5一种基于自动机的分词方法。鞍山科技大学。计算机学院，东北大学。信息学院迟呈英，战学刚，姚天顺。

6种中文分词算法优劣比较，http：／／www．htmldata．cn／?p=248

六．总结。

分词是中文自然语言处理的基础，在现实中已经得到广泛应用。比如，google的chrome浏览器就内置了中文分词功能。如上图，我们可以注意到，在chrome中双击无链接文本时，chrome选中的不是一个字，也不是一句话，而是一个词。

当然，中文分词在数据挖掘等方面的应用就更加明显了。掌握自然语言处理的基本知识，已经成为it行业对计算机专业学生的基本要求。

算法课程设计

算法课程设计

算法课程设计

算法课程设计

其他用户还读了