1、第四章 分词补充 分词有人把文本解析比喻成人体的消化过程，输入食物，分解出有用的氨基酸和葡萄糖等。这部分处理从整段的文本中解析出有意义的词语。1.1 中文分词因为中文文本中词和词之间不像英文一样存在边界，所以中文分词是一个专业处理中文信息的搜索引擎首先面对的问题。英语、法语和德语等西方语言通常采用空格或标点符号将词隔开，具有天然的分隔符，所以词的获取简单。但是中文、日文和韩文等东方语言，虽然句子之间有分隔符，但词与词之间没有分隔符，所以需要靠程序切分出词。另外，除了可以用于全文查找，中文分词的方法也被应用到英语手写体识别中。因为在识别手写体时，单词之间的空格就不很清楚了。1.1.1 查找词典算
2、法 (机械分词法)在讨论查找词典方法之前，首先看看文本方式的词典格式：滤波器 n 0堵击 v 0稿费 n 7神机妙算 i 0开设 vn 0 v 32 每行一个词，然后是这个词可能的词性和语料库中按这个词性出现的次数。存储基本词性相关信息的类如下：public class POSInf public short pos=0; /词性 public int freq=0; /词频 public String seCode = null; /词的语义编码在基于词典的中文分词方法中，词典匹配算法是基础。使用的词典规模往往在几十万词义上。为了保证切分速度，需要选择一个好的查找词典算法。本节介绍词典的Ti
3、re树组织结构及词典的最大长度查找方法等。（早期的结构是倒排索引）在一个三叉搜索树(TernarySearchTrie)中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针，一个指向左边的树，一个指向右边的树，还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不是太重要。通过选择一个排序后的数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。我们再次以有序的数据单元 (as at be
4、by he in is it of on or to) 为例。 首先我们把关键字“is”作为中间值并且构建一个包含字母“i”的根节点。它的直接后继结点包含字母“s”并且可以存储任何与“is”有关联的数据。对于“i”的左树，我们选择“be”作为中间值并且创建一个包含字母“b”的结点，字母“b”的直接后继结点包含“e”。该数据存储在“e”结点。对于“i”的右树，按照逻辑，选择“on”作为中间值，并且创建“o”结点以及它的直接后继结点“n”。最终的三叉树如图4-3所示：图4-3 三叉树垂直的虚线代表一个父节点的下面的直接的后继结点。只有父节点和它的直接后继节点才能形成一个数据单元的关键字；“i”和“
5、s”形成关键字“is”，但是“i”和“b”不能形成关键字，因为它们之间仅用一条斜线相连，不具有直接后继关系。图4-3中带圈的节点为终止节点，如果查找一个词以终止节点结束，则说明三叉树包含这个词。 TernarySearchTrie本身存储关键字到值的对应关系，可以当作HashMap对象来使用。关键字按照字符拆分成了Node，以TSTNode的实例存在。值存储在TSTNode的data属性中。TSTNode的实现如下： public final class TSTNode /* 节点的值 */ public Data data=null;/ data属性可以存储词原文和词性、词频等相关的信息 p
6、rotected TSTNode loNode; /左边节点 protected TSTNode eqNode; /中间节点 protected TSTNode hiNode; /右边节点 protected char splitchar; / 本节点表示的字符 /* * 构造方法 * *param splitchar 该节点表示的字符 */ protected TSTNode(char splitchar) this.splitchar = splitchar; public String toString() return splitchar:+ splitchar; 基本的查找词典过程是
7、：输入一个词，返回这个词对应的TSTNode，如果该词不在词典中则返回空。查找词典的过程中，从树的根节点匹配Key。Key 按Char从前往后匹配。charIndex表示Key的当前要比较的Char的位置。匹配过程如下： protected TSTNode getNode(String key, TSTNode startNode) if (key = null ) return null; int len = key.length(); if (len =0) return null; TSTNode currentNode = startNode; /匹配过程中的当前节点的位置 int c
8、harIndex = 0; char cmpChar = key.charAt(charIndex); int charComp; while (true) if (currentNode = null) return null; charComp = cmpChar - currentNode.splitchar; if (charComp = 0) charIndex+; if (charIndex = len) return currentNode; else cmpChar = key.charAt(charIndex); currentNode = currentNode.eqNod
9、e; else if (charComp 0) currentNode = currentNode.loNode; else currentNode = currentNode.hiNode; 三叉树的创建过程如下： TSTNode currentNode = root; /从树的根节点开始查找 int charIndex = 0; /从词的开头匹配 while (true) int charComp =key.charAt(charIndex) - currentNode.splitchar;/比较词的当前字符与节点的当前字符 if (charComp = 0) /相等 charIndex+
10、; if (charIndex = key.length() return currentNode; if (currentNode.eqNode = null) currentNode.eqNode = new TSTNode(key.charAt(charIndex); currentNode = currentNode.eqNode; else if (charComp 0) /小于 if (currentNode.loNode = null) currentNode.loNode = new TSTNode(key.charAt(charIndex); currentNode = cu
11、rrentNode.loNode; else /大于 if (currentNode.hiNode = null) currentNode.hiNode = new TSTNode(key.charAt(charIndex); currentNode = currentNode.hiNode; 相对于查找过程，创建过程在搜索的过程中判断链接的空值，而不是一开始就判断。1.1.2 中文分词的原理分词的两类方法： 机械匹配的方法：例如正向最大长度匹配(Forward Maximum Match)的方法和逆向最大长度匹配(Reverse Maximum Matching)的方法。 统计的方法：例如最
12、大概率分词方法和最大熵的分词方法等。正向最大长度匹配的分词方法实现起来很简单。每次从词典找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词，如果词典中没有词匹配上，则按单字切分。下面给出正向对大匹配（Maximum Matching Method,MM）算法基本思想：设自动分词词典中最长词条所含汉字个数为I；取被处理材料当前字符串序数中的I个字作为匹配字段，查找分词词典。若词典中有这样的一个I字词，则匹配成功，匹配字段作为一个词被切分出来，转；如果词典中找不到这样的一个I字词，则匹配失败；匹配字段去掉最后一个汉字，I-；重复-，直至切分成功为止；I重新赋初值，
13、转，直到切分出所有词为止。例如，Trie树结构的词典中包括如下的8个词语：大 大学 大学生 活动 生活 中 中心 心 为了形成平衡的Trie树，把词先排序，排序后为：中 中心 大 大学 大学生 心 活动 生活 按平衡方式生成的词典Trie树如下图，其中粗黑显示的节点可以做为匹配终止节点：输入：“大学生活动中心”，首先匹配出“大学生”，然后匹配出“活动”，最后匹配出“中心”。切分过程如下：已匹配上的结果待匹配串NULL大学生活动中心大学生活动中心大学生/活动中心大学生/活动/中心NULL最后分词结果为：“大学生/活动/中心”。在最大长度匹配的分词方法中，需要用到从指定字符串返回指定位置的最长匹配
14、词的方法。例如，当输入串是“大学生活动中心”，则返回“大学生”这个词，而不是返回“大”或者“大学”。从Trie树搜索最长匹配单词的方法如下： public String matchLong(String key,int offset) String ret = null; if (key = null | rootNode = null | .equals(key) return ret; TSTNode currentNode = rootNode; int charIndex = offset; while (true) if (currentNode = null) return ret
15、; int charComp = key.charAt(charIndex) - currentNode.spliter; if (charComp = 0) charIndex+; if(currentNode.data != null) ret = currentNode.data; /候选最长匹配词 if (charIndex = key.length() return ret; /已经匹配完 currentNode = currentNode.eqNode; else if (charComp 0) currentNode = currentNode.loNode; else curr
16、entNode = currentNode.hiNode; 测试方法：String sentence = 大学生活动中心;int offset = 0;String ret = dic.matchLong(sentence,offset);System.out.println(sentence+ match:+ret);返回结果：大学生活动中心 match:大学生 正向最大长度分词的实现代码如下： public void wordSegment(String sentence)/传入一个字符串作为要处理的对象 int senLen = sentence.length();/首先计算出传入的这句
17、话的字符长度 int i=0;/控制匹配的起始位置 while(i senLen)/如果i小于此句话的长度就进入循环 String word = dic.matchLong(sentence, i);/正向最大长度匹配 if(word!=null)/已经匹配上 /下次匹配点在这个词之后 i += word.length(); /如果这个词是词库中的那么就打印出来 System.out.print(word + ); else/如果在我们所处理的范围内一直都没有找到匹配上的词，就按单字切分 word = sentence.substring(i, i+1); /打印一个字 System.out.
18、print(word + ); +i;/下次匹配点在这个字符之后 因为采用了Trie树结构查找单词，所以和用HashMap查找单词的方式比较起来，这种实现方法代码更简单，而且切分速度更快。例如：“有意见分歧”这句话，正向最大长度切分的结果是：“有意/见/分歧”，逆向最大长度切分的结果是：“有/意见/分歧”。因为汉语的主干成分后置，所以逆向最大长度切分的精确度稍高。另外一种最少切分的方法是使每一句中切出的词数最小。1.1.3 中文分词流程与结构图4-4中文分词结构图1. 对输入字符串切分成句子：对一段文本进行切分，首先是依次从这段文本里面切分出一个句子出来，然后再对这个句子进行切分；2. 原子切
19、分：对于一个句子的切分，首先是通过原子切分，将整个句子切分成一个个的原子单元(即不可再切分的形式，例如ATM这样的英文单词可以看成不可再切分的)；3. 生成全切分词图：根据基本词库对句子进行全切分，并且生成一个邻接链表表示的词图；4. 计算最佳切分路径：在这个词图的基础上，运用动态规划算法生成切分最佳路径；5. 未登录词识别：进行中国人名、外国人名、地名、机构名等未登录名词的识别；6. 重新计算最佳切分路径；7. 词性标注：可以采用HMM方法或最大熵方法等；（作用？）8. 根据规则调整切分结果：根据每个分词的词形以及词性进行简单的规则处理，如：日期分词的合并；9. 按需要的格式输出结果：例如输
20、出成搜索引擎需要的格式。把待切分的字符串的每个位置看成是节点，词看成边，可以根据词典生成一个切分词图。中文分词所有可能的切分。“有意见分歧”这句话的切分词图如图4-4所示：图4-5 中文分词切分路径在切分词图中：“有意见分歧”.subString(0,1) 是“有”；“有意见分歧”.subString(0,2) 是“有意”；依次类推。路径1： 0135路径2： 0235该走哪条路呢？邻接表表示的切分词图由一个链表表示的数组组成。1.1.4 最大概率分词方法从统计思想的角度来看，分词问题的输入是一个字串C=，输出是一个词串S=，其中m P()如何尽快找到概率最大的词串（路径）？ (公式1)首先介
21、绍前驱词，假定对字串从左到右进行扫描，可以得到等若干候选词，如果的尾字跟的首字邻接，就称为的前驱词。比如上面例中，候选词“有”就是候选词“意见”的前驱词，“意见”和“见”都是“分歧”的前驱词。字串最左边的词没有前驱词。然后介绍最佳前驱词，如果某个候选词有若干个前驱词等等，其中累计概率最大的候选词称为的最佳前驱词。比如候选词“意见”只有一个前驱词“有”，因此，“有”同时也就是“意见”的最佳前驱词；候选词“分歧”有两个前驱词“意见”和“见”，其中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最佳前驱词。（注意累积的含义）最大概率分词算法描述如下：1. 对一个待分词的字串 S，按照从
22、左到右的顺序取出全部候选词；2. 到词典中查出每个候选词的概率值P()，并记录每个候选词的全部前驱词；3. 按照公式1计算每个候选词的累计概率，同时比较得到每个候选词的最佳前驱词；4. 如果当前词是字串S的尾词，且累计概率P ()最大，则就是S的终点词；5. 从S的终点词开始，按照从右到左顺序，依次将每个词的最佳前驱词输出，即为S的分词结果。 算法运行示例如下：（1）对“有意见分歧”，从左到右进行一遍扫描，得到全部候选词：“有”，“有意”，“意见”，“见”，“分歧”；（2）对每个候选词，记录下它的概率值，并将累计概率赋初值为0；（3）顺次计算各个候选词的累计概率值，同时记录每个候选词的最佳前驱
23、词：P(有)=P(有)，P(有意) = P(有意)，P (意见)= P (有) P(意见)， ( “意见”的最佳前驱词为“有”)P (见)= P (有意) P(见)， ( “见”的最佳前驱词为“有意”)P（意见） P（见）（4）“分歧”是尾词，“意见”是“分歧”的最佳前驱词，分词过程结束，输出结果：有/ 意见/ 分歧/。1.1.5 N元分词方法n-gram模型指在句子中在n个单词序列后出现的单词 w的概率，也就是：P(w|)二元模型(Bigram)考虑一个单词后出现另外一个单词的概率，是n-gram模型中的一种。例如：一般来说，“中国”之后出现“北京”的概率大于“中国”之后出现“北海”的概率，
24、也就是：P(北京|中国) P(北海|中国)二元词表的格式是“左词右词:组合频率”，例如：中国北京:100中国北海:1可以把二元词表看成是基本词表的常用搭配。分词初始化时，先加载基本词表，然后加载二元词表。对于拼音转换等歧义较多的情况下也可以采用三元模型(Trigram)，例如：P (海淀|中国,北京) P (海龙|中国,北京)1.1.6 新词发现词典中没有的，但是结合紧密的字或词有可能组成一个新词。比如：“水立方”如果不在词典中，可能会切分成两个词“水”和“立方”。如果在一篇文档中“水”和“立方”结合紧密，则有“水立方”可能是一个新词。判断词的结合紧密程度的方法，信息熵：如果和的出现相互独立,
25、那么()的值和()()的值相等,(,)为0。如果和密切相关,()将比()()大很多,(,)值也就远大于0。如果和的几乎不会相邻出现,而它们各自出现的概率又比较大,那么(,)将取负值。设f(C)是词出现的次数，N是文档的总词数，则：I(C1,C2) = + 从二元连接串中计算二元连接串结合紧密程度的过程： int index = 0; fullResults = new BigramsCountstable.size(); Bigrams key; int freq; double logn = Math.log(double)n); double temp; double entropy; i
26、nt bigramCount; for( Entry 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); fullResultsindex+ = new BigramsCounts
27、( bigramCount, entropy, key.one, key.two); 新词语有些具有普遍意义的构词规则，例如“模仿秀”由“动词+名词”组成。基于Web信息挖掘的方法：网页锚点上的文字可能是新词，例如，“美甲”。统计的方法和规则的方法结合对每个文档中重复子串组成的候选新词打分候选新词打分，超过阈值的候选新词选定为新词。1.1.7 未登录词识别有个笑话：有人问：南京市长叫江大桥？你怎么知道的？因为看到一个标语南京市长江大桥欢迎您。未登录词在英文中叫做Out Of Vocabulary (简称OOV)词。常见的未登录词包括：人名、地名、机构名。对识别未登录词有用的信息： 未登录词所在的上下文。例如：“*教授”，这里“教授”是人名的下文；“邀请*”，这里“邀请”是人名的上文。 未登录词本身的概率。例如：不依赖
