1.前言

在使用ES进行中文搜索时，分词的效果直接影响搜索的结果。对于没有能力自研分词，或者一般的使用场景，都会使用ik分词器作为分词插件。ik分词器的基本使用可以参考: Elasticsearch中ik分词器的使用。ik分词器的主要逻辑包括三部分：
1）词典：词典的好坏直接影响分词结果的好坏，本文将介绍词典的构建和存储结构
2）词的匹配：有了词典之后，就可以对输入的字符串逐字句和词典进行匹配
3）消除歧义：通过词典匹配出来的切分方式会有多种，消除歧义就是从中寻找最合理的一种方式

2前期准备

在研究ik的原理之前，需要把ik的源码clone到本地，https://github.com/medcl/elasticsearch-analysis-ik。
clone到本地之后checkout 6.8.1版本，然后写一个方法调用ik分词器，这样就可以进行debug了。

public class TestIK {

    public static void main(String[] args) throws IOException {
        testIkSegment();
    }

    public static void testIkSegment() throws IOException {
        String t = "得饶人处且饶人";
        Settings settings =  Settings.builder()
                .put("use_smart", false)
                .put("enable_lowercase", false)
                .put("enable_remote_dict", false)
                .build();
        Configuration configuration=new Configuration(null,settings).setUseSmart(false);
        IKSegmenter segmenter = new IKSegmenter(new StringReader(t), configuration);
        Lexeme next;
        while ((next = segmenter.next())!=null){
            System.out.println(next.getLexemeText());
        }
    }
}

启动的时候会出现如下错误：

启动错误

出现错误的原因就是没有指定词典的路径，因为构造Environment对象相对比较复杂，因此直接采用文件路径的方法代替，修改org.wltea.analyzer.dic.Dictionary构造器中代码，让代码能快速运行

//     this.conf_dir = cfg.getEnvironment().configFile().resolve(AnalysisIkPlugin.PLUGIN_NAME);
      this.conf_dir = Paths.get("/Users/zjb/code/mine/commit/ik/elasticsearch-analysis-ik/config");

3.词典

从上面的准备工作能看出来，词典的配置其实是非常重要的，ik为我们提供了三种常见的词典分别是：
1）main.dic：主词典，一些常用词
2）quantifier.dic：常用的量词
3）stopword.dic：停用词
这些词典用户都可以自行扩展，只需要配置IKAnalyzer.cfg.xml文件即可
词典是怎么加载的呢，常用的字典树 tire tree 是一种结构简单的树，也叫做前缀树，结构如下图所示

前缀树

从根节点触发，把一个词挂在这颗树上。其中词的开头，都是根节点的孩子节点，每个字都是前一个字的孩子节点，红色的节点表示词的结尾。上图中间表示，前门是一个词，门是结尾；前门巨虎也是一个词，虎结尾。
由于main.dic的词非常多，而且用户又可以自定义扩展，这样会导致这个树会非常庞大，如果存粹用map存储，会比较浪费空间，因此ik采用了一种折中的方式。结构参考DictSegment.java代码：

class DictSegment implements Comparable<DictSegment>{
   
   //公用字典表，存储汉字
   private static final Map<Character , Character> charMap = new ConcurrentHashMap<Character , Character>(16 , 0.95f);
   //数组大小上限
   private static final int ARRAY_LENGTH_LIMIT = 3;

   
   //Map存储结构
   private Map<Character , DictSegment> childrenMap;
   //数组方式存储结构
   private DictSegment[] childrenArray;
   
   
   //当前节点上存储的字符
   private Character nodeChar;
   //当前节点存储的Segment数目
   //storeSize <=ARRAY_LENGTH_LIMIT ，使用数组存储， storeSize >ARRAY_LENGTH_LIMIT ,则使用Map存储
   private int storeSize = 0;
   //当前DictSegment状态 ,默认 0 , 1表示从根节点到当前节点的路径表示一个词
   private int nodeState = 0; 
}

ik的代码注释还算比较全，而且都是中文的，也比较好理解。主要的思想，就是根据子节点的数量对存储结构进行调整，如果子节点的数量小于等于3，则采用数组存储，如果子节点的数量大于3，采用map存储。其中的nodeState就是用来标记当前节点（即当前的字符是否是词的结尾）。

有了这个结构之后，我们看一下词是怎么从文件加载到内存的，词典的加载是在Configuration构造器内进行的，最终会调用DictSegment#fillSegment方法:

