最近在研究中文分词的相关内容，决定从一个小项目练起，实现简单效果不错，主要内容是基于结巴分词JAVA版本，可以满足大部分需要，如有不足之处还请多多指教。
模式
- Search模式，用于对用户查询词分词
- Index模式，用于对索引文档分词
算法
- 基于 trie 树结构实现高效词图扫描
- 生成所有切词可能的有向无环图 DAG
- 采用动态规划算法计算最佳切词组合
- 基于 HMM 模型，采用 Viterbi (维特比)算法实现未登录词识别
首先先从源码架构来分析大致分为三步：预处理，按登录词切分，按照HMM处理未登录词。JAVA版本相比python算法实现基本一致，只是进行了略微的修改并且添加了搜狗细胞词库和用户词库等。
原理
-
加载词库（包括来自语料库的词，python原作者统计来自于人民日报等）搜狗词库、用户自定义词典, 生成trie树（还采用了python版本原作者训练的概率表，包括位置转换概率，位置到单字的发射概率，词语以某种状态开头的概率，其中发射概率在资源文件中）
-
给定待分词的句子切分成 短语列表, 对每个短语使用DAG(查字典)和动态规划, 得到最大概率路径（这里相当于最短路径）, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词.
相关知识
1.trie树字典树，详见http://blog.csdn.net/abcd_d_/article/details/40116485
2.JavaIO方面知识，详见https://www.cnblogs.com/oubo/archive/2012/01/06/2394638.html
3.动态规划，详见http://blog.csdn.net/yuih344/article/details/78994776
4.概率统计模型分词基本概念，详见http://blog.csdn.net/yuih344/article/details/78996396
5.HMM，用到的机器学习核心算法详见https://www.cnblogs.com/skyme/p/4651331.html
6.维特比算法，详见http://blog.csdn.net/yuih344/article/details/78995119
代码解析
代码我加了很多自己的注释，应该是比较清楚了，基本分为三个层次来讲，这一部分设计到第一步，即为，预处理，包括初始化等，是分词的第一步，基本包括词典词库的载入，字典树词典的初始化以及填充等工作，生成字典树，还有一点我的代码顺序基本是按照调用顺序来的。
1.初始化调用不用多讲，通过初始化调用，及构造方法中的调用，载入用户和搜狗细胞词库，这里值得注意一点的是，实例的产生作者用了线程安全的单例模式，这也就是说在多线程调用的情况下不会出现线程安全的问题
protected void setUp() throws Exception {
WordDictionary.getInstance().init(Paths.get("conf"));
}
public void init(Path configFile) {
String abspath = configFile.toAbsolutePath().toString();
System.out.println("initialize user dictionary:" + abspath);
synchronized (WordDictionary.class) {
if (loadedPath.contains(abspath))
return;
DirectoryStream<Path> stream;
try {
stream = Files.newDirectoryStream(configFile, String.format(Locale.getDefault(), "*%s", USER_DICT_SUFFIX));
for (Path path: stream){
System.err.println(String.format(Locale.getDefault(), "loading dict %s", path.toString()));
singleton.loadUserDict(path);
}
loadedPath.add(abspath);
} catch (IOException e) {
// TODO Auto-generated catch block
// e.printStackTrace();
System.err.println(String.format(Locale.getDefault(), "%s: load user dict failure!", configFile.toString()));
}
}
}
//构造方法加载词典
private WordDictionary() {
this.loadDict();
}
public static WordDictionary getInstance() {
if (singleton == null) {
synchronized (WordDictionary.class) {
if (singleton == null) {
singleton = new WordDictionary();
return singleton;
}
}
}
return singleton;
}
public void loadUserDict(Path userDict) {
loadUserDict(userDict, StandardCharsets.UTF_8);
}
//加载用户词典和细胞词库，初始化时完成
public void loadUserDict(Path userDict, Charset charset) {
try {
BufferedReader br = Files.newBufferedReader(userDict, charset);
long s = System.currentTimeMillis();
int count = 0;
while (br.ready()) {
String line = br.readLine();
String[] tokens = line.split("[\t ]+");//匹配制表符号一次或多次，然后每行切分
if (tokens.length < 1) {
// Ignore empty line
continue;
}
String word = tokens[0];//前一位置为词，后一个位置是词的频度
double freq = 3.0d;//默认为3
if (tokens.length == 2)
freq = Double.valueOf(tokens[1]);
word = addWord(word);
freqs.put(word, Math.log(freq / total));//对频率取log，放在map结构中
count++;
}
System.out.println(String.format(Locale.getDefault(), "user dict %s load finished, tot words:%d, time elapsed:%dms", userDict.toString(), count, System.currentTimeMillis() - s));
br.close();
}
catch (IOException e) {
System.err.println(String.format(Locale.getDefault(), "%s: load user dict failure!", userDict.toString()));
}
}
2.填词，Dictsegment表示字典树的一个分支，也可以理解为一个节点，存储字符，节点的子节点采用数组（DictSegment[]）或map（Map(Character, DictSegment)）存储，选用标准根据子节点的数量而定。如果子节点的数量小于等于ARRAY_LENGTH_LIMIT，采用数组存储；如果子节点的数量大于ARRAY_LENGTH_LIMIT，采用Map存储。ARRAY_LENGTH_LIMIT默认为3。这样做好处在于，节省内存空间。因为HashMap的方式的方式，肯定是需要预先分配内存的，就可能会存在浪费的现象，但如果全都采用数组去存组（后续采用二分的方式查找），你就无法获得O（1）的算法复杂度。所以这里采用了两者方式，当子节点数很少时，用数组存储，当子结点数较多时候，则全部迁至hashMap中去。在构建过程中，会将每个词一步步地加入到字典树中，这是一个递归的过程
private String addWord(String word) {
if (null != word && !"".equals(word.trim())) {
String key = word.trim().toLowerCase(Locale.getDefault());
_dict.fillSegment(key.toCharArray());
return key;
}
else
return null;
}
private synchronized void fillSegment(char[] charArray, int begin, int length, int enabled){
// 获取字典表中的汉字对象
Character beginChar = new Character(charArray[begin]);
Character keyChar = charMap.get(beginChar);//用以检验字典表中是否含有该中文字符
// 字典中没有该字，则将其添加入字典
if (keyChar == null) {//填入词中keychar和beginchar相同
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;
}
}
}
private DictSegment lookforSegment(Character keyChar, int create) {//在分支中查找
DictSegment ds = null;
if (this.storeSize <= ARRAY_LENGTH_LIMIT) {
// 获取数组容器，如果数组未创建则创建数组
DictSegment[] segmentArray = getChildrenArray();
// 搜寻数组
DictSegment keySegment = new DictSegment(keyChar);
//由于二分查找，数组需要有序从而下面排序
int position = Arrays.binarySearch(segmentArray, 0, this.storeSize, keySegment);
if (position >= 0) {
ds = segmentArray[position];
}
// 遍历数组后没有找到对应的segment
if (ds == null && create == 1) {
ds = keySegment;
if (this.storeSize < ARRAY_LENGTH_LIMIT) {
// 数组容量未满，使用数组存储
segmentArray[this.storeSize] = ds;
// segment数目+1
this.storeSize++;
Arrays.sort(segmentArray, 0, this.storeSize);
}
else {
// 数组容量已满，切换Map存储
// 获取Map容器，如果Map未创建,则创建Map
Map<Character, DictSegment> segmentMap = getChildrenMap();
// 将数组中的segment迁移到Map中
migrate(segmentArray, segmentMap);
// 存储新的segment
segmentMap.put(keyChar, ds);
// segment数目+1 ， 必须在释放数组前执行storeSize++ ， 确保极端情况下，不会取到空的数组
this.storeSize++;
// 释放当前的数组引用
this.childrenArray = null;
}
}
}
else {
// 获取Map容器，如果Map未创建,则创建Map
Map<Character, DictSegment> segmentMap = getChildrenMap();
// 搜索Map
ds = (DictSegment) segmentMap.get(keyChar);
if (ds == null && create == 1) {
// 构造新的segment
ds = new DictSegment(keyChar);
segmentMap.put(keyChar, ds);
// 当前节点存储segment数目+1
this.storeSize++;
}
}
return ds;
}
3.在上一条解析中已经完成读入并生成了字典树，初始化基本完成，接下来读入词条，按照分词模式进行分词。
public void testCutForSearch() {
for (String sentence : sentences) {
List<SegToken> tokens = segmenter.process(sentence, SegMode.SEARCH);//List返回
System.out.print(String.format(Locale.getDefault(), "\n%s\n%s", sentence, tokens.toString()));
}
}
public List<String> sentenceProcess(String sentence) {
List<String> tokens = new ArrayList<String>();
int N = sentence.length();
Map<Integer, List<Integer>> dag = createDAG(sentence);//存储合法句子生成的DAG
Map<Integer, Pair<Integer>> route = calc(sentence, dag);//存储当前句子的最大切分路径,这个map中比dag多存了已切分句子的频度
int x = 0;
int y = 0;
String buf;
StringBuilder sb = new StringBuilder();
while (x < N) {//已经成词的加到tokens中
y = route.get(x).key + 1;
String lWord = sentence.substring(x, y);
if (y - x == 1)//切分之后长度为1的字符
sb.append(lWord);//未成词的加到sb中
else {
if (sb.length() > 0) {
buf = sb.toString();
sb = new StringBuilder();
if (buf.length() == 1) {//若当前已经成词，但是之前有一个未成词的直接添加
tokens.add(buf);
}
else {//若有两个或大于两个连续未成词的如果字典包含，则加入，若字典不包含则调用finalSeg.cut，说明是bigram model二元模型
if (wordDict.containsWord(buf)) {
tokens.add(buf);
}
else {
finalSeg.cut(buf, tokens);
}
}
}
tokens.add(lWord);
}
x = y;
}
buf = sb.toString();
if (buf.length() > 0) {
if (buf.length() == 1) {
tokens.add(buf);
}
else {
if (wordDict.containsWord(buf)) {
tokens.add(buf);
}
else {
finalSeg.cut(buf, tokens);
}
}
}
return tokens;
}
}
4.经过以上函数处理基本完成登陆词的识别，在finalSeg.cut(buf, tokens)方法中完成未登陆词识别，对于未登录的词要采用HMM模型用维特比算法进行解码
for (int i = 0; i < sentence.length(); ++i) {
char ch = sentence.charAt(i);
if (CharacterUtil.isChineseLetter(ch)) {//英文及其他字符遇到中文
if (other.length() > 0) {
processOtherUnknownWords(other.toString(), tokens);
other = new StringBuilder();
}
chinese.append(ch);
}
else {
if (chinese.length() > 0) {
viterbi(chinese.toString(), tokens);
chinese = new StringBuilder();
}
other.append(ch);
}
}
if (chinese.length() > 0)
viterbi(chinese.toString(), tokens);
else {
processOtherUnknownWords(other.toString(), tokens);
}
}
如上这段代码包含对中英文的区别，可以看出，结巴分词同样可以处理英文数字等字符
private void processOtherUnknownWords(String other, List<String> tokens) {//正则匹配等处理非中文字符串
Matcher mat = CharacterUtil.reSkip.matcher(other);
int offset = 0;
while (mat.find()) {
if (mat.start() > offset) {
tokens.add(other.substring(offset, mat.start()));
}
tokens.add(mat.group());
offset = mat.end();
}
if (offset < other.length())
tokens.add(other.substring(offset));
}
下面是采用维特比算法对未登录词进行处理，可以看出BMES序列标注可以看做一阶马尔科夫模型，类似于一种bigram，考虑前一个状态的约束
public void viterbi(String sentence, List<String> tokens) {
Vector<Map<Character, Double>> v = new Vector<Map<Character, Double>>();//可看做句子对应序列存储当前位置概率
Map<Character, Node> path = new HashMap<Character, Node>();
v.add(new HashMap<Character, Double>());
for (char state : states) {
Double emP = emit.get(state).get(sentence.charAt(0));//四个状态中取出该值的概率
if (null == emP)
emP = MIN_FLOAT;
v.get(0).put(state, start.get(state) + emP);//以当前字开始四种概率
path.put(state, new Node(state, null));
}
for (int i = 1; i < sentence.length(); ++i) {
Map<Character, Double> vv = new HashMap<Character, Double>();
v.add(vv);
Map<Character, Node> newPath = new HashMap<Character, Node>();
for (char y : states) {
Double emp = emit.get(y).get(sentence.charAt(i));
if (emp == null)
emp = MIN_FLOAT;
Pair<Character> candidate = null;
for (char y0 : prevStatus.get(y)) {
Double tranp = trans.get(y0).get(y);
if (null == tranp)
tranp = MIN_FLOAT;
tranp += (emp + v.get(i - 1).get(y0));
if (null == candidate)
candidate = new Pair<Character>(y0, tranp);
else if (candidate.freq <= tranp) {
candidate.freq = tranp;
candidate.key = y0;
}
}
vv.put(y, candidate.freq);//存放四种状态和前面候选的最大频率
newPath.put(y, new Node(y, path.get(candidate.key)));//存放状态路径
}
path = newPath;
}
//可以看做是以E或S结尾
double probE = v.get(sentence.length() - 1).get('E');
double probS = v.get(sentence.length() - 1).get('S');
Vector<Character> posList = new Vector<Character>(sentence.length());
Node win;
if (probE < probS)
win = path.get('S');
else
win = path.get('E');
while (win != null) {
posList.add(win.value);
win = win.parent;
}
Collections.reverse(posList);
int begin = 0, next = 0;
for (int i = 0; i < sentence.length(); ++i) {
char pos = posList.get(i);
if (pos == 'B')
begin = i;
else if (pos == 'E') {
tokens.add(sentence.substring(begin, i + 1));
next = i + 1;
}
else if (pos == 'S') {
tokens.add(sentence.substring(i, i + 1));
next = i + 1;
}
}
if (next < sentence.length())
tokens.add(sentence.substring(next));
}
然后大功告成，基本实现了一个简单版本的分词器。
接下来我说我的一些思考：
结巴分词采用HMM模型，之前通过词典的匹配生成DAG，中文分词本身难度较大，采用这种方法最大的特点就是简单快速，字典树采用空间换时间的方法来提高匹配的效率，也带来一些自身的缺点，比如字典占用空间问题，而对于未登录词的识别采用HMM模型，其中概率表上采用位置到单字的发射概率，这一点我认为可能也是HMM算法的局限型所在，较强的独立输出假设，在字与字之间判别可能会有一些问题，因为汉字之间的概率关系并没有考虑到，因此其分词的准确率很大程度依然依赖于DAG，而由于短词相乘概率会变得很小，分词也将会偏向于处理长句，可能这都是传统机器学习算法的局限性，所以现在nlp转而在深度学习方面进展的如火如荼，可是最后到底能达到怎样的效果谁又知道呢，我个人觉得吧，自然语言很多时候难度在于知识的世界性，现在网络用语时不时就能造出一个词来，而机器并不能像人类一样很快的学习，这也是中文有异于图像啊语音等等深度学习应用发展比较好的，他少了某些共性可以量化计算的东西，而word2vec用来量化所谓的词向量，我觉得其实吧可能还不是那么靠谱，就像谁知道几年后AI会是什么样呢，就像现在感觉研究生毕业可能AI都要玩完了，不管怎么样，还是拭目以待吧。