1.Hit 类
这个类只包含几个状态位，用于判断匹配的类型。
结构很简单
主要是几个常量：
//Hit不匹配 private static final int UNMATCH = 0x00000000; //Hit完全匹配 private static final int MATCH = 0x00000001; //Hit前缀匹配 private static final int PREFIX = 0x00000010; 默认状态是UNMATCH private 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]}
一
花
一世
世界
界
最大粒度切分基本就这样，后面还有歧义处理部分。