private synchronized void fillSegment(char[] charArray , int begin , int length , int enabled){
   //获取字典表中的汉字对象
   Character beginChar = Character.valueOf(charArray[begin]);
   Character keyChar = charMap.get(beginChar);
   //字典中没有该字，则将其添加入字典
   if(keyChar == null){
      charMap.put(beginChar, beginChar);
      keyChar = beginChar;
   }
   
   //搜索当前节点的存储，查询对应keyChar的keyChar，如果没有则创建
   DictSegment ds = lookforSegment(keyChar , enabled);
   if(ds != null){
      //处理keyChar对应的segment
      if(length > 1){
         //词元还没有完全加入词典树
         ds.fillSegment(charArray, begin + 1, length - 1 , enabled);
      }else if (length == 1){
         //已经是词元的最后一个char,设置当前节点状态为enabled，
         //enabled=1表明一个完整的词，enabled=0表示从词典中屏蔽当前词
         ds.nodeState = enabled;
      }
   }

}

这就是个递归把词塞入词典的过程，通过lookforSegment方法查找当前map是存在字，如果没有的话，就创建一个DictSegment。然后判断当前处理的这个词是否处理完了，没处理完就递归处理，处理完了就标记这个字是词的结尾。

4.切词

有了词典和输入语句之后，就可以进行切词了。ik的切词方式主要有两种，一种为smart模式，一种为ik_max_word即非smart模式。以宝剑锋从磨砺出为例：

非smart模式分词结果：宝剑锋从磨砺出、宝剑锋、宝剑、从、锋、从、磨砺、出
smart模式下的分词结果：宝剑锋从磨砺出

从非smart的分词结果中可以看出，对于一个语句可以有很多种切分方式，非smart就是把没种可能的分词结果都给出来了。而smart模式，就是需要在这几种分词模式中，寻找一种认为最合理的分词方式。

从处理角度说，设置了smart模式，就是在进行词切分后，在进行一次分词的选择，即通常说的消除歧义。

ik默认实现了三种分词器，分别为CJKSegmenter（中文-日韩文子分词器）、CN_QuantifierSegmenter（中文数量词分词器）、LetterSegmenter（英文字符及阿拉伯数字子分词器）。

分词的主要逻辑如下所示，采用类似懒加载的形式，第一次调用 segmenter.next()拿分词结果的时候，才进行分词。

while((l = context.getNextLexeme()) == null ){
   /*
    * 从reader中读取数据，填充buffer
    * 如果reader是分次读入buffer的，那么buffer要  进行移位处理
    * 移位处理上次读入的但未处理的数据
    */
   int available = context.fillBuffer(this.input);
   if(available <= 0){
      //reader已经读完
      context.reset();
      return null;
      
   }else{
      //初始化指针
      context.initCursor();
      do{
             //遍历子分词器
             for(ISegmenter segmenter : segmenters){
                segmenter.analyze(context);
             }
             //字符缓冲区接近读完，需要读入新的字符
             if(context.needRefillBuffer()){
                break;
             }
            //向前移动指针
      }while(context.moveCursor());
      //重置子分词器，为下轮循环进行初始化
      for(ISegmenter segmenter : segmenters){
         segmenter.reset();
      }
   }
   //对分词进行歧义处理
   this.arbitrator.process(context, configuration.isUseSmart());
   //将分词结果输出到结果集，并处理未切分的单个CJK字符
   context.outputToResult();
   //记录本次分词的缓冲区位移
   context.markBufferOffset();          
}

主要的分词逻辑在do循环里，其中segmenters为三个分词器。context内存储当前输入语句，每次循环指针移动一个，即每次去一个字符，然后遍历三个分词器，用每个分词器对当前这个词进行处理。

首先是LetterSegmenter，英文分词器比较简单，就是把连续的英文字符，或者连续的数据进行分词。

然后是CN_QuantifierSegmenter，量词分词器。主要是判断当前的字符是否是数词和量词，会把连起来的数词和量词分成一个词。

最主要的是CJKSegmenter，该分词器就是基于词典匹配的。在介绍主要逻辑之前，需要介绍一个类Lexeme，该类表示一个分词结果，即一个词元

public class Lexeme implements Comparable<Lexeme>{
   //lexemeType常量
   //未知
   public static final int TYPE_UNKNOWN = 0;
   //英文
   public static final int TYPE_ENGLISH = 1;
   //数字
   public static final int TYPE_ARABIC = 2;
   //英文数字混合
   public static final int TYPE_LETTER = 3;
   //中文词元
   public static final int TYPE_CNWORD = 4;
   //中文单字
   public static final int TYPE_CNCHAR = 64;
   //日韩文字
   public static final int TYPE_OTHER_CJK = 8;
   //中文数词
   public static final int TYPE_CNUM = 16;
   //中文量词
   public static final int TYPE_COUNT = 32;
   //中文数量词
   public static final int TYPE_CQUAN = 48;
   
   //词元的起始位移
   private int offset;
    //词元的相对起始位置
    private int begin;
    //词元的长度
    private int length;
    //词元文本
    private String lexemeText;
    //词元类型
    private int lexemeType;
}

