实验报告下载链接：
/download/qq_37636795/16337679
南华大学
计算机科学与技术学院
实验报告
（ ~ 学年度 第二学期 ）
课程名称 搜索引擎
实验名称 中文分词
姓名 学号
专业
地点 8-606B 教师 肖建田
目录
一.实验目的 3
二.实验环境 3
三.实验材料 3
四.实验设计 3
一.分词策略 3
词典逆向最大匹配法 4
二.程序设计 5
汉字编码格式:UTF-8 6
算法流程图 9
程序源代码 10
五．结果和性能分析 13
分词结果示例 13
性能分析 13
六．有待解决的问题 14
七．实验总结 15
一、实验目的
了解中文分词的意义
掌握中文分词的基本方法
二、实验环境
eclipse
三、实验材料
单句:你好！请问你叫什么名字?
四、实验设计
一、分词策略
对于中文分词技术的实现，有许多算法可以完成，目前大致可以把算法分为三大类：
1.基于字符串匹配的分词方法；
2.基于理解的分词方法；
3.基于统计的分词方法。
其中，基于字符串匹配的分词方法是把中文句子按照一定的策略将待分析的汉字串与已知且足够大的中文词典库进行比对，从而达到分词效果。而我们通常使用最多的分词策略，大致有三类，正向最大匹配法，逆向最大匹配法和最少切分法。
基于理解的分词方法是指让计算机模拟人对句子的理解进行分词。基于统计的分词方法是指找出上下文中出现较多的汉字组合，将这些组合视为词汇，代入到原文中进行分词。
在这里，就使用字符串匹配的分词方法，利用逆向最大匹配的策略，对中文句子进行简单的分词。
词典逆向最大匹配法
词典逆向最大匹配法完成分词的大部分工作，设计思路是这样的：
1、 将词典的每个词条读入内存，最长是 4 字词，最短是 1 字词；
2、 从语料中读入一段（一行）文字，保存为字符串；
3、 如果字符串长度大于 4 个中文字符，则取字符串最右边的 4 个中文字符，作
为候选词；否则取出整个字符串作为候选词；
4、 在词典中查找这个候选词，如果查找失败，则去掉这个候选词的最左字，重
复这步进行查找，直到候选词为 1 个中文字符；
5、 将候选词从字符串中取出、删除，回到第 3 步直到字符串为空；
6、 回到第 2 步直到语料已读完。
二、程序设计
算法：逆向最大匹配法
逆向最大匹配法大致思想为：将整个字符串作为一个“词组”带入到词典中进行比对，若不成功，删除第一个字符，继续进行如此操作，直到成功或者只剩下最后一个字，再把结果放入一个字符串的数组中，最后删除原句中的结果，继续上面的操作。下面我将用一个例子解释这个操作：
原句：今晚月亮真漂亮啊
词典：“今晚”，“月亮”，“漂亮”
第一次代入：今晚月亮真漂亮啊（在词典中没有该词汇，删除首字符继续比对）
删除首字符：晚月亮真漂亮啊（在词典中没有该词汇，删除首字符继续比对）
删除首字符：月亮真漂亮啊（在词典中没有该词汇，删除首字符继续比对）
删除首字符：亮真漂亮啊（在词典中没有该词汇，删除首字符继续比对）
…
删除首字符：啊（在词典中没有该词汇，只剩下一个字，放入结果数组，并删除位于句尾的最后这个字，进行第二次代入）
第二次代入：今晚月亮真漂亮（在词典中没有该词汇，删除首字符继续比对）
…
删除首字符：漂亮（在词典中找到词汇“漂亮”，放入结果数组，并删除位于句尾的结果“漂亮”，进行第三次代入）
汉字编码格式：UTF-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 – 007F 0xxxxxxx
0080 – 07FF 110xxxxx 10xxxxxx
0800 – FFFF 1110xxxx 10xxxxxx 10xxxxxx
例如“汉”字的 Unicode 编码是 6C49。6C49 在 0800-FFFF 之间，所以肯定要用 3
字节模板了：1110xxxx 10xxxxxx 10xxxxxx。将 6C49 写成二进制是：0110 110001
001001 ， 用 这 个 比 特 流 依 次 代 替 模 板 中 的 x ， 得 到 ： 11100110 10110001 10001001，即 E6 B1 89。 所以，就有了这个结论： 汉字的UTF-8编码是
3字节的。然而，语料库中出现的 字符并非都是汉字。比如半角空格、外国人名字间隔符等。如果把所有字单元都视为 3 字节，就要出错了。这是编程时必须考虑的问题。
算法流程图
程序源代码
public class secondwork {
public static void main(String args[])
{
String[] cs = {“你好”,“请问”,“什么”,“名字”};//词典
String a = “你好！请问你叫什么名字？”;
System.out.print(“原句：”);
System.out.print(a + ‘\n’);
System.out.print(“拆分后为：”);
String[] cs2 = new String[100]; //结果数组
int jud=0;//找到匹配字符串与否的标志
int j=0;
String temp=null;//初始化临时字符串
for(;a.length()>0;)
{
for(int i = 0;i<a.length();i++)
{
temp = a.substring(i);//每次截取掉首个字符
if(isin(cs,temp) == true)//如果目标字符串在数组中
{
cs2[j] = temp;
jud = 1;
int number = temp.length();
a = a.substring(0,a.length()-number);
}
}
if(jud == 0)//没有找到匹配字符串
{
cs2[j] = a.substring(a.length()-1,a.length());//将最后一个元素放在cs2里面
a = a.substring(0, a.length()-1);//截掉最后一个元素继续循环。
}
jud = 0;
j++;
}
for(;j >= 0;j–)
{
if(cs2[j] != null)
System.out.print(cs2[j]+" ");
}
}
/** 下面为判断字符串是否在词典中的函数方法*/static public boolean isin(String[] cs,String temp)//判断目标字符串是否在对比字符串数组中{int i;for(i = 0;i<cs.length;){if(temp.equals(cs[i]))i = cs.length+1;elsei++;}if(i == cs.length+1)return true;elsereturn false;}
}
五、结果和性能分析
分词结果示例
程序编码基本正确，实现了程序设计中提到的分词策略，分词结果就在预料之中。
性能分析
单句读入完毕，耗时0.03S
据显示，本机的运行时间为 0.03 ｓ。在分词策略不变的情
况下，仍有优化空间。
影响性能的几个因素：
逆向最大匹配法的思想使得这个策略十分容易实现，具有非常明显的简单易懂的特点，实现代码也不算太长。但是，逆向最大匹配算法对于一些比较特殊的句子，分词准确率可能会降低。例如下面这个句子：
爱迪生发明了很多东西
如果你的词典足够大，你会发现，按照逆向最大匹配的方法，计算机会将“明了”看做一个中文词汇分隔出来，继续向下走，计算机将分出词汇“生发”，这样一来，就会造成 “爱迪 生发 明了” 的错误。
我们还有正向最大匹配法，我们可以用正向最大匹配法，对这个句子进行分词，结果就对了。但是正向最大匹配法也会出现bug，怎么办呢，我们可以将正向和逆向结合，这样就是另外一种分词策略：双向最大匹配法，大大降低了出现bug的概率。
六、有待解决的问题
1.对于一些比较特殊的句子，分词准确率可能会降低。
2.如果你的词典足够大，你会发现，按照逆向最大匹配的方法，计算机会将一些词语当做特定词语单个标明出来。
七、实验总结
任何算法都有它的优劣性，我们在使用算法时，不仅要使用算法，更要去考虑怎么样去优化算法，使算法更加贴合自己的需求。
附实验作业五源码：
设计并实现一个中文分词的算法
# -- coding utf-8 --__author__ = 'Zhao'import reimport operator# --------------- in this part we save the list as list ---------------path = 'Usersappledesktop' # 这里可以随便改你存放的文件夹fp = open(path + 'list.txt') # list.txt这里可以放你的词表的文件名ori = fp.readlines()# ori is the list with out any operationcopy = []for x in orix = re.sub(r'n', '', x)copy.append(x)# in this part we change the format in a into standard format and save as copyfp.close()# we close the file, then we can run the list totally in this programcopy.sort()# --------------- this part end ---------------# in this part we know the average length in this list is 2, thus we set step as 5.# In that case, we can contain at least one word.# totally, there are 56064 words in this list and only 56 is longer than 5.# In that case, 5 can be a reasonable step for this program.# sum = 0# num = 0# for x in copy#sum += len(x)#num += 1# average = (int)(sumnum)# print(average, ' ', num);# max_lenth = 0# for x in copy#if max_lenth len(x)# max_lenth = len(x)## print(max_lenth)# number = 0# for x in copy#if len(x) 5# number += 1## print(number)# --------------- the upper is the calculation in the preparation ---------------str_input = input(请输入一个段落：n)str_input = re.sub(r',', , str_input)str_input = re.sub(r'，', , str_input)str_input = re.sub(r'.', , str_input)str_input = re.sub(r'。', , str_input)str_input = re.sub(r'——', , str_input)str_input = re.sub(r'……', , str_input)str_input = re.sub(r'！', , str_input)str_input = re.sub(r'!', , str_input)str_input = re.sub(r'', , str_input)str_input = re.sub(r'？', , str_input)str_input = re.sub(r';', , str_input)str_input = re.sub(r'；', , str_input)str_input = re.sub(r' ', , str_input)# change all the punctuation as blank, however, we may split falsely.# Words get around, the step can also split at wrong place, so, I do not fix this mistake.str_head = 0str_tail = len(str_input)ptr = 5temp = 0step = 5while temp str_tail-1flag = 0ptr = 5while flag != 1in_put = str_input[temptemp + ptr]tail = len(copy)head = 0half = int((tail + head) 2)while tail != half and head != halfif operator.lt(copy[half], in_put)# 如果字符组的一半比input小head = halfhalf = int((tail + head) 2)elif operator.gt(copy[half], in_put)# 如果字符组的一半比input大tail = halfhalf = int((tail + head) 2)elseprint(in_put, end='')flag = 1temp += len(in_put)breakif ptr == 0 and temp = len(str_input)-1print(str_input[temp], end='')temp += 1flag = 1if flag == 0ptr -= 1
如果觉得《大数据搜索引擎原理分析——设计并实现一个中文分词的算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
