IKAnalyzer 分词如何消歧

     个人认为分词最根本的有三个步骤：字典加载，根据一定策略分词，消歧。稍微介绍过分词程序的基本词典数据结构，接着看看如何进行消歧。分词不用多说，比较简单。

     拿IKAnalyzer分词器为例，IKAnalyzer的切分方式是细粒度切分，当不需要智能处理时，其就把切出的所有词输出，但若启动了智能处理，那么接下来就是要进行消歧工作。

     细粒度切出的词比较杂，但是经过智能处理后，其看上去就像是采用MM算法或者RMM算法切分出。

     要想知道IKAnalyzer是如何进行消歧的，有必要先查清其实如何进行切分的，切分的词有何特点。下面这段代码是IKAnalyzer汉字切分的主要核心代码：

public void analyze(AnalyzeContext context) {
		if(CharacterUtil.CHAR_USELESS != context.getCurrentCharType()){
			
			//优先处理tmpHits中的hit
			if(!this.tmpHits.isEmpty()){
				//处理词段队列
				Hit[] tmpArray = this.tmpHits.toArray(new Hit[this.tmpHits.size()]);
				for(Hit hit : tmpArray){
					hit = Dictionary.matchWithHit(context.getSegmentBuff(), context.getCursor() , hit);
					if(hit.isMatch()){
						//输出当前的词
						Lexeme newLexeme = new Lexeme(context.getBufferOffset() , hit.getBegin() , context.getCursor() - hit.getBegin() + 1 , Lexeme.TYPE_CNWORD);
						context.addLexeme(newLexeme);
						
						if(!hit.isPrefix()){//不是词前缀，hit不需要继续匹配，移除
							this.tmpHits.remove(hit);
						}
						
					}else if(hit.isUnmatch()){
						//hit不是词，移除
						this.tmpHits.remove(hit);
					}					
				}
			}			
			
			//*********************************
			//再对当前指针位置的字符进行单字匹配
			Hit singleCharHit = Dictionary.matchInMainDict(context.getSegmentBuff(), context.getCursor(), 1);
			if(singleCharHit.isMatch()){//首字成词
				//输出当前的词
				Lexeme newLexeme = new Lexeme(context.getBufferOffset() , context.getCursor() , 1 , Lexeme.TYPE_CNWORD);
				context.addLexeme(newLexeme);

				//同时也是词前缀
				if(singleCharHit.isPrefix()){
					//前缀匹配则放入hit列表
					this.tmpHits.add(singleCharHit);
				}
			}else if(singleCharHit.isPrefix()){//首字为词前缀
				//前缀匹配则放入hit列表
				this.tmpHits.add(singleCharHit);
			}
			

		}else{
			//遇到CHAR_USELESS字符
			//清空队列
			this.tmpHits.clear();
		}
		
		//判断缓冲区是否已经读完
		if(context.isBufferConsumed()){
			//清空队列
			this.tmpHits.clear();
		}
		
		//判断是否锁定缓冲区
		if(this.tmpHits.size() == 0){
			context.unlockBuffer(SEGMENTER_NAME);
			
		}else{
			context.lockBuffer(SEGMENTER_NAME);
		}
	}

外层有一个游标在控制扫描的字符串位移：

do{
        			//遍历子分词器
        			for(ISegmenter segmenter : segmenters){
        				segmenter.analyze(context);
        			}
        			//字符缓冲区接近读完，需要读入新的字符
        			if(context.needRefillBuffer()){
        				break;
        			}
   				//向前移动指针
				}while(context.moveCursor());

这样的切分效果类似于paoding的切分效果，由于IKAnalyzer和paoding的字典数据结构不同，采用的字典匹配方式看上去不一样，但剖析原理，还是一个毪子中出来的，paoding是通过双层循环来尽可能的切出所有的词，而IKAnalyzer是采用

for(Hit hit : tmpArray){
					hit = Dictionary.matchWithHit(context.getSegmentBuff(), context.getCursor() , hit);
					if(hit.isMatch()){
						//输出当前的词
						Lexeme newLexeme = new Lexeme(context.getBufferOffset() , hit.getBegin() , context.getCursor() - hit.getBegin() + 1 , Lexeme.TYPE_CNWORD);
						context.addLexeme(newLexeme);
						
						if(!hit.isPrefix()){//不是词前缀，hit不需要继续匹配，移除
							this.tmpHits.remove(hit);
						}
						
					}else if(hit.isUnmatch()){
						//hit不是词，移除
						this.tmpHits.remove(hit);
					}					
				}

进行尽可能多的切词。这里不细说，读读两者的源码就会明白到底是怎么一回事。IKAnalyzer的词典的数据结构致使其采用这样复杂的方式切词。

    明白其切出的词是怎么样子后，下面进入主题，其实如何消歧的？
   
    在解说其如何消歧之前，得先说一个数据结构：TreeSet,因为IKAnalyzer正式借助这样的一个数据结构完成分词的消歧工作。
    TreeSet的javaDoc的解释如下
    A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.




     TreeSet是一个有序的集合序列，其必须实现

 Comparable

  接口，在IKAnalyzer的代码中，LexemePath类实现了Comparable接口，这个类恰好是分词消歧的核心，看看其实如何实现compareTO接口的：

