第四章--分词(补充)

分词有人把文本解析比喻成人体的消化过程，输入食物，分解出有用的氨基酸和葡萄糖等。这部分处理从整段的文本中解析出有意义的词语。1.1中文分词因为中文文本中词和词之间不像英文一样存在边界，所以中文分词是一个专业处理中文信息的搜索引擎首先面对的问题。英语、法语和德语等西方语言通常采用空格或标点符号将词隔开，具有天然的分隔符，所以词的获取简单。但是中文、日文和韩文等东方语言，虽然句子之间有分隔符，但词与词之间没有分隔符，所以需要靠程序切分出词。另外，除了可以用于全文查找，中文分词的方法也被应用到英语手写体识别中。因为在识别手写体时，单词之间的空格就不很清楚了。1.1.1查找词典算法(机械分词法)在讨论查找词典方法之前，首先看看文本方式的词典格式：滤波器n0堵击v0稿费n7神机妙算i0开设vn0v32每行一个词，然后是这个词可能的词性和语料库中按这个词性出现的次数。存储基本词性相关信息的类如下：publicclassPOSInf{publicshortpos=0;//词性publicintfreq=0;//词频publicStringseCode=null;//词的语义编码}在基于词典的中文分词方法中，词典匹配算法是基础。使用的词典规模往往在几十万词义上。为了保证切分速度，需要选择一个好的查找词典算法。本节介绍词典的Tire树组织结构及词典的最大长度查找方法等。（早期的结构是倒排索引）在一个三叉搜索树(TernarySearchTrie)中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针，一个指向左边的树，一个指向右边的树，还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不是太重要。通过选择一个排序后的数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。我们再次以有序的数据单元(asatbebyheinisitofonorto)为例。首先我们把关键字“is”作为中间值并且构建一个包含字母“i”的根节点。它的直接后继结点包含字母“s”并且可以存储任何与“is”有关联的数据。对于“i”的左树，我们选择“be”作为中间值并且创建一个包含字母“b”的结点，字母“b”的直接后继结点包含“e”。该数据存储在“e”结点。对于“i”的右树，按照逻辑，选择“on”作为中间值，并且创建“o”结点以及它的直接后继结点“n”。最终的三叉树如图4-3所示：bnsnoehtotyefrtiasasatbebyheinisitofonorto图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(){returnsplitchar:+splitchar;}}基本的查找词典过程是：输入一个词，返回这个词对应的TSTNode，如果该词不在词典中则返回空。查找词典的过程中，从树的根节点匹配Key。Key按Char从前往后匹配。charIndex表示Key的当前要比较的Char的位置。匹配过程如下：protectedTSTNodegetNode(Stringkey,TSTNodestartNode){if(key==null){returnnull;}intlen=key.length();if(len==0)returnnull;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(charComp0){currentNode=currentNode.loNode;}else{currentNode=currentNode.hiNode;}}}三叉树的创建过程如下：TSTNodecurrentNode=root;//从树的根节点开始查找intcharIndex=0;//从词的开头匹配while(true){intcharComp=key.charAt(charIndex)-currentNode.splitchar;//比较词的当前字符与节点的当前字符if(charComp==0){//相等charIndex++;if(charIndex==key.length()){returncurrentNode;}if(currentNode.eqNode==null){currentNode.eqNode=newTSTNode(key.charAt(charIndex));}currentNode=currentNode.eqNode;}elseif(charComp0){//小于if(currentNode.loNode==null){currentNode.loNode=newTSTNode(key.charAt(charIndex));}currentNode=currentNode.loNode;}else{//大于if(currentNode.hiNode==null){currentNode.hiNode=newTSTNode(key.charAt(charIndex));}currentNode=currentNode.hiNode;}}相对于查找过程，创建过程在搜索的过程中判断链接的空值，而不是一开始就判断。1.1.2中文分词的原理分词的两类方法：机械匹配的方法：例如正向最大长度匹配(ForwardMaximumMatch)的方法和逆向最大长度匹配(ReverseMaximumMatching)的方法。统计的方法：例如最大概率分词方法和最大熵的分词方法等。正向最大长度匹配的分词方法实现起来很简单。每次从词典找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词，如果词典中没有词匹配上，则按单字切分。下面给出正向对大匹配（MaximumMatchingMethod,MM）算法基本思想：①设自动分词词典中最长词条所含汉字个数为I；②取被处理材料当前字符串序数中的I个字作为匹配字段，查找分词词典。若词典中有这样的一个I字词，则匹配成功，匹配字段作为一个词被切分出来，转⑥；③如果词典中找不到这样的一个I字词，则匹配失败；④匹配字段去掉最后一个汉字，I--；⑤重复②-④，直至切分成功为止；⑥I重新赋初值，转②，直到切分出所有词为止。例如，Trie树结构的词典中包括如下的8个词语：大大学大学生活动生活中中心心为了形成平衡的Trie树，把词先排序，排序后为：中中心大大学大学生心活动生活按平衡方式生成的词典Trie树如下图，其中粗黑显示的节点可以做为匹配终止节点：输入：“大学生活动中心”，首先匹配出“大学生”，然后匹配出“活动”，最后匹配出“中心”。切分过程如下：已匹配上的结果待匹配串NULL大学生活动中心大学生活动中心大学生/活动中心大学生/活动/中心NULL最后分词结果为：“大学生/活动/中心”。在最大长度匹配的分词方法中，需要用到从指定字符串返回指定位置的最长匹配词的方法。例如，当输入串是“大学生活动中心”，则返回“大学大中学活心生心动生活生”这个词，而不是返回“大”或者“大学”。从Trie树搜索最长匹配单词的方法如下：publicStringmatchLong(Stringkey,intoffset){Stringret=null;if(key==null||rootNode==null||.equals(key)){returnret;}TSTNodecurrentNode=rootNode;intcharIndex=offset;while(true){if(currentNode==null){returnret;}intcharComp=key.charAt(charIndex)-currentNode.spliter;if(charComp==0){charIndex++;if(currentNode.data!=null){ret=currentNode.data;//候选最长匹配词}if(charIndex==key.length()){returnret;//已经匹配完}currentNode=currentNode.eqNode;}elseif(charComp0){currentNode=currentNode.loNode;}else{currentNode=currentNode.hiNode;}}}测试方法：Stringsentence=大学生活动中心;intoffset=0;Stringret=dic.matchLong(sentence,offset);System.out.println(sentence+match:+ret);返回结果：大学生活动中心match:大学生正向最大长度分词的实现代码如下：publicvoidwordSegment(Stringsentence)//传入一个字符串作为要处理的对象{intsenLen=sentence.length();//首先计算出传入的这句话的字符长度inti=0;//控制匹配的起始位置while(isenLen)//如果i小于此句话的长度就进入循环{Stringword=dic.matchLong(sentence,i);//正向最大长度匹配if(word!=null)//已经匹配上{//下次匹配点在这个词之后i+=word.length();//如果这个词是词库中的那么就打印出来System.out.print(word+);}else//如果在我们所处理的范围内一直都没有找到匹配上的词，就按单字切分{word=sentence.substring(i,i+1);//打印一个字System.out.print(word+);++i;//下次匹配点在这个字符之后}}}因为采用了Trie树结构查找单词，所以和用HashMap查找单词的方式比较起来，这种实现方法代码更简单，而且切分速度更快。例如：“有意见分歧”这句话，正向最大长