从右到左寻找词的最大匹配.pptVIP

汉语分词:最大匹配方法 张月（李正华指导） 2015.9.15 中文分词的目的是将汉字序列切分为词序列 举例说明： 输入句子：他是研究生物化学的。 可能的分词：他 是 研究生 物化 学 的 。 他 是 研究生 物 化学 的 。 他 是 研究 生物 化学 的 。 合理答案：他 是 研究 生物 化学 的 。 分词任务 从左到右寻找词的最大匹配（每次都贪心的找一个最长的词典词） 我们有一个词典，用于存放所有可能的词语，即除了单字，分词结果中的每个词均要在词典中出现。 正向最大匹配算法 从左到右寻找词的最大匹配 从当前位置开始，向右截取最大长度，组成当前词； 和字典中的词逐一进行匹配； 若匹配成功，则进行下次匹配，下次匹配的当前位置则为这次词后面的那个字。 如果未能匹配，就缩短长度（长度减一）重新截取，直到当前词与词典中的词匹配或者当前词是单字； 正向最大匹配算法 从左到右寻找词的最大匹配 正向最大匹配算法 例子：我是中国人 词典中包括【中国、中国人】 假设：最大词长为3 正向最大匹配算法 例子：我是中国人 第一轮： 第一次：我是中是选取的词，在词典中 未找到匹配项 第二次：我是是选取的词，在词典中未 找到匹配项 第三次：我是选取的词，是单字，匹配 成功 正向最大匹配算法 例子：我/是中国人 第二轮： 第一次：是中国是选取的词，在词典中 未找到匹配项 第二次：是中是选取的词，在词典中未 找到匹配项 第三次：是是选取的词，是单字，匹配 成功 正向最大匹配算法 例子：我/是/中国人/ 第三轮： 第一次：中国人是选取的词，在词典中 找到匹配项，匹配成功。 至此，短句中所有字匹配结束，该短句分词结束。 正向最大匹配算法 从右到左寻找词的最大匹配 与正向最大匹配的区别在于，从句子的末尾开始，向左边截取一定的长度去匹配。 逆向最大匹配算法 从右到左寻找词的最大匹配 逆向最大匹配算法 例子：我是中国人 第一轮： 第一次：中国人是选取的词，在词典中 找到匹配项，匹配成功 逆向最大匹配算法 例子：我是/中国人 第二轮： 第一次：因为剩余字数已不足3，小于假 定的最大词长，所以选择我是， 在词典中未找到匹配项 第二次：是是选取的词，是单字，匹配 成功 逆向最大匹配算法 例子：我/是/中国人 第三轮： 第一次：因为剩余字数已不足3，小于假 定的最大词长，所以选择我， 是单字，匹配成功 至此，短句中所有字匹配结束，该短句 分词结束。 逆向最大匹配算法 给定人工标注的分词答案，评价某一算法给出的结果。 正确率(Precision) = 正确识别的词数 / 识别出的个体总数 召回率(Recall) = 正确识别的个体总数 / 测试集中存在的个体总数 F值 = 正确率* 召回率 * 2 / (正确率 + 召回率) 分词算法评价：正确率/召回率/F值 思考：评价程序应该怎么写？ utf-8是不定长的，根据左侧位1的个数来决定占用了几个字节，中文一般占2-4个字节 UTF-8编码 utf-8可以根据字的第一个字节移位推出长度的 0xxxxxxx占1个字节 110xxxxx 10xxxxxx占2个字节 1110xxxx 10xxxxxx 10xxxxxx占3个字节 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx占4个字节 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分）或（二者