public int compareTo(LexemePath o) {
		//比较有效文本长度
		if(this.payloadLength > o.payloadLength){
			return -1;
		}else if(this.payloadLength < o.payloadLength){
			return 1;
		}else{
			//比较词元个数，越少越好
			if(this.size() < o.size()){
				return -1;
			}else if (this.size() > o.size()){
				return 1;
			}else{
				//路径跨度越大越好
				if(this.getPathLength() >  o.getPathLength()){
					return -1;
				}else if(this.getPathLength() <  o.getPathLength()){
					return 1;
				}else {
					//根据统计学结论，逆向切分概率高于正向切分，因此位置越靠后的优先
					if(this.pathEnd > o.pathEnd){
						return -1;
					}else if(pathEnd < o.pathEnd){
						return 1;
					}else{
						//词长越平均越好
						if(this.getXWeight() > o.getXWeight()){
							return -1;
						}else if(this.getXWeight() < o.getXWeight()){
							return 1;
						}else {
							//词元位置权重比较
							if(this.getPWeight() > o.getPWeight()){
								return -1;
							}else if(this.getPWeight() < o.getPWeight()){
								return 1;
							}
							
						}
					}
				}
			}
		}
		return 0;
	}

这个就是IKAnalyzer分词消歧的核心，按照如下方式消歧：
     1）比较有效文本长度
     2）比较词元个数，越少越好
     3）路径跨度越大越好
     4）根据统计学结论，逆向切分概率高于正向切分，因此位置越靠后的优先
     5）词长越平均越好
     。。。
这些都是人为定的规则，按照统计方式进行消歧。

     看看外围的逻辑代码：

private LexemePath judge(QuickSortSet.Cell lexemeCell , int fullTextLength){
		//候选路径集合
		TreeSet<LexemePath> pathOptions = new TreeSet<LexemePath>();
		//候选结果路径
		LexemePath option = new LexemePath();
		
		//对crossPath进行一次遍历,同时返回本次遍历中有冲突的Lexeme栈
		Stack<QuickSortSet.Cell> lexemeStack = this.forwardPath(lexemeCell , option);
		
		//当前词元链并非最理想的，加入候选路径集合
		pathOptions.add(option.copy());
		
		//存在歧义词，处理
		QuickSortSet.Cell c = null;
		while(!lexemeStack.isEmpty()){
			c = lexemeStack.pop();
			//回滚词元链
			this.backPath(c.getLexeme() , option);
			//从歧义词位置开始，递归，生成可选方案
			this.forwardPath(c , option);
			pathOptions.add(option.copy());
		}
		
		//返回集合中的最优方案
		return pathOptions.first();
	}

这部分足以说明是采用TreeSet自动为其排好序列，把最优的结果放在最下面，返回最优的结果。

      IKAnalyzer是在细粒度切分后的结果中进行消歧，首先是扫描未经过歧义消除的词源，遇到有歧义的词就放到LexemePath数据结构中，当遇到没有歧义的词后就出来LexemePath这个数据结构，对其进行消歧，消歧后的LexemePath放到了 Map<Integer , LexemePath>数据结构中，最后对这个数据结构进行合并把结果放到LinkedList<Lexeme>数据结构中，至此完成分词工作。

代码如下：

void process(AnalyzeContext context , boolean useSmart){
		QuickSortSet orgLexemes = context.getOrgLexemes();
		Lexeme orgLexeme = orgLexemes.pollFirst();
		
		LexemePath crossPath = new LexemePath();
		while(orgLexeme != null){
			if(!crossPath.addCrossLexeme(orgLexeme)){
				//找到与crossPath不相交的下一个crossPath	
				if(crossPath.size() == 1 || !useSmart){
					//crossPath没有歧义 或者 不做歧义处理
					//直接输出当前crossPath
					context.addLexemePath(crossPath);
				}else{
					//对当前的crossPath进行歧义处理
					QuickSortSet.Cell headCell = crossPath.getHead();
					LexemePath judgeResult = this.judge(headCell, crossPath.getPathLength());
					//输出歧义处理结果judgeResult
					context.addLexemePath(judgeResult);
				}
				
				//把orgLexeme加入新的crossPath中
				crossPath = new LexemePath();
				crossPath.addCrossLexeme(orgLexeme);
			}
			orgLexeme = orgLexemes.pollFirst();
		}
		
		
		//处理最后的path
		if(crossPath.size() == 1 || !useSmart){
			//crossPath没有歧义 或者 不做歧义处理
			//直接输出当前crossPath
			context.addLexemePath(crossPath);
		}else{
			//对当前的crossPath进行歧义处理
			QuickSortSet.Cell headCell = crossPath.getHead();
			LexemePath judgeResult = this.judge(headCell, crossPath.getPathLength());
			//输出歧义处理结果judgeResult
			context.addLexemePath(judgeResult);
		}
	}

最后向IKAnalyzer的作者致敬，开源自己的源代码，给后者打开方便之门，给新手提供这么好的学习材料。