IK分词源码分析连载(三)--歧义处理

转载请注明出处：

http://blog.chinaunix.net/uid-20761674-id-3424553.html

前一篇介绍了IK分词源码分析连载(二)--子分词器

开始进入IK分词的另一个核心模块，分词歧义处理，这里使用了组合遍历的一些代码，代码有点绕

总体思路是这样：

• 从三个子分词器(见前一篇文章)得到的分词结果中取出不相交的分词块，假如分词结果为abcd(abcd代表词)，abcd是按其在文本中出现的位置排序的，从前到后。假如a与b相交，b与c相交，c与d不相交，则将分词结果切成abc和d两个块分别处理
• 如果选择了useSmart(智能分词)，则从相交的块中选举一个相对最优的分词结果输出，这是由judge()完成的
• 如果没有选择useSmart，则输出所有分词结果，包括相交的结果

void process(AnalyzeContext context , boolean useSmart){
        QuickSortSet orgLexemes = context.getOrgLexemes();
        Lexeme orgLexeme = orgLexemes.pollFirst();

        LexemePath crossPath = new LexemePath();
        while(orgLexeme != null){
            //jw出现不相交的分词，把之前的所有词进行歧义处理
            if(!crossPath.addCrossLexeme(orgLexeme)){
                //找到与crossPath不相交的下一个crossPath
                //jw非智能歧义处理，即使相交，也直接输出分词结果
                if(crossPath.size() == 1 || !useSmart){
                    //crossPath没有歧义 或者 不做歧义处理
                    //直接输出当前crossPath
                    context.addLexemePath(crossPath);
                }else{
                    //jw出现一个不相交的分词，将之前相交的词开始歧义处理
                    //对当前的crossPath进行歧义处理
                    QuickSortSet.Cell headCell = crossPath.getHead();
                    LexemePath judgeResult = this.judge(headCell, crossPath.getPathLength());
                    //输出歧义处理结果judgeResult
                    context.addLexemePath(judgeResult);
                }
                //jw只要出现不相交的词，即进行歧义处理，选出当前最优结果，然后继续处理后面的词
                //把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);
        }

下面来看最重要的judge()方法

/**
     * 歧义识别
     * @param lexemeCell 歧义路径链表头
     * @param fullTextLength 歧义路径文本长度
     * @param option 候选结果路径
     * @return
     */
    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());
        //jw这种处理方式应该不是最优的，只是采用贪心的方法获取近似最优方案，并没有遍历所有的可能集合
        //jw每次从一个歧义位置开始，贪心的获取一种分词方案
        //存在歧义词，处理
        QuickSortSet.Cell c = null;
        while(!lexemeStack.isEmpty()){
            System.out.println("jwdebug one option begin");
            c = lexemeStack.pop();
            //回滚词元链
            this.backPath(c.getLexeme() , option);
            //从歧义词位置开始，递归，生成可选方案
            this.forwardPath(c , option);
            pathOptions.add(option.copy());
        }

        //jw跳转到LexemePath.java中的compareTo()接口查看最优方案选择策略
        //返回集合中的最优方案
        return pathOptions.first();

    }

这个TreeSet用来保存候选分词结果集，并按照排序策略对分词结果集进行排序，排序策略后面说

TreeSet<LexemePath> pathOptions = new TreeSet<LexemePath>();

接下来是forwardPath

• 将相交的分词块传入，进行歧义处理
• 贪心选择其中不相交的分词结果，存放到分词候选结果集option中
• 把存在歧义的词，也就是和option中的词相交的词放入conflickStack中

/**
     * 向前遍历，添加词元，构造一个无歧义词元组合
     * @param LexemePath path
     * @return
     */
    private Stack<QuickSortSet.Cell> forwardPath(QuickSortSet.Cell lexemeCell , LexemePath option){
        //发生冲突的Lexeme栈
        Stack<QuickSortSet.Cell> conflictStack = new Stack<QuickSortSet.Cell>();
        QuickSortSet.Cell c = lexemeCell;
        //迭代遍历Lexeme链表
        while(c != null && c.getLexeme() != null){
            if(!option.addNotCrossLexeme(c.getLexeme())){
                //词元交叉，添加失败则加入lexemeStack栈
                conflictStack.push(c);
            }
            c = c.getNext();
        }
        return conflictStack;
    }

然后就是分词结果组合遍历方法：

• 从conflictStack中选出一个歧义词c，从option结尾回滚option词元链，直到能放下词c
• 从词c的位置执行forwardPath，生成一个可选分词结果集
• 直到conflictStack中的所有歧义词处理完毕
• 可以看出，该方法没有遍历所有可能的集合，只是从当前替换歧义词的位置贪心的生成其中一种可选方案，只是一种近似最优的选取结果。个人估计，分词的冲突不会太复杂，这样的选取结果可以接受

最后来看分词结果集的排序方案，不复杂，简单做下说明：

• 比较有效文本长度，有效文本长度是指所有分词结果最靠后的一个词距离最靠前的一个词的长度(这里的靠前和靠后是指词在待匹配文本中的位置)
• 词元个数，即分出来的词的个数
• 路径跨度，指所有词的长度的加和
• 逆向切分、词元长度、位置权重就不解释鸟

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;
    }

到此，IK分词中两个最核心的模块：3个子分词器+歧义处理已经介绍完了。到这里，对IK分词的思路应该了解大部分了。

还有几个部分需要考虑：

1.非词典中的词语切不出来，怎么处理的？

2.停用词处理在哪里？

后续会继续介绍