该类在切词过程中比较主要的域是begin和length，begin表示该词元在输入语句的起始位置，length表示该词元的长度。

分词的主要逻辑在CJKSegmenter#analyze方法内

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.getSingleton().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.getSingleton().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);
   }
}

我们先看下半部分代码，大概思路就是取当前这次循环中的字符，然后判断是否match。

1）如果match表示：该字符能匹配到词典中的词尾（即3小节描述的红色点）则说明当前这个字符可以作为词的结尾，那么加上前面缓存的bufferoffset就能推出这个词首位未知，然后新建一个Lexeme，放入context内。
2）如果为prefix，则表示当前这个字符不是词的结尾，但是是词的前缀，则放入tmpHits内，tmpHits表示之前的遍历过程中，可以作为词前缀的字符。
3）根本不在词典中，则清空一下临时变量。

有了timpHits，我们再来看上半部分代码：
首先遍历timpHits内的所有字符。
1）如果当前字符和tipHits内的prefix结合能够match的，则新建词元存入context。
2）如果加上当前字符，反而不是prefix了，则从timpsHits中移除

经过一系列的处理，最终会在contenxt内得到一个orgLexemes的QuickSortSet，Lexemes本身是实现了Comparable接口的，并且按照begin的值从小到达排序，如果begin一样，则按照lenght从大到小排序。也就是位置靠前，并且长度较长的词元会排到前排。

以宝剑锋从磨砺出为例，最终得到四个词元 0-7，0-3，0-2，4-6。即宝剑锋从磨砺出、宝剑锋、宝剑、磨砺这四个词元。到这里还只是一种切分方式，和最后的结果：宝剑锋从磨砺出、宝剑锋、宝剑、从、锋、从、磨砺、出。还有些差距。

5.输出结果

从切词到最后的输出，中间其实还有一步，就是其一处理，当设置useSmart为true的时候，会对上面的四个词元进行去除歧义，最后只剩一条词元0-7。这部分逻辑后面再讲，假设没有设置useSmart为true的话，现在还是四条词元，然后准备输出结果，看这中间做了什么事。主要逻辑在AnalyzeContext#outputToResult方法中。

void outputToResult(){
   int index = 0;
   for( ; index <= this.cursor ;){
      //跳过非CJK字符
      if(CharacterUtil.CHAR_USELESS == this.charTypes[index]){
         index++;
         continue;
      }
      //从pathMap找出对应index位置的LexemePath
      LexemePath path = this.pathMap.get(index);
      if(path != null){
         //输出LexemePath中的lexeme到results集合
         Lexeme l = path.pollFirst();
         while(l != null){
            this.results.add(l);
            //字典中无单字，但是词元冲突了，切分出相交词元的前一个词元中的单字
            int innerIndex = index + 1;
            for (; innerIndex < index + l.getLength(); innerIndex++) {
               Lexeme innerL = path.peekFirst();
               if (innerL != null && innerIndex == innerL.getBegin()) {
                  this.outputSingleCJK(innerIndex - 1);
               }
            }
            
            //将index移至lexeme后
            index = l.getBegin() + l.getLength();              
            l = path.pollFirst();
            if(l != null){
               //输出path内部，词元间遗漏的单字
               for(;index < l.getBegin();index++){
                  this.outputSingleCJK(index);
               }
            }
         }
      }else{//pathMap中找不到index对应的LexemePath
         //单字输出
         this.outputSingleCJK(index);
         index++;
      }
   }
   //清空当前的Map
   this.pathMap.clear();
}

该部分的主要逻辑，就是对于那些没有被分词分到的位置，用单字输出的方式输出词元。细心的读者应该已经发现，最后的结果：宝剑锋从磨砺出、宝剑锋、宝剑、从、锋、从、磨砺、出。有两个从字，并且这个输入语句里只有一个从。这个其实是特定的ik版本才有的bug，6.8.1很不幸，存在这个bug。关于这个bug，后面写文章再具体分析。主要有 //字典中无单字，但是词元冲突了，切分出相交词元的前一个词元中的单字这段注释下大代码引起，也是一个ik的pr，不过最新版本已经备注掉了。

6.消除歧义

我们现在再回过头来看，设置useSmart会发生什么。主要逻辑在IKArbitrator#process 方法中

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

当useSmart为true时，进行歧义处理，如果为false，则不处理，直接输出。
将词元转换成词元路径 LexemePath，LexemePath实现了Comparable接口，LexemePath内部的词元不想交，并且根据排序规则进行排序，规则如下

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

根据这个规则，对词元链路进行排序，选择排序第一的词元链路，即最后消除歧义的那个分词方式。

7.总结

IK分词器虽然使用上比较简单，但是了解它内部的原理的思想很重要，能够帮助分析和定位问题。

更多精彩内容，请关注公众号

公众号二维码.jpg

IK分词器原理