IK分词器原理
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
