1、,汉语分词:最大匹配方法,张月（李正华指导）2015.9.15,中文分词的目的是将汉字序列切分为词序列举例说明：输入句子：他是研究生物化学的。可能的分词：他 是 研究生 物化 学 的 。 他 是 研究生 物 化学 的 。 他 是 研究 生物 化学 的 。合理答案：他 是 研究 生物 化学 的 。,分词任务,从左到右寻找词的最大匹配（每次都贪心的找一个最长的词典词）我们有一个词典，用于存放所有可能的词语，即除了单字，分词结果中的每个词均要在词典中出现。,正向最大匹配算法,从左到右寻找词的最大匹配从当前位置开始，向右截取最大长度，组成当前词；和字典中的词逐一进行匹配；若匹配成功，则进行下次匹配，下
2、次匹配的当前位置则为这次词后面的那个字。如果未能匹配，就缩短长度（长度减一）重新截取，直到当前词与词典中的词匹配或者当前词是单字；,正向最大匹配算法,从左到右寻找词的最大匹配,正向最大匹配算法,例子：我是中国人 词典中包括【中国、中国人】假设：最大词长为3,正向最大匹配算法,例子：我是中国人 第一轮：第一次：我是中是选取的词，在词典中 未找到匹配项 第二次：我是是选取的词，在词典中未 找到匹配项 第三次：我是选取的词，是单字，匹配 成功,正向最大匹配算法,例子：我/是中国人 第二轮：第一次：是中国是选取的词，在词典中 未找到匹配项 第二次：是中是选取的词，在词典中未 找到匹配项 第三次：是是选
3、取的词，是单字，匹配 成功,正向最大匹配算法,例子：我/是/中国人/ 第三轮：第一次：中国人是选取的词，在词典中 找到匹配项，匹配成功。 至此，短句中所有字匹配结束，该短句分词结束。,正向最大匹配算法,从右到左寻找词的最大匹配 与正向最大匹配的区别在于，从句子的末尾开始，向左边截取一定的长度去匹配。,逆向最大匹配算法,从右到左寻找词的最大匹配,逆向最大匹配算法,例子：我是中国人 第一轮：第一次：中国人是选取的词，在词典中 找到匹配项，匹配成功,逆向最大匹配算法,例子：我是/中国人 第二轮：第一次：因为剩余字数已不足3，小于假 定的最大词长，所以选择我是， 在词典中未找到匹配项 第二次：是是选取
4、的词，是单字，匹配 成功,逆向最大匹配算法,例子：我/是/中国人 第三轮：第一次：因为剩余字数已不足3，小于假 定的最大词长，所以选择我， 是单字，匹配成功 至此，短句中所有字匹配结束，该短句 分词结束。,逆向最大匹配算法,给定人工标注的分词答案，评价某一算法给出的结果。正确率(Precision) = 正确识别的词数 / 识别出的个体总数召回率(Recall) = 正确识别的个体总数 / 测试集中存在的个体总数F值 = 正确率* 召回率 * 2 / (正确率 + 召回率),分词算法评价：正确率/召回率/F值,思考：评价程序应该怎么写？,utf-8是不定长的，根据左侧位1的个数来决定占用了几个
5、字节，中文一般占2-4个字节,UTF-8编码,gbk的编码方式是中文占两个字节，英文占一个字节,根据第一个字节的最高位来判断如果第一个字节的最高位是1，则是两个字节连在一起为一个字符，否则一个字节为一个字符中文的编码范围 第一个字节 | 第二个字节 0x81-0xFE(129-254) | 0x40-0xFE(64-254),GBK编码,数据格式,四个编程任务（编程语言不限，Linux上运行）,1. 构建词典（3分）给一个人工分好词的文件data.conll，构建一个词典，输出到一个文件中，起名为word.dict（格式自定义）2. 构建毛文本（2分）将data.conll文件中的格式修改为：每行一句话，词语之间无空格，起名为data.txt,四个编程任务（编程语言不限，Linux上运行）,3. 前向（5分）或（二者只可以选一个）后向（7分）最大匹配分词算法给定词典word.dict，对data.txt进行分词，结果输出到data.out中（格式自定义）4. 评价程序（7分）对比data.conll和data.out，给出算法的P/R/F指标。,谢 谢 ！,
