java版本结巴分词算法bug[通俗易懂]
大家好，又见面了，我是你们的朋友全栈君。
Never to late。所以明天再做也不会晚
结巴分词的过程是： 1、根据dict.txt中的词库构建一棵trie树，这棵树的实例只有一个，采取单例模式。 2、每来一次分词构造，就顺着trie树进行分词，这将产生很多种结果，于是就生成了一个DGA，分词的有向无环图，终点是句子的左边或者右边（实际上应该分别以左边和右边为终点来做处理）。 3、利用动态规划，从句子的终点开始，到这算回去（这个在动态规划中很常见，概率dp）：对DGA中查找最大的概率的分词路径，路径上的词语就是分词结果。 4、返回分词结果。
bug1：在实现单例模式的时候，作者用的如下方法
public class WordDictionary{
private static WordDictionary singleton;
public static WordDictionary getInstance() {
if (singleton == null) {
synchronized (WordDictionary.class) {
if (singleton == null) {
singleton = new WordDictionary();
return singleton;
}
}
}
return singleton;
}
}这种双重锁的方式，在并发场景下，是不安全的，为了避免java编译器对代码进行重排序，应该改为如下形式
private static volatile WordDictionary singleton;
public static WordDictionary getInstance() {
if (singleton == null) {
synchronized (WordDictionary.class) {
if (singleton == null) {
singleton = new WordDictionary();
return singleton;
}
}
}
return singleton;
}bug2：使用trie树对待分词句子建立DGA的时候采取递归建树，使得大量DictSegment和DictSegment[]堆积，对内存消耗特别严重。使用visual vm进行测试可以发现，将该分词加入到项目中一段时间后，在内存中可以看见DictSegment和DictSegment[]的占比非常高，如果老年代不够大，很有可能会引起OutOfMemory的异常
Hit match(char[] charArray, int begin, int length, Hit searchHit) {
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]);
//该keyChar对应的DictSegment
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;
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/149054.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
