中文分词程序实验报告含源代码.pdf

北京邮电大学计算机学院北京邮电大学计算机学院自然语言处理导论自然语言处理导论中文分词实验报告中文分词实验报告姓 名：许伟林 学 号：08211306 指导教师：郑岩 日 期：2010/12/22 1内容目录内容目录一、实验目的.3二、实验环境.3三、实验材料.3四、实验设计.3一、分词策略.3词典逆向最大匹配法.4基于确定文法的分词法.4二、程序设计.4查找算法：哈希表查找.4汉字编码格式：UTF-8.5程序流程图.6程序源代码.8五、结果和性能分析.16分词结果示例.16性能分析.17六、有待解决的问题.18七、实验总结.192一、实验目的一、实验目的了解中文分词的意义掌握中文分词的基本方法二、实验环境二、实验环境UBUNTU 10.05GCC v4.4.3三、实验材料三、实验材料中文常用词词典人民日报1998年合订本四、实验设计四、实验设计一、分词策略一、分词策略据我的了解，目前较为成熟的中文分词方法主要有：1、词典正向最大匹配法2、词典逆向最大匹配法3、基于确定文法的分词法4、基于统计的分词方法一般认为，词典的逆向匹配法要优于正向匹配法。基于确定文法和基于统计的方法作为自然语言处理的两个流派，各有千秋。3由于时间仓促，且水平有限，本程序只实现了第 2 种和第 3种分词法，即词典逆向最大匹配法和基于确定文法的分词法。词典逆向最大匹配法词典逆向最大匹配法词典逆向最大匹配法完成分词的大部分工作，设计思路是这样的：1、将词典的每个词条读入内存，最长是4字词，最短是1字词；2、从语料中读入一段（一行）文字，保存为字符串；3、如果字符串长度大于 4个中文字符，则取字符串最右边的 4 个中文字符，作为候选词；否则取出整个字符串作为候选词；4、在词典中查找这个候选词，如果查找失败，则去掉这个候选词的最左字，重复这步进行查找，直到候选词为1个中文字符；5、将候选词从字符串中取出、删除，回到第3步直到字符串为空；6、回到第2步直到语料已读完。基于确定文法的分词法基于确定文法的分词法基于确定文法的分词法可以进行数字、西文、时间的分词，设计思路是这样的：1、增加一个词典，存储中文编码（全角）的大小写拉丁字母、中文小写数字、阿拉伯数字、数字单位（百、千、万、亿、兆）、小数点、百分号、除号；词类型记为D1；2、增加一个词典，存储中文编码的时间单位，包括年、月、日、时、分、秒、点;词类型记为D2；3、文法的正则表达式为D1*D2？。二、程序设计二、程序设计查找算法：哈希表查找查找算法：哈希表查找除了分词结果的准确性，程序的性能也是至关重要的。由于本程序采用了词典法来分词，执行过程需要检索大量数据，因此查找效率成为程序性能的决定性因素。据我的了解，目前比较成熟的查找算法主要有顺序查找、二分查找、哈希表查找等。顺序查找的算法复杂度为O(n)；二分查找的算法复杂度为O(logn)，但需要事先排序；哈希表查找的复杂度为O(1)。本程序采用效率最高的哈希表查找算法。4汉字编码格式：汉字编码格式：UTF-8UTF-8中文处理和英文处理的一个很大不同就在于编码格式的复杂性。常见的中文编码格式有GB2312，GB18030，GBK，Unicode等等。同样的中文字符，在不同的汉字编码格式中，可能有不同的二进制表示。因此编程做字符串匹配时，通常要求统一的编码格式。在linux下可以用file命令查看文本文件的编码格式。经过检查，发现老师提供的词典和语料属于不同的编码格式，直接做字符串匹配可能会有问题。考虑到UBUNTU以UTF-8作为默认编码格式，我索性使用 enconv 命令将词典和语料都转换成 UTF-8格式。下面简要介绍一下UTF-8格式。前面 提到的 Unicode 的学名 是 Universal Multiple-Octet Coded Character Set，简称为UCS。UCS 可以看作是Unicode Character Set的缩写。UCS只是规定如何编码，并没有规定如何传输、保存这个编码。UTF-8是被广泛接受的方案。UTF-8 的一个特别的好处是它与 ISO-8859-1 完全兼容。UTF“是 UCS Transformation Format”的缩写。UTF-8就是以8位为单元对UCS 进行编码。从UCS-2到UTF-8的编码方式如下：UCS-2编码(16进制)UTF-8字节流(二进制)0000 007F0 xxxxxxx0080 07FF110 xxxxx 10 xxxxxx0800 FFFF1110 xxxx 10 xxxxxx 10 xxxxxx“”例如 汉 字的Unicode 编码是6C49。6C49在0800-FFFF 之间，所以肯定要用3字节模板了：1110 xxxx 10 xxxxxx 10 xxxxxx。将 6C49 写成二进制是：0110 110001 001001，用这 个比 特流 依次 代替 模板 中的 x，得 到：11100110 10110001 10001001，即E6 B1 89。所以，就有了这个结论：汉字的 UTF-8 编码是 3 字节的 。然而，语料库中出现的字符并非都是汉字。比如半角空格、外国人名字间隔符等。如果把所有字单元都视为3字节，就要出错了。这是编程时必须考虑的问题。5程序流程图程序流程图67程序源代码程序源代码/*segment.cpp-中文分词程序 *功能：）中文词典分词（逆向最大匹配）*）数字分词 *）西文分词 *）时间分词 *用法：*./segment ARTICAL *范例：*./segment 1998-01-qiefen-file.txt.utf8 *屏幕输出：*词典读入完毕，耗时 0.000776 s *分词完毕，耗时 3.18s*分词结果保存在result.txt.utf8中。*注意：）本程序只能处理utf-8文本，其他格式的文本请用iconv或enconv转换成utf-8格式。*）程序运行需要dict/CoreDict.txt.utf8，dict/number.txt.utf8，dict/unit.txt.utf8三个文件。*参考了以下文章，特此感谢！*http:/ on:2010-11-30 *Author:xuweilin */#include#include#include#include#include#include#include#include#define MaxWordLength 12/最大词长字节（即 4 个汉字）8#define Separator /词界标记#define UTF8_CN_LEN 3 /汉字的 UTF-8 编码为 3字节 using namespace std;using namespace _gnu_cxx;namespace _gnu_cxx template struct hash size_t operator()(const std:string&x)const return hash()(x.c_str();hash_map wordhash;/词典 hash_map numberhash;/数字和字母 hash_map unithash;/时间单位/读入词典，以及数字、字母、时间单位集 void get_dict(void)string strtmp;/读取词典的每一行 string word;/保存每个词 typedef pair sipair;ifstream infile(dict/CoreDict.txt.utf8);if(!infile.is_open()cerr Unable to open input file:wordlexicon -bailing out!word;/读入每行第一个词 wordhash.insert(sipair(word,1);/插入到哈希中 infile.close();9infile.open(dict/number.txt.utf8);if(!infile.is_open()cerr Unable to open input file:wordlexicon -bailing out!word;/读入每行第一个词 numberhash.insert(sipair(word,1);/插入到哈希中 infile.close();infile.open(dict/unit.txt.utf8);if(!infile.is_open()cerr Unable to open input file:wordlexicon -bailing out!word;/读入每行第一个词 unithash.insert(sipair(word,1);/插入到哈希中 infile.close();/删除语料库中已有的分词空格，由本程序重新分词 string eat_space(string s1)int p1=0,p2=0;int count;string s2;while(p2 p1)/s2+=s1.substr(p1,p2-p1);/p2+=3;/p1=p2;/else/p2+=3;/删除半角空格 if(s1p2-0 x20=0)if(p2p1)s2+=s1.substr(p1,p2-p1);p2+;p1=p2;else p2+;s2+=s1.substr(p1,p2-p1);return s2;/用词典做逆向最大匹配法分词 string dict_segment(string s1)string s2=;/用s2存放分词结果 while(!s1.empty()int len=(int)s1.length();/取输入串长度 if(len MaxWordLength)/如果输入串长度大于最大词长 len=MaxWordLength;/只在最大词长范围内进行处理 /string w=s1.substr(0,len);/（正向用）将输入串左边等于最大词长长度串取出作为候选词 string w=s1.substr(s1.length()-len,len);/逆向用 int n=(wordhash.find(w)!=wordhash.end();/在词典中查找相应的词 while(len UTF8_CN_LEN&n=0)/如果不是词 len-=UTF8_CN_LEN;/从候选词左边减掉一个汉字,将剩下的部分作为候选词 11/w=w.substr(0,len);/正向用 w=s1.substr(s1.length()-len,len);/逆向用 n=(wordhash.find(w)!=wordhash.end();/s2+=w+Separator;/(正向用）将匹配得到的词连同词界标记加到输出串末尾 w=w+Separator;/(逆向用)s2=w+s2;/(逆向用)/s1=s1.substr(w.length(),s1.length();/(正向用)从 s1-w 处开始 s1=s1.substr(0,s1.length()-len);/(逆向用)return s2;/中文分词，先分出数字和字母以及时间，再交由词典分词，具有一定的智能。string cn_segment(string s1)/先分出数字和字母 string s2;int p1,p2;p1=p2=0;while(p2 s1.length()while(p2 =(s1.length()-3)&numberhash.find(s1.substr(p2,3)=numberhash.end()/不是数字或字母 p2+=3;s2+=dict_segment(s1.substr(p1,p2-p1);/之前的句子用词典分词/将数字/字母和单位分出来 p1=p2;p2+=3;while(p2 =(s1.length()-3)&numberhash.find(s1.substr(p2,3)!=numberhash.end()/是数字或字母 p2+=3;if(p2=(s1.length()-3)&unithash.find(s1.substr(p2,3)!=unithash.end()/是单位 p2+=3;s2+=s1.substr(p1,p2-p1)+Separator;12p1=p2;return s2;/在执行中文分词前，过滤半角空格以及其他非 UTF-8 字符 string seg_analysis(string s1)string s2;string s3=;int p1=0;int p2=0;int count;while(p2 4)&0 xe)0 xe)/过滤非 utf-8 字符 count=0;do p2+;count+;while(s1p24)&0 xe)0 xe)&p2 s1.length();s2=s1.substr(p1,p2-count-p1);/特殊字符前的串 s3+=cn_segment(s2)+s1.substr(p2-count,count)+Separator;/特殊字符，不要用汉字分词处理 if(p2=s1.length()/这个等号!当特殊符号是最后一个字符时！s1=s1.substr(p2,s1.length()-p2);/剩余串 p1=p2=0;else p2+=UTF8_CN_LEN;if(p2!=0)s3+=cn_segment(s1);return s3;int main(int argc,char*argv)13 if(argv1=NULLNULL)cout nnsegment.cpp-中文分词程序nn *nn *功能：）中文词典分词（逆向最大匹配）nn *）数字分词nn *）西文分词nn *）时间分词nn *用法：nn *./segment ARTICALnn *范例：nn *./segment 1998-01-qiefen-file.txt.utf8nn *!格外注意：本程序只能处理 utf-8 文本，其他格式的文本请用 iconv 或 enconv 转换成utf-8 格式。nn;exit(0);clock_t start,finish;double duration;start=clock();get_dict();finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout 词典读入完毕，耗时 duration s endl;string strtmp;/用于保存从语料库中读入的每一行 string line;/用于输出每一行的结果 ifstream infile(argv1);/打开输入文件 if(!infile.is_open()/打开输入文件失败则退出程序 cerr Unable to open input file:argv1 -bailing out!endl;exit(-1);ofstream outfile1(result.txt.utf8);/确定输出文件 if(!outfile1.is_open()cerr Unable to open file：SegmentResult.txt -bailing out!endl;exit(-1);14 start=clock();cout 正在分词并输出到文件，请稍候.endl;while(getline(infile,strtmp)/读入语料库中的每一行并用最大匹配法处理 line=eat_space(strtmp);/cout NOSPACE with endl line endl;line=seg_analysis(line);/调用分词函数进行分词处理/cout result endl line endl;outfile1 line endl;/将分词结果写入目标文件 finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout 分词完毕，耗时 duration s endl;cout 分词结果保存在 result.txt.utf8中。endl;return 0;15五、结果和性能分析五、结果和性能分析分词结果示例分词结果示例程序编码基本正确，实现了程序设计中提到的两种分词策略，分词结果就在预料之中。第 100 行原文：据最新统计，年月至月份，来华旅游人数达万多人次，国际旅游收入达亿多美元，分别较上年同期增长和，预计全年来华旅游入境人数约万人次，旅游创汇达亿美元，再创新纪录，国内旅游人数及收入也比上年有大幅增长。分词结果：据 最新 统计，年 月 至 月 份，来华 旅游 人数 达 万 多 人次，国际 旅游 收入 达 亿 多 美元，分别 较 上年 同期 增长 和 ，预计 全年 来华 旅游 入境 人数 约 万 人次，旅游 创汇 达 亿 美元，再 创新纪录，国内 旅游 人数 及 收入 也 比 上年 有 大幅 增长。结果分析：程序实现了词典分词，还能识别出复杂数字、时间等词。第1994行原文：数字移动通讯新阶段分词结果：数字 移动 通讯 新 阶段 分析：程序能识别英文单词。16第19096 行原文：参加调查小组的世界卫生组织官员丹尼尔拉万奇博士说，中国政府对病毒高质量的监视活动给他留下了深刻的印象。他同时表示，今后对这种病毒的监控仍不能放松。分词结果：参加 调查 小组 的 世界 卫生 组织 官员 丹 尼 尔 拉 万 奇 博士 说，中国 政府 对 病毒 高 质量 的 监视 活动 给 他 留下 了 深刻 的 印象。他 同时 表示，今后 对 这种 病毒 的 监控 仍 不 能 放松。分析：程序能识别复杂英文词组性能分析性能分析$./segment 1998-01-qiefen-file.txt.utf8 词典读入完毕，耗时 0.22 s 正在分词并输出到文件，请稍候.分词完毕，耗时 3.49s 分词结果保存在result.txt.utf8 中。程序运行输出结果如上所示。据显示，本机的运行时间为3.49。在分词策略不变的情况下，仍有优化空间。影响性能的几个因素：1、查词典。程序使用哈希表查词典，复杂度为 O(1),剩余优化空间不多。但是，若词条数目太多，导致哈希表冲突经常发生，复杂度就不是 O(1)了。因此，当词典很大时，可以把不同长度的词条分开到不同的哈希表存储，以减少冲突。经过测试本程序若采用这个优化方案，可以减少数百毫秒的执行时间。为增加代码可读性，这个优化方案没有写入程序最终版。2、删除空格操作。因为语料库是已经分好词的内容，所以完整的分词包括删除空格操作。经过测试，若没有这项操作，可以减少数百毫秒的执行时间。3、过程分遍执行。为了简化程序设计，删除空格、过滤非UTF-8 字符、确定文法分词、词典分词等四个过程设计为多遍执行，即前一项的输出作为后一项的输入。如果分词过程合并为一遍，可以节省内存拷贝时间。4、汉字编码格式。系列的汉字编码为2字节，而 UTF-8 的汉字编码为 3字节，采用UTF8编码时，文件 I/O、字符匹配的时间都增加了 50。17六、有待解决的问题六、有待解决的问题本程序的分词结果并不完全令人满意。下面就是一些失败的分词结果。第行原文：迈向充满希望的新世纪一九九八年新年讲话（附图片张）分词结果：迈向 充满 希望 的 新 世纪 一九九八年 新年 讲话（附 图片 张）问题：“”是两条横线组成的破折号，是确定文法的词，暂未包含在程序问题：“”是两条横线组成的破折号，是确定文法的词，暂未包含在程序处理范围。处理范围。第4 行原文：月日，中共中央总书记、国家主席江泽民发表年新年讲话迈向充满希望的新世纪。（新华社记者兰红光摄）分词结果：月 日，中共中央 总书记、国家 主席 江 泽 民 发表 年 新年 讲话 迈向 充满 希望 的 新 世纪 。（新华社 记者 兰 红 光 摄）问题：“江泽民”应为一个词。人民日报 是党的机关报，党和国家领导人的名问题：“江泽民”应为一个词。人民日报 是党的机关报，党和国家领导人的名字出现的频率很高，这种错误是不能容忍的。这可以通过丰富词典内容，也可以通过字出现的频率很高，这种错误是不能容忍的。这可以通过丰富词典内容，也可以通过统计方法来解决。统计方法来解决。第 131 行原文：本报伊斯兰堡月日电记者王南报道：巴基斯坦穆斯林联盟（谢里夫派）候选人、原最高法院大法官穆罕默德拉斐克塔拉尔，今天在巴国民议会、参议院以及各省议会选举中，当选巴基斯坦第九任总统，任期年。塔拉尔将于明天宣誓就职。分词结果：本报 伊斯兰堡 月 日 电 记者 王 南 报道：巴基斯坦 穆斯林 联盟（谢里夫派）候选人、原 最高 法院 大法官 穆 罕 默 德 拉 斐 克 塔 拉 尔，今天 在 巴 国民 议会、参议院 以及 各省 议会 选举 中，当选 巴基斯坦 第 九 任 总统，任期 年。塔 拉 尔 将 于 明天 宣誓 就职。问题：“穆罕默德问题：“穆罕默德 拉斐克拉斐克 塔拉尔”是一个以“塔拉尔”是一个以“”为隔断的人名，不能再分词为隔断的人名，不能再分词。因为“因为“”不是不是 UTF-8UTF-8 字符，本程序暂时没有实现外国人名分词。字符，本程序暂时没有实现外国人名分词。第9 行片段：在这一年中，中国的外交工作取得了重要成果。分词结果：在 这 一年 中，中国 的 外交 工作 取 得了 重要 成果。问题：“取得了”应分词为“取得 了”，而不是“取 得了”。未实现语义消歧问题：“取得了”应分词为“取得 了”，而不是“取 得了”。未实现语义消歧。18七、实验总结七、实验总结分词是中文自然语言处理的基础，在现实中已经得到广泛应用。比如，Google 的Chrome浏览器就内置了中文分词功能。如上图，我们可以注意到，在Chrome中双击无链接文本时，Chrome选中的不是一个字，也不是一句话，而是一个词。当然，中文分词在数据挖掘等方面的应用就更加明显了。掌握自然语言处理的基本知识，已经成为 IT 行业对计算机专业学生的基本要求。虽然我曾经系统学习过 算法 数据结构 等基础课程，但编写程序时仍然遇到了很多问题，仅在汉字编码的问题上就纠缠了很久。幸而在搜索引擎和开源社区以及开源软件细致的文档的帮助下，我攻克了一个又一个难题，最终做出了分词程序雏形。尽管它在功能和性能上都没有达到国际先进水平，但确实是我在学习 自然语言处理 这门课中产生的阶段性成果，是非常值得欣慰的。自然语言处理是一个正在快速发展的学科，但愿我有朝一日能在这个领域大显身手。19