第四章分词补充课件Word格式.docx
《第四章分词补充课件Word格式.docx》由会员分享，可在线阅读，更多相关《第四章分词补充课件Word格式.docx（35页珍藏版）》请在冰点文库上搜索。
该数据存储在“e”结点。
对于“i”的右树，按照逻辑，选择“on”作为中间值，并且创建“o”结点以及它的直接后继结点“n”。
最终的三叉树如图4-3所示：
图4-3三叉树
垂直的虚线代表一个父节点的下面的直接的后继结点。
只有父节点和它的直接后继节点才能形成一个数据单元的关键字；
“i”和“s”形成关键字“is”，但是“i”和“b”不能形成关键字，因为它们之间仅用一条斜线相连，不具有直接后继关系。
图4-3中带圈的节点为终止节点，如果查找一个词以终止节点结束，则说明三叉树包含这个词。
TernarySearchTrie本身存储关键字到值的对应关系，可以当作HashMap对象来使用。
关键字按照字符拆分成了Node，以TSTNode的实例存在。
值存储在TSTNode的data属性中。
TSTNode的实现如下：
publicfinalclassTSTNode{
/**节点的值*/
publicDatadata=null;
//data属性可以存储词原文和词性、词频等相关的信息
protectedTSTNodeloNode;
//左边节点
protectedTSTNodeeqNode;
//中间节点
protectedTSTNodehiNode;
//右边节点
protectedcharsplitchar;
//本节点表示的字符
/**
*构造方法
*
*@paramsplitchar该节点表示的字符
*/
protectedTSTNode（charsplitchar）{
this.splitchar=splitchar;
}
publicStringtoString（）
{
return"
splitchar:
"
+splitchar;
}
基本的查找词典过程是：
输入一个词，返回这个词对应的TSTNode，如果该词不在词典中则返回空。
查找词典的过程中，从树的根节点匹配Key。
Key按Char从前往后匹配。
charIndex表示Key的当前要比较的Char的位置。
匹配过程如下：
protectedTSTNodegetNode（Stringkey,TSTNodestartNode）{
if（key==null）{
returnnull;
intlen=key.length（）;
if（len==0）
TSTNodecurrentNode=startNode;
//匹配过程中的当前节点的位置
intcharIndex=0;
charcmpChar=key.charAt（charIndex）;
intcharComp;
while（true）{
if（currentNode==null）{
returnnull;
}
charComp=cmpChar-currentNode.splitchar;
if（charComp==0）{
charIndex++;
if（charIndex==len）{
returncurrentNode;
}
else
{
cmpChar=key.charAt（charIndex）;
currentNode=currentNode.eqNode;
}elseif（charComp<
0）{
currentNode=currentNode.loNode;
}else{
currentNode=currentNode.hiNode;
三叉树的创建过程如下：
TSTNodecurrentNode=root;
//从树的根节点开始查找
//从词的开头匹配
intcharComp=key.charAt（charIndex）-
currentNode.splitchar;
//比较词的当前字符与节点的当前字符
if（charComp==0）{//相等
if（charIndex==key.length（））{
if（currentNode.eqNode==null）{
currentNode.eqNode=
newTSTNode（key.charAt（charIndex））;
0）{//小于
if（currentNode.loNode==null）{
currentNode.loNode=
}else{//大于
if（currentNode.hiNode==null）{
currentNode.hiNode=
相对于查找过程，创建过程在搜索的过程中判断链接的空值，而不是一开始就判断。
1.1.2中文分词的原理
分词的两类方法：
●机械匹配的方法：
例如正向最大长度匹配（ForwardMaximumMatch）的方法和逆向最大长度匹配（ReverseMaximumMatching）的方法。
●统计的方法：
例如最大概率分词方法和最大熵的分词方法等。
正向最大长度匹配的分词方法实现起来很简单。
每次从词典找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词，如果词典中没有词匹配上，则按单字切分。
下面给出正向对大匹配（MaximumMatchingMethod,MM）算法基本思想：
①设自动分词词典中最长词条所含汉字个数为I；
②取被处理材料当前字符串序数中的I个字作为匹配字段，查找分词词典。
若词典中有这样的一个I字词，则匹配成功，匹配字段作为一个词被切分出来，转⑥；
③如果词典中找不到这样的一个I字词，则匹配失败；
④匹配字段去掉最后一个汉字，I--；
⑤重复②-④，直至切分成功为止；
⑥I重新赋初值，转②，直到切分出所有词为止。
例如，Trie树结构的词典中包括如下的8个词语：
大大学大学生活动生活中中心心
为了形成平衡的Trie树，把词先排序，排序后为：
中中心大大学大学生心活动生活
按平衡方式生成的词典Trie树如下图，其中粗黑显示的节点可以做为匹配终止节点：
输入：
“大学生活动中心”，首先匹配出“大学生”，然后匹配出“活动”，最后匹配出“中心”。
切分过程如下：
已匹配上的结果
待匹配串
NULL
大学生活动中心
大学生
活动中心
大学生/活动
中心
大学生/活动/中心
最后分词结果为：
“大学生/活动/中心”。
在最大长度匹配的分词方法中，需要用到从指定字符串返回指定位置的最长匹配词的方法。
例如，当输入串是“大学生活动中心”，则返回“大学生”这个词，而不是返回“大”或者“大学”。
从Trie树搜索最长匹配单词的方法如下：
publicStringmatchLong（Stringkey,intoffset）{
Stringret=null;
if（key==null||rootNode==null||"
.equals（key））{
returnret;
TSTNodecurrentNode=rootNode;
intcharIndex=offset;
returnret;
intcharComp=key.charAt（charIndex）-currentNode.spliter;
if（currentNode.data!
=null）{
ret=currentNode.data;
//候选最长匹配词
returnret;
//已经匹配完
测试方法：
Stringsentence="
大学生活动中心"
;
intoffset=0;
Stringret=dic.matchLong（sentence,offset）;
System.out.println（sentence+"
match:
+ret）;
返回结果：
大学生活动中心match:
正向最大长度分词的实现代码如下：
publicvoidwordSegment（Stringsentence）//传入一个字符串作为要处理的对象
{
intsenLen=sentence.length（）;
//首先计算出传入的这句话的字符长度
inti=0;
//控制匹配的起始位置
while（i<
senLen）//如果i小于此句话的长度就进入循环
Stringword=dic.matchLong（sentence,i）;
//正向最大长度匹配
if（word!
=null）//已经匹配上
{
//下次匹配点在这个词之后
i+=word.length（）;
//如果这个词是词库中的那么就打印出来
System.out.print（word+"
"
）;
else//如果在我们所处理的范围内一直都没有找到匹配上的词，就按单字切分
word=sentence.substring（i,i+1）;
//打印一个字
++i;
//下次匹配点在这个字符之后
因为采用了Trie树结构查找单词，所以和用HashMap查找单词的方式比较起来，这种实现方法代码更简单，而且切分速度更快。
例如：
“有意见分歧”这句话，正向最大长度切分的结果是：
“有意/见/分歧”，逆向最大长度切分的结果是：
“有/意见/分歧”。
因为汉语的主干成分后置，所以逆向最大长度切分的精确度稍高。
另外一种最少切分的方法是使每一句中切出的词数最小。
1.1.3中文分词流程与结构
图4-4中文分词结构图
1.对输入字符串切分成句子：
对一段文本进行切分，首先是依次从这段文本里面切分出一个句子出来，然后再对这个句子进行切分；
2.原子切分：
对于一个句子的切分，首先是通过原子切分，将整个句子切分成一个个的原子单元（即不可再切分的形式，例如ATM这样的英文单词可以看成不可再切分的）；
3.生成全切分词图：
根据基本词库对句子进行全切分，并且生成一个邻接链表表示的词图；
4.计算最佳切分路径：
在这个词图的基础上，运用动态规划算法生成切分最佳路径；
5.未登录词识别：
进行中国人名、外国人名、地名、机构名等未登录名词的识别；
6.重新计算最佳切分路径；
7.词性标注：
可以采用HMM方法或最大熵方法等；
（作用？
）
8.根据规则调整切分结果：
根据每个分词的词形以及词性进行简单的规则处理，如：
日期分词的合并；
9.按需要的格式输出结果：
例如输出成搜索引擎需要的格式。
把待切分的字符串的每个位置看成是节点，词看成边，可以根据词典生成一个切分词图。
中文分词所有可能的切分。
“有意见分歧”这句话的切分词图如图4-4所示：
图4-5中文分词切分路径
在切分词图中：
“有意见分歧”.subString（0,1）是“有”；
“有意见分歧”.subString（0,2）是“有意”；
依次类推。
路径1：
0－1－3－5
路径2：
0－2－3－5
该走哪条路呢？
邻接表表示的切分词图由一个链表表示的数组组成。
1.1.4最大概率分词方法
从统计思想的角度来看，分词问题的输入是一个字串C=
，输出是一个词串S=
，其中m<
=n。
对于一个特定的C，会有多个S对应，统计分词的任务就是在这些W中找出概率最大的一个。
例如对于输入字符串C“有意见分歧”，有
和
两种切分可能：
:
有/意见/分歧/
有意/见/分歧/
计算概率P（
|C）和P（
|C），然后采用概率大的值对应的切分方案。
根据贝叶斯公式，有：
其中P（C）是固定值，从词串恢复到汉字串的概率只有唯一的一种方式，所以P（C|S）=1。
由此求解问题可以变换为：
在全切分所得的所有结果中，求得某个S，使得P（S）为最大。
那么，如何来表示P（S）呢？
为了容易实现，假设每个词之间的概率是上下文无关的，则：
其中，对于不同的S，m的值是不一样的，一般来说m越大，P（S）会越小。
也就是说，分出的词越多，概率越小。
这符合实际的观察，如最大长度匹配切分往往会使得m较小。
常用的词语概率表如表4-1所示。
表4-1词语概率表
P（
）=P（有）*P（意见）*P（分歧）
=1.8×
10-9
）=P（有意）*P（见）*P（分歧）
=1×
10-11
可得P（
）>
P（
如何尽快找到概率最大的词串（路径）？
（公式1）
首先介绍前驱词，假定对字串从左到右进行扫描，可以得到
等若干候选词，如果
的尾字跟
的首字邻接，就称
为
的前驱词。
比如上面例中，候选词“有”就是候选词“意见”的前驱词，“意见”和“见”都是“分歧”的前驱词。
字串最左边的词没有前驱词。
然后介绍最佳前驱词，如果某个候选词
有若干个前驱词
等等，其中累计概率最大的候选词称为
的最佳前驱词。
比如候选词“意见”只有一个前驱词“有”，因此，“有”同时也就是“意见”的最佳前驱词；
候选词“分歧”有两个前驱词“意见”和“见”，其中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最佳前驱词。
（注意累积的含义）
最大概率分词算法描述如下：
1.对一个待分词的字串S，按照从左到右的顺序取出全部候选词
；
2.到词典中查出每个候选词的概率值P（
），并记录每个候选词的全部前驱词；
3.按照公式1计算每个候选词的累计概率，同时比较得到每个候选词的最佳前驱词；
4.如果当前词
是字串S的尾词，且累计概率P'
（
）最大，则
就是S的终点词；
5.从S的终点词
开始，按照从右到左顺序，依次将每个词的最佳前驱词输出，即为S的分词结果。
算法运行示例如下：
（1）对“有意见分歧”，从左到右进行一遍扫描，得到全部候选词：
“有”，“有意”，“意见”，“见”，“分歧”；
（2）对每个候选词，记录下它的概率值，并将累计概率赋初值为0；
（3）顺次计算各个候选词的累计概率值，同时记录每个候选词的最佳前驱词：
P'
（有）=P（有），
（有意）=P（有意），
（意见）=P'
（有）×
P（意见），（“意见”的最佳前驱词为“有”）
（见）=P'
（有意）×
P（见），（“见”的最佳前驱词为“有意”）
（意见）P'
（见）
（4）“分歧”是尾词，“意见”是“分歧”的最佳前驱词，分词过程结束，输出结果：
有/意见/分歧/。
1.1.5N元分词方法
n-gram模型指在句子中在n个单词序列后出现的单词w的概率，也就是：
P（w|
二元模型（Bigram）考虑一个单词后出现另外一个单词的概率，是n-gram模型中的一种。
一般来说，“中国”之后出现“北京”的概率大于“中国”之后出现“北海”的概率，也就是：
P（北京|中国）>
P（北海|中国）
二元词表的格式是“左词@右词:
组合频率”，例如：
中国@北京:
100
中国@北海:
1
可以把二元词表看成是基本词表的常用搭配。
分词初始化时，先加载基本词表，然后加载二元词表。
对于拼音转换等歧义较多的情况下也可以采用三元模型（Trigram），例如：
P（海淀|中国,北京）>
P（海龙|中国,北京）
1.1.6新词发现
词典中没有的，但是结合紧密的字或词有可能组成一个新词。
比如：
“水立方”如果不在词典中，可能会切分成两个词“水”和“立方”。
如果在一篇文档中“水”和“立方”结合紧密，则有“水立方”可能是一个新词。
判断词的结合紧密程度的方法，信息熵：
如果ｘ和ｙ的出现相互独立,那么ｐ（ｘｙ）的值和ｐ（ｘ）ｐ（ｙ）的值相等,Ｉ（ｘ,ｙ）为0。
如果ｘ和ｙ密切相关,ｐ（ｘｙ）将比ｐ（ｘ）ｐ（ｙ）大很多,Ｉ（ｘ,ｙ）值也就远大于0。
如果ｘ和ｙ的几乎不会相邻出现,而它们各自出现的概率又比较大,那么Ｉ（ｘ,ｙ）将取负值。
设f（C）是词出现的次数，N是文档的总词数，则：
I（C1,C2）=
+
从二元连接串中计算二元连接串结合紧密程度的过程：
intindex=0;
fullResults=newBigramsCounts[table.size（）];
Bigramskey;
intfreq;
doublelogn=Math.log（（double）n）;
doubletemp;
doubleentropy;
intbigramCount;
for（Entry<
Bigrams,int[]>
e:
table.entrySet（））{
key=e.getKey（）;
if（key.one.equals（keyWord））
freq=（oneFreq.get（key.two））[0];
else
freq=（oneFreq.get（key.one））[0];
temp=keyCount*freq;
bigramCount=（e.getValue（））[0];
entropy=logn+Math.log（（double）bigramCount/temp）;
fullResults[index++]=
newBigramsCounts（
bigramCount,
entropy,
key.one,
key.two）;
新词语有些具有普遍意义的构词规则，例如“模仿秀”由“动词+名词”组成。
基于Web信息挖掘的方法：
网页锚点上的文字可能是新词，例如，“美甲”。
统计的方法和规则的方法结合对每个文档中重复子串组成的候选新词打分候选新词打分，超过阈值的候选新词选定为新词。
1.1.7未登录词识别
有个笑话：
有人问：
南京市长叫江大桥？
你怎么知道的？
因为看到一个标语——南京市长江大桥欢迎您。
未登录词在英文中叫做OutOfVocabulary（简称OOV）词。
常见的未登录词包括：
人名、地名、机构名。
对识别未登录词有用的信息：
●未登录词所在的上下文。
“**教授”，这里“教授”是人名的下文；
“邀请**”，这里“邀请”是人名的上文。
●未登录词本身的概率。
不
升级会员 