东莞市盛裕绒艺玩具有限公司

东莞市盛裕绒艺玩具有限公司

lzyq858游戏

18509552024
新闻资讯
联系方式
全国服务热线: 18509552024

咨询热线:13556085153
联系人:马悠悠
地址:宁夏 银川 市市城区解放东街3号

IK 分词器源码阅读笔记(1)

来源:lzyq858游戏   发布时间:2019-11-12   点击量:63

1.Hit 类

这个类只包含几个状态位,用于判断匹配的类型。 结构很简单 主要是几个常量:

//Hit不匹配private static final int UNMATCH = 0x00000000;//Hit完全匹配private static final int MATCH = 0x00000001;//Hit前缀匹配private static final int PREFIX = 0x00000010;默认状态是UNMATCHprivate int hitState = UNMATCH;

同时还有词段的开始和结束为止

//词段开始位置private int begin;//词段的结束位置private int end;

补充一个DictSegment类的对象,存储词典匹配过程中,当前匹配到的词典分支节点

private DictSegment matchedDictSegment;

暴露出来的公共方法

isMatch判断是否完全匹配 isPrefix判断是否是词的前缀 isUnmatch判断是否是不匹配 以及对应的set方法

2.DictSegment 类

主要功能是存储字典使用。我的理解,这个类就是tire词典数中的每一个节点, 内置HashMap和Array两个结构,默认有一个数组limit值,为3。也就是说当存储字符不超过3的情况下,使用数组存放,如果超过3个,就用map存放。个人理解使用数组是为了节省存储空间,使用map是为了达到o(1)的查找效率。

先看一下field:

charMap 存储字符用的map ARRAY_LENGTH_LIMIT 数组上界,超过这个大小就是用map结构 childrenArray 数组存储结构 childrenMap map存储结构 nodeChar 当前节点是哪个字 storeSize 当前节点存储的segment数 nodeState 从根节点到当前节点是不是一个完整的词语,1是完整词语,0不是完整词语。

接下来就是几个核心的方法及其变种方法:

第一个核心方法:

fillSegment,参数(char[] charArray , int begin , int length , int enabled) charArray就是一个词语转成的char数组 begin是当前这个字位于charArrary的index length是后面还有几个字(如果当前字符是词语的最后一个字,length=1) enable是给停用词或者非停用词做标志位是哟,enable=0为停用词,enable=1为非停用词。

