当前位置: 首页 > 中文分词, 搜索 > 正文

ik分词源码分析

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

词典结构
1.词典是以树状结构存储的。
2.每个节点是一个字。
3.每个节点还包含所有子节点的集合。
4.最根节点是(char)0
5. 每个节点中存贮子结点的方式有两种
//Map存储结构 子节点个数>3
private Map childrenMap;
//数组方式存储结构 字节点个数<=3
private DictSegment[] childrenArray;
6.每个节点用 private Character nodeChar; 标示
7.当前节点存储的Segment数目 private int storeSize = 0; 递增
8.当前DictSegment状态 ,默认 0 , 1表示从根节点到当前节点的路径表示一个词
private int nodeState = 0;

装载词库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
public synchronized void fillSegment(char[] charArray , int begin , int length){
  //获取字典表中的汉字对象
  Character beginChar = new Character(charArray[begin]);
  Character keyChar = charMap.get(beginChar);
  //字典中没有该字,则将其添加入字典
  if(keyChar == null){
   charMap.put(beginChar, beginChar);
   keyChar = beginChar;
  }
 
  //搜索当前节点的存储,查询对应keyChar的keyChar,如果没有则创建
  DictSegment ds = lookforSegment(keyChar);
  //处理keyChar对应的segment
  if(length > 1){
   //词元还没有完全加入词典树
   ds.fillSegment(charArray, begin + 1, length - 1);
  }else if (length == 1){
   //已经是词元的最后一个char,设置当前节点状态为1,表明一个完整的词
   ds.nodeState = 1;
  }
 
 }
 
 /**
  * 查找本节点下对应的keyChar的segment
  * 如果没有找到,则创建新的segment
  * @param keyChar
  * @return
  */
 private DictSegment lookforSegment(Character keyChar){
 
  DictSegment ds = null;
 
  if(this.storeSize <= ARRAY_LENGTH_LIMIT){
   //获取数组容器,如果数组未创建则创建数组
   DictSegment[] segmentArray = getChildrenArray();   
   //搜寻数组
   for(DictSegment segment : segmentArray){
    if(segment != null && segment.nodeChar.equals(keyChar)){
     //在数组中找到与keyChar对应的segment
     ds =  segment;
    }
   }   
   //遍历数组后没有找到对应的segment
   if(ds == null){
    //构造新的segment
    ds = new DictSegment(keyChar);    
    if(this.storeSize < ARRAY_LENGTH_LIMIT){
     //数组容量未满,使用数组存储
     segmentArray[this.storeSize] = ds;
    }else{
     //数组容量已满,切换Map存储
     //获取Map容器,如果Map未创建,则创建Map
     Map<Character , DictSegment> segmentMap = getChildrenMap();
     //将数组中的segment迁移到Map中
     migrate(segmentArray ,  segmentMap);
     //存储新的segment
     segmentMap.put(keyChar, ds);
     //释放当前的数组引用
     this.childrenArray = null;
    }
    //segment数目+1
    this.storeSize++;
   }   
 
  }else{
   //获取Map容器,如果Map未创建,则创建Map
   Map<Character , DictSegment> segmentMap = getChildrenMap();
   //搜索Map
   ds = (DictSegment)segmentMap.get(keyChar);
   if(ds == null){
    //构造新的segment
    ds = new DictSegment(keyChar);
    segmentMap.put(keyChar , ds);
    //当前节点存储segment数目+1
    this.storeSize ++;
   }
  }
 
  return ds;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
//判断某个词是否匹配
public Hit match(char[] charArray , int begin , int length){
  Character keyChar = new Character(charArray[begin]);
  DictSegment ds = null;
 
  //引用实例变量为本地变量,避免查询时遇到更新的同步问题
  DictSegment[] segmentArray = this.childrenArray;
  Map<Character , DictSegment> segmentMap = this.childrenMap;  
 
  //STEP1 在节点中查找keyChar对应的DictSegment
  if(segmentArray != null){
   //在数组中查找
   for(DictSegment seg : segmentArray){
    if(seg != null && seg.nodeChar.equals(keyChar)){
     //找到匹配的段
     ds = seg;
    }
   }
  }else if(segmentMap != null){
   //在map中查找
   ds = (DictSegment)segmentMap.get(keyChar);
  }
  //STEP2 找到DictSegment,判断词的匹配状态,是否继续递归,还是返回结果
  if(ds != null){   
   if(length > 1){
    //词未匹配完,继续往下搜索
    return ds.match(charArray, begin + 1 , length - 1);
   }else if (length == 1){//搜索最后一个char
    Hit searchHit= new Hit();
 
    if(ds.nodeState == 1){
     //添加HIT状态为完全匹配
     searchHit.setMatch();
    }
    if(ds.hasNextNode()){
     //添加HIT状态为前缀匹配
     searchHit.setPrefix();
    }
    return searchHit;
   }
 
  }  
  //STEP3 没有找到DictSegment, 将HIT设置为不匹配
  return new Hit();  
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 public class Hit {
 //Hit不匹配
 private static final int UNMATCH = 0x00000000;
 //Hit完全匹配
 private static final int MATCH = 0x00000001;
 //Hit前缀匹配
 private static final int PREFIX = 0x00000010;
 
 
 //该HIT当前状态,默认未匹配
 private int hitState = UNMATCH;
 /**
  * 判断是否完全匹配
  */
 public boolean isMatch() {
  return (this.hitState & MATCH) > 0;
 }
 public void setMatch() {
  this.hitState = this.hitState | MATCH;
 }
 /**
  * 判断是否是词的前缀
  */
 public boolean isPrefix() {
  return (this.hitState & PREFIX) > 0;
 }
 public void setPrefix() {
  this.hitState = this.hitState | PREFIX;
 }
 /**
  * 判断是否是不匹配
  */
 public boolean isUnmatch() {
  return this.hitState == UNMATCH ;
 }
 public void setUnmatch() {
  this.hitState = UNMATCH;
 } 
} 
二进制  int     状态
00      0       不匹配
01      1       匹配
10      2       是前缀。(ds.hasNextNode()11      3       比配并且是前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Lexeme  语义单元(词元) 
    //lexemeType常量
 //普通词元
 public static final int TYPE_CJK_NORMAL = 0;
 //姓氏
 public static final int TYPE_CJK_SN = 1;
 //尾缀
 public static final int TYPE_CJK_SF = 2;
 //未知的
 public static final int TYPE_CJK_UNKNOWN = 3;
 //数词
 public static final int TYPE_NUM = 10;
 //量词
 public static final int TYPE_NUMCOUNT = 11;
 //英文
 public static final int TYPE_LETTER = 20;
 
 //词元的起始位移
 private int offset;
    //词元的相对起始位置
    private int begin;
    //词元的长度
    private int length;
    //词元文本
    private String lexemeText;
    //词元类型
    private int lexemeType;
 
    //当前词元的前一个词元
    private Lexeme prev;
    //当前词元的后一个词元
    private Lexeme next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
  /**
 * 分词器上下文状态
 * @author 林良益
 *
 */
public class Context{
 
 //是否使用最大词长切分(粗粒度)
 private boolean isMaxWordLength = false; 
    //记录Reader内已分析的字串总长度
    //在分多段分析词元时,该变量累计当前的segmentBuff相对于reader的位移
 private int buffOffset; 
 //最近一次读入的,可处理的字串长度
 private int available;
    //最近一次分析的字串长度
    private int lastAnalyzed; 
    //当前缓冲区位置指针
    private int cursor; 
    //字符窜读取缓冲
    private char[] segmentBuff;
    /*
     * 记录正在使用buffer的分词器对象
     * 如果set中存在有分词器对象,则buffer不能进行位移操作(处于locked状态)
     */
    private Set<ISegmenter> buffLocker;
    /*
     * 词元结果集,为每次游标的移动,存储切分出来的词元
     */
 private IKSortedLinkSet lexemeSet;
 
 
*******************************************************************************
private class IKSortedLinkSet{
  //链表头
  private Lexeme head;
  //链表尾
  private Lexeme tail;
  //链表的实际大小
  private int size;
 
  /**
   * 向链表集合添加词元  是一个有序的队列。排序方式。是//起始位置优先,再//词元长度优先
   * @param lexeme
   */
  private void addLexeme(Lexeme lexeme){。。}
  /**
   * 取出链表集合的第一个元素
   * @return Lexeme
   */
  private Lexeme pollFirst(){。。。}
  /**
   * 取出链表集合的最后一个元素
   * @return Lexeme
   */
  private Lexeme pollLast(){。。。}
  /**
   * 剔除集合汇总相邻的切完全包含的lexeme
   * 进行最大切分的时候,过滤长度较小的交叠词元
   */
  private void excludeOverlap(){。。。}
***********************************************************************************
分词器接口
public interface ISegmenter {
 
 /**
  * 从分析器读取下一个可能分解的词元对象
  * @param segmentBuff 文本缓冲
  * @param context 分词算法上下文
  */
 void nextLexeme(char[] segmentBuff , Context context);
 
 /**
  * 重置子分析器状态
  */
 void reset();
}
 
***************************************************************************************
/**
 * IK Analyzer v3.2
 * IK主分词器
 * 注:IKSegmentation是一个lucene无关的通用分词器
 * @author 林良益
 *
 */
public final class IKSegmentation{
 
 
 private Reader input; 
 //默认缓冲区大小
 private static final int BUFF_SIZE = 3072;
 //缓冲区耗尽的临界值
 private static final int BUFF_EXHAUST_CRITICAL = 48; 
    //字符窜读取缓冲
    private char[] segmentBuff;
 //分词器上下文
 private Context context;
 //分词处理器列表
 private List<ISegmenter> segmenters;
 
 /**
  * 获取下一个语义单元
  * @return 没有更多的词元,则返回null
  * @throws IOException
  */
 public synchronized Lexeme next() throws IOException {。。。}
  /**
     * 取出词元集合中的下一个词元
     * @return Lexeme
     */
    private Lexeme buildLexeme(Lexeme lexeme){。。。}
***************************************************************************************
private class CSeg{
  /*
   * 词段开始位置
   */
  private int start;
  /*
   * 词段的结束位置
   */
  private int end;
 }
 public void reset() {
  //重置已处理标识
  doneIndex = -1;
  _CSegList.clear();
 }
}
**************************************************************************************
 
/**
 * 中文词元处理子分词器,涵盖一下范围
 * 1.中文词语
 * 2.姓名
 * 3.地名
 * 4.未知词
 * @author 林良益
 *
 */
public class ChineseSegmenter implements ISegmenter {
 /*
  * 已完成处理的位置
  */
 private int doneIndex;
 /*
  * 词段处理队列
  */
 List<CSeg> _CSegList;
 
 
  public void nextLexeme(char[] segmentBuff , Context context) {
 
  //读取当前位置的char 
  char input = segmentBuff[context.getCursor()];
  Hit hit = null;
  if(CharacterHelper.isCJKCharacter(input)){//是中文(CJK)字符,则进行处理
   if(_CSegList.size() > 0){
    //处理词段队列
    List<CSeg> tmpList = new ArrayList<CSeg>(_CSegList);
    for(CSeg seg : tmpList){
     hit = Dictionary.matchInMainDict(segmentBuff, seg.start, context.getCursor() - seg.start + 1);
     if(hit.isMatch()){//匹配成词
      //判断是否有不可识别的词段
      if(seg.start > doneIndex + 1){
       //输出并处理从doneIndex+1 到 seg.start - 1之间的未知词段
       processUnknown(segmentBuff , context , doneIndex + 1 , seg.start - 1);
      }
      //输出当前的词
      Lexeme newLexeme = new Lexeme(context.getBuffOffset() , seg.start , context.getCursor() - seg.start + 1 , Lexeme.TYPE_CJK_NORMAL);
      context.addLexeme(newLexeme);
      //更新goneIndex,标识已处理
      if(doneIndex < context.getCursor()){
       doneIndex = context.getCursor();
      }
 
      if(hit.isPrefix()){//同时也是前缀
       //更新seg.end、seg.type,
       seg.end = context.getCursor();
       //seg.type = CSeg.TYPE_MATCH;
 
      }else{ //后面不再可能有匹配了
       //移出当前的CSeg
       _CSegList.remove(seg);
      }
 
     }else if(hit.isPrefix()){//前缀,未匹配成词
      //更新seg.end、seg.type
      seg.end = context.getCursor();
      //seg.type = CSeg.TYPE_PRE;
 
     }else if(hit.isUnmatch()){//不匹配
      //移出当前的CSeg
      _CSegList.remove(seg);
     }
    }
   }
 
   //处理以input为开始的一个新CSeg
   hit = Dictionary.matchInMainDict(segmentBuff, context.getCursor() , 1);
   if(hit.isMatch()){//匹配成词
    //判断是否有不可识别的词段
    if(context.getCursor() > doneIndex + 1){
     //输出并处理从doneIndex+1 到 context.getCursor()- 1之间的未知
     processUnknown(segmentBuff , context , doneIndex + 1 , context.getCursor()- 1);
    }
    //输出当前的词
    Lexeme newLexeme = new Lexeme(context.getBuffOffset() , context.getCursor() , 1 , Lexeme.TYPE_CJK_NORMAL);
    context.addLexeme(newLexeme);
    //更新doneIndex,标识已处理
    if(doneIndex < context.getCursor()){
     doneIndex = context.getCursor();
    }
 
    if(hit.isPrefix()){//同时也是前缀
     //向词段队列增加新的词段
     CSeg newCSeg = new CSeg();
     newCSeg.start = context.getCursor();
     newCSeg.end = newCSeg.start;
     //newCSeg.type = CSeg.TYPE_MATCH;
     _CSegList.add(newCSeg);
    }
 
   }else if(hit.isPrefix()){//前缀,未匹配成词
    //向词段队列增加新的词段
    CSeg newCSeg = new CSeg();
    newCSeg.start = context.getCursor();
    newCSeg.end = newCSeg.start;
    //newCSeg.type = CSeg.TYPE_PRE;
    _CSegList.add(newCSeg);
 
   }else if(hit.isUnmatch()){//不匹配,当前的input不是词,也不是词前缀,将其视为分割性的字符
    //输出从doneIndex到当前字符(含当前字符)之间的未知词
    processUnknown(segmentBuff , context , doneIndex + 1 , context.getCursor());
    //更新doneIndex,标识已处理
    doneIndex = context.getCursor();
   }
 
  }else {//输入的不是中文(CJK)字符
   if(_CSegList.size() > 0
     &&  doneIndex < context.getCursor() - 1){
    for(CSeg seg : _CSegList){
     //判断是否有不可识别的词段
     if(doneIndex < seg.end){
      //输出并处理从doneIndex+1 到 seg.end之间的未知词段
      processUnknown(segmentBuff , context , doneIndex + 1 , seg.end);
     }
    }
   }
   //清空词段队列
   _CSegList.clear();
   //更新doneIndex,标识已处理
   if(doneIndex < context.getCursor()){
    doneIndex = context.getCursor();
   }
  }
 
  //缓冲区结束临界处理
  if(context.getCursor() == context.getAvailable() - 1){ //读取缓冲区结束的最后一个字符   
   if( _CSegList.size() > 0 //队列中还有未处理词段
    && doneIndex < context.getCursor()){//最后一个字符还未被输出过
    for(CSeg seg : _CSegList){
     //判断是否有不可识别的词段
     if(doneIndex < seg.end ){
      //输出并处理从doneIndex+1 到 seg.end之间的未知词段
      processUnknown(segmentBuff , context , doneIndex + 1 , seg.end);
     }
    }
   }
   //清空词段队列
   _CSegList.clear();
  }
 
  //判断是否锁定缓冲区
  if(_CSegList.size() == 0){
   context.unlockBuffer(this);
 
  }else{
   context.lockBuffer(this);
 
  }
 }

本文固定链接: http://www.chepoo.com/ik-code-analysis.html | IT技术精华网

ik分词源码分析:等您坐沙发呢!

发表评论