作用是将词语转换成tire词典中的节点。 代码如下:

      { charMap中没有charArray[begin],没有则添加 Character beginChar = new Character(charArray[begin]); Character keyChar = charMap.get(beginChar); //字典中没有该字,则将其添加入字典 if(keyChar == null){ charMap.put(beginChar, beginChar); keyChar = beginChar; } 通过lookforSegment寻找charArray[begin]对应DictSegment的存储,enable表示没有则创建 DictSegment ds = lookforSegment(keyChar , enabled); 如果找到了,分情况进行处理 if(ds != null){ //处理keyChar对应的segment if(length > 1){ //length大于1,说明当前还不是词语的结尾,需要继续递归,词元并没有完全加入词典树 ds.fillSegment(charArray, begin + 1, length - 1 , enabled); }else if (length == 1){ //已经是词元的最后一个char,设置当前节点状态为enabled, //enabled=1表明一个完整的词,enabled=0表示从词典中屏蔽当前词 ds.nodeState = enabled; } } }  

顺带说一下其中出现的lookforSegment: lookforSegment方法,参数(Character keyChar , int create)

keyChar 待寻找的char create =1如果没有找到,则创建新的segment ; =0如果没有找到,不创建,返回null

作用是根据keyChar 找到其对应的DictSegment,如果找不到根据标识位决定是否进行创建。作者本身注释已经很全面了,在这里仅作补充

      private DictSegment lookforSegment(Character keyChar , int create){ DictSegment ds = null;//用于返回的DictSegment值 if(this.storeSize <= ARRAY_LENGTH_LIMIT){//没有达到数组最大值,说明使用数组进行存储 //获取数组容器,如果数组未创建则创建数组 DictSegment[] segmentArray = getChildrenArray();//获取数组对象,如果为空则创建,不为空则直接使用(childrenArray) //搜寻数组 DictSegment keySegment = new DictSegment(keyChar);//根据keyChar创建一个DictSegment int position = Arrays.binarySearch(segmentArray, 0 , this.storeSize, keySegment);//二分法查找 if(position >= 0){ ds = segmentArray[position];//找到则赋值给ds并用于返回值 } //遍历数组后没有找到对应的segment if(ds == null && create == 1){//如果没找到,并且需要进行创建 ds = keySegment;//将创建好的keySegment赋值给ds if(this.storeSize < ARRAY_LENGTH_LIMIT){//检查是否达到数组最大值 //数组容量未满,使用数组存储 segmentArray[this.storeSize] = ds; //segment数目+1 this.storeSize++; Arrays.sort(segmentArray , 0 , this.storeSize);//排序(用于二分法查找) }else{ //数组容量已满,切换Map存储 Map<Character , DictSegment> segmentMap = getChildrenMap();//获取Map容器,如果Map未创建,则创建Map //将数组中的segment迁移到Map中 migrate(segmentArray , segmentMap); //存储新的segment segmentMap.put(keyChar, ds); //segment数目+1 , 必须在释放数组前执行storeSize++ , 确保极端情况下,不会取到空的数组 this.storeSize++; //释放当前的数组引用 this.childrenArray = null; } } }else{//在此之前已经达到了数组最大值,从map中查找 //获取Map容器,如果Map未创建,则创建Map Map<Character , DictSegment> segmentMap = getChildrenMap(); //搜索Map ds = (DictSegment)segmentMap.get(keyChar); if(ds == null && create == 1){//如果没找到,并且需要创建新的segment //构造新的segment ds = new DictSegment(keyChar); segmentMap.put(keyChar , ds); //当前节点存储segment数目+1 this.storeSize ++; } } return ds; }

  getChildrenArray,getChildrenMap,migrate三个方法比较简单,前两个是判断一下是否为空,为空则创建,注意下线程安全就好(作者好像没有考虑指令重排的情况),migrate方法就是把数据从array中转存到map中,就不多进行分析了。

接下来是另外一个重头方法match方法:

match方法参数(char[] charArray , int begin , int length , Hit searchHit) 前三个参数和fillSegment一模一样,hit也介绍了,就是用于存放匹配结果。 直接看方法:

{ //searchHit开始可能为空,为空则创建,不为空则将hit设置为unmatch状态。 if(searchHit == null){ //如果hit为空,新建 searchHit= new Hit(); //设置hit的其实文本位置 searchHit.setBegin(begin); }else{ //否则要将HIT状态重置 searchHit.setUnmatch(); } //设置hit的当前处理位置 searchHit.setEnd(begin); 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){ //在数组中查找 DictSegment keySegment = new DictSegment(keyChar); int position = Arrays.binarySearch(segmentArray, 0 , this.storeSize , keySegment); if(position >= 0){ ds = segmentArray[position]; } }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 , searchHit); }else if (length == 1){ //搜索最后一个char if(ds.nodeState == 1){ //添加HIT状态为完全匹配 searchHit.setMatch(); } if(ds.hasNextNode()){ //添加HIT状态为前缀匹配 searchHit.setPrefix(); //记录当前位置的DictSegment searchHit.setMatchedDictSegment(ds); } return searchHit; } } //STEP3 没有找到DictSegment, 将HIT设置为不匹配 return searchHit; }

  

3.Dictionary 类

一个典型的懒加载单例模式类,不过没有考虑指令重排

先说一下几个主要的field_MainDict 主要词典_StopWordDict 停用词词典_QuantifierDict 量词词典singleton 真正词典实例cfg 配置文件

还有两个默认Path路径(内置Main和Quantifier词典路径) 方法也不是太多,很容易理解

getInstance 不多说了,获取实例对象 addWords 批量增加单词的 disableWords 批量过滤的 matchInMainDict 主词典是否匹配 matchInQuantifierDict 量词词典是否匹配 isStopWord 是否是停用词 loadMainDict 加载主词典(内置) loadExtDict 加载外部词典 loadStopWordDict 加载停用词词典 loadQuantifierDict 加载量词词典 matchWithHit 从已匹配的Hit中直接取出DictSegment,继续向下匹配

上述方法基本都是对DictSegment中的match方法进行封装,要么就是直接读取dic,比较容易,就不过多分析了。

上述3个类了解之后,基本上来说就算是熟悉了字典树的生成(Tire词典),match匹配的过程了。

4.测试一下基于字典的Dag,并实现分词

一个创建Dag的方法,主要是判断字典中是否包含对应的key,在此之前现根据标点符号进行切分。

    private static Map<Integer,List<Integer>> getDag(String text){ Map<Integer,List<Integer>> dagMap = new HashMap<>(); int length = text.length(); for (int i = 0; i < length; i++) { List<Integer> list = new ArrayList<>(); int k = i; String subStr; while (k<length ){ subStr =text.substring(i,k+1); if (dict.containsKey(subStr)){ list.add(k); } k++; } if (list.isEmpty()) list.add(i); dagMap.put(i,list); } return dagMap; }

  

代码还是很好理解的,接受到字符串。字符串长度从1开始一直到结束,检查字典中是否包含,这个应该输属于最大力度切分了,算法复杂度O(n^2),应该有优化空间吧。

dict声明及初始化如下:

private static Map<String,Integer> dict = new HashMap<>(); static { load("dict",dict); } private static void load(String fileName,Map<String,Integer> map,boolean flag){ try { InputStream stream = Main.class.getClassLoader().getResource("com/company/"+fileName).openStream(); try (BufferedReader reader = new BufferedReader(new InputStreamReader(stream))) { String line; while ((line=reader.readLine())!=null){ String[] arr = line.split(" "); String str=arr[0]; Integer num = Integer.parseInt(arr[1]); map.put(str,num); } } } catch (IOException e) { e.printStackTrace(); } }在Main函数中测试一下:

public static void main(String[] args) throws IOException { String text="一花一世界"; Map<Integer, List<Integer>> dag = getDag(text); System.out.println(dag); for (List<Integer> list : dag.values()) { Integer start = list.remove(0); if (list.size() == 0) System.out.println(text.charAt(start)); else for (Integer end : list) { System.out.println(text.substring(start,end+1)); } } }输出结果如下:

{0=[0], 1=[1], 2=[2, 3], 3=[3, 4], 4=[4]}一花一世世界界

最大粒度切分基本就这样,后面还有歧义处理部分。

相关产品

COPYRIGHTS©2017 lzyq858游戏 ALL RIGHTS RESERVED 备案号:63