结巴分词（Java版）的学习与详解

对github上的结巴分词项目的Java移植版的源码学习，欢迎对中文分词与文本模式识别有兴趣的朋友来讨论。

起源

最近发现一个很平常但是很多人没有加以思考的问题：为什么在文本编辑器和浏览器中对文本双击时会自动选中一个词组而不是只选中单字呢？背后的分词算法是怎么样的，为什么这么迅速？在github上我发现了一个比较火的分词算法–结巴分词，通过这个项目，我想应该能够对分词算法有一个更好的了解。

项目地址

这是结巴分词原始版本(python编写)的项目地址：
https://github.com/fxsjy/jieba

这是结巴分词Java移植版本的项目地址：
https://github.com/huaban/jieba-analysis

需要使用结巴分词的朋友可以去这两个仓库fork一下。
本文主要对Java移植版本的代码进行学习。

测试示例与项目入口

如果你只是想使用结巴分词，只需要这几行代码就可以了：

JiebaSegmenter segmenter = new JiebaSegmenter();
String[] sentences =
       new String[] {"这是一个伸手不见五指的黑夜。我叫张枫旸，我爱北京邮电大学，我爱Java和Scala"};
for (String sentence : sentences) {
    System.out.println(segmenter.process(sentence, JiebaSegmenter.SegMode.INDEX).toString());
}

这里我只在sentences里面加了一句话，当然你可以加入多句话。JiebaSegmenter的process方法是主要的调用接口，该方法接收的第二个参数可以是INDEX和SEARCH，分别代表的意义我们在之后再说。
run之后，结果是这样的：

main dict load finished, time elapsed 1092 ms
model load finished, time elapsed 73 ms.
[[这是, 0, 2], [一个, 2, 4], [伸手, 4, 6], [不见, 6, 8], [五指, 8, 10], [伸手不见五指, 4, 10], [的, 10, 11], [黑夜, 11, 13], [。, 13, 14], [我, 14, 15], [叫, 15, 16], [张枫, 16, 18], [旸, 18, 19], [，, 19, 20], [我, 20, 21], [爱, 21, 22], [北京, 22, 24], [邮电, 24, 26], [电大, 25, 27], [大学, 26, 28], [北京邮电大学, 22, 28], [，, 28, 29], [我, 29, 30], [爱, 30, 31], [java, 31, 35], [和, 35, 36], [scal, 36, 40], [a, 40, 41]]

我们看到，除了scala这个词没有被分解对，其他的词都没有错误，所以说算法的准确性还是很高的，而且效率也不错，用python版本的应该还要快上不少，而且之前所说在浏览器和文本编辑器中的应用只需要处理很小的一个语块，所以应该非常快。
我们的疑惑解决了，现在可以看一看具体的算法了。

process方法

首先看看刚才提到的调用入口process方法，直接上代码（做了一些小的修改，原来的代码好像没怎么考虑代码的长度和美观，明明加半句话的判断就可以的事儿，非把一样的几十行代码粘了一遍，搞得我开始没看懂是干啥）。

public List<SegToken> process(String paragraph, SegMode mode) {
    List<SegToken> tokens = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    int offset = 0;
    for (int i = 0; i < paragraph.length(); ++i) {
        char ch = CharacterUtil.regularize(paragraph.charAt(i));
        //如果找到的是中文字符且不是最后一个，都加入处理语块中
        if (CharacterUtil.ccFind(ch) && i!= paragraph.length()-1 )
            sb.append(ch);
        //遇到标点符号或尾部，开始处理语块
        else {
            if (sb.length() > 0) {
                //开始处理
                //SEARCH模式下，只处理一次句子，不对长的词句再次分解
                if (mode == SegMode.SEARCH) {
                    for (String word : sentenceProcess(sb.toString())) {
                        tokens.add(new SegToken(word, offset, offset += word.length()));
                    }
                }
                //INDEX模式下，对长的词句不仅将其自身加入token，并且将其中的长度为2和3的词也加入token中
                if (mode == SegMode.INDEX) {
                    for (String token : sentenceProcess(sb.toString())) {
                        if (token.length() > 2) {
                            String gram2;
                            int j = 0;
                            for (; j < token.length() - 1; ++j) {
                                gram2 = token.substring(j, j + 2);
                                if (wordDict.containsWord(gram2))
                                    tokens.add(new SegToken(gram2, offset + j, offset + j + 2));
                            }
                        }
                        if (token.length() > 3) {
                            String gram3;
                            int j = 0;
                            for (; j < token.length() - 2; ++j) {
                                gram3 = token.substring(j, j + 3);
                                if (wordDict.containsWord(gram3))
                                    tokens.add(new SegToken(gram3, offset + j, offset + j + 3));
                            }
                        }
                        tokens.add(new SegToken(token, offset, offset += token.length()));
                    }
                }
                sb = new StringBuilder();
                offset = i;
            }
            //将标点符号也加入token中
            if (wordDict.containsWord(paragraph.substring(i, i + 1))) {
                tokens.add(new SegToken(paragraph.substring(i, i + 1), offset, ++offset));
            }
            else {
                tokens.add(new SegToken(paragraph.substring(i, i + 1), offset, ++offset));
            }
        }
    }
    return tokens;
}

关键的判断点我做了注释应该比较好看懂，INDEX和SEARCH模式的区别也在注释里，可以分情况使用。我们看到在开头创建了一个tokens列表，后面将分好的词存在这里面返回了，包括标点符号。那么tokens中的每个token是怎么分出来的呢？接下来进入下一步代码解析：JiebaSegmenter的sentenceProcess方法。

sentenceProcess方法

sentenceProcess方法包含了结巴分词的所有关键算法，它们包括：
1.Trie前缀树（用来形成字典）
2.DAG有向无环图（用来形成句子的构成路径）
3.HMM隐马尔科夫模型
4.Viterbi维特比算法（用来组合未组成词的单字）

Trie前缀树

如图，Trie是一种有序树，每个节点的所有子孙都有着相同的前缀，根节点则对应空字符串。
项目中使用trie的地方在形成字典的DictSegment类中。初始化字典时，每次加入一个字典里的词，就让该类的对象递归地调用fillSegment方法，形成一个trie。每个节点存着自己的子节点组成的列表。这样可以方便之后的匹配工作。匹配工作在match()函数中进行，在下面DAG的形成中会用到。

DAG有向无环图

如图所示即是一种简单的有向无环图，任意一条路径表示句子的一种组成方式。也就是说，如果能得到这张图中每条线段的起点和终点，我们就能得到给定句子的所有分解方法。下面还是贴上代码和注释：

private Map<Integer, List<Integer>> createDAG(String sentence) {
    Map<Integer, List<Integer>> dag = new HashMap<>();
    //获得Trie
    DictSegment trie = wordDict.getTrie();
    char[] chars = sentence.toCharArray();
    int N = chars.length;
    int i = 0, j = 0;
    while (i < N) {
        //尝试从尾部开始，词长度不断增长地匹配字典中的词
        Hit hit = trie.match(chars, i, j - i + 1);
        if (hit.isPrefix() || hit.isMatch()) {
            if (hit.isMatch()) {
                if (!dag.containsKey(i)) {
                    List<Integer> value = new ArrayList<>();
                    //在有向无环图中加入一个点，相当于记下线段首部
                    dag.put(i, value);
                    //将线段的尾部记下来
                    value.add(j);
                }
                else
                    dag.get(i).add(j);
            }
            //如果只是前缀而没有完全匹配，则词长度向后加一
            //如果匹配到，则词长度向后加一，碰到结尾则重新初始化
            j += 1;
            if (j >= N) {
                i += 1;
                j = i;
            }
        }
        //没有匹配成功，则为无法组词的单字，放到while循环外统一处理
        else {
            i += 1;
            j = i;
        }
    }
    //把未被匹配的单字加入有向无环图
    for (i = 0; i < N; ++i) {
        if (!dag.containsKey(i)) {
            List<Integer> value = new ArrayList<>();
            value.add(i);
            dag.put(i, value);
        }
    }
    System.out.println(dag);
    return dag;
}

到此为止我们已经获得了有向无环图，下一步计算出最大可能的路径，我们就可以完成分词了。这个计算的过程在calc函数中，找到最大可能的路径并不难，因为字典里的所有词都有频率。关键是这个函数之后，在sentenceProcess函数中还需要对DAG中剩下的单字尝试组词，使结果更完美一点。基本的逻辑是，这些剩下的单字，如果是单独一个单字的话，直接加入tokens里面返回到process函数即可，如果是多个单字的话，需要用一个viterbi算法尝试将它们组词。不过之前需要先对隐马尔科夫模型有一个了解。

HMM隐马尔科夫模型

根据维基百科上的解释，马尔科夫模型用来描述一个含有未知参数的马尔科夫过程，关键点在于从可观察的参数中确定该过程的隐含参数，然后利用这些参数做进一步的分析。中文分词算法里这个模型的使用非常普遍。
在隐马尔科夫模型中，状态并不是直接可见的，只有受状态影响的某些变量是可见的，每一个状态根据一个概率分布输出符号，因此可以根据输出符号的序列解析出状态序列的一些信息。
在结巴分词中，FinalSeg类的LoadModel()建立了一个HMM模型，并将该模型用一个数组和四个Map表示。
首先，数组states中存储了状态值的集合{‘B’,’M’,’E’,’S’},分别代表Begin，Middle，End和Single。顾名思义。
第二，在prevStatus中，定义了状态之间的转移关系，比如B的前面只可能是E或者S，因为很明显作开头的字不会出现在中间字之后。

prevStatus = new HashMap<Character, char[]>();
prevStatus.put('B', new char[] { 'E', 'S' });
prevStatus.put('M', new char[] { 'M', 'B' });
prevStatus.put('S', new char[] { 'S', 'E' });
prevStatus.put('E', new char[] { 'B', 'M' });

第三，在start中，定义了初始状态的概率分布（模型中所有概率都是取过对数的，避免下溢）。可以看到E跟M的概率是0，B的概率最大（一个词的开头不能是中间字和结尾字，最可能是开头字）。

start = new HashMap<Character, Double>();
    start.put('B', -0.26268660809250016);
    start.put('E', -3.14e+100);
    start.put('M', -3.14e+100);
    start.put('S', -1.4652633398537678);

第四，在trans中，定义了各状态之间的转移概率，也就是说这是一个转移矩阵。根据HMM的有限历史假设，HMM的状态只跟前1个状态有关，大大简化了模型。可以看到，B只可能向E跟M转移，因为开始词后面跟的只能是中间字或者结尾字（如果跟的是开始字或者单字，则说明这个字不是开始字，自相矛盾）。

trans = new HashMap<Character, Map<Character, Double>>();
    Map<Character, Double> transB = new HashMap<Character, Double>();
    transB.put('E', -0.510825623765990);
    transB.put('M', -0.916290731874155);
    trans.put('B', transB);
    Map<Character, Double> transE = new HashMap<Character, Double>();
    transE.put('B', -0.5897149736854513);
    transE.put('S', -0.8085250474669937);
    trans.put('E', transE);
    Map<Character, Double> transM = new HashMap<Character, Double>();
    transM.put('E', -0.33344856811948514);
    transM.put('M', -1.2603623820268226);
    trans.put('M', transM);
    Map<Character, Double> transS = new HashMap<Character, Double>();
    transS.put('B', -0.7211965654669841);
    transS.put('S', -0.6658631448798212);
    trans.put('S', transS);

第五个Map，emit，即发射概率矩阵。是在某个状态观察到某个观察值（即某个字）的概率。由以下代码得到。其中PROB_EMIT文件存储了几千个字和他们在对应状态时出现的概率。

InputStream is = this.getClass().getResourceAsStream(PROB_EMIT);
    try {
        BufferedReader br = new BufferedReader(new InputStreamReader(is, Charset.forName("UTF-8")));
        emit = new HashMap<>();
        Map<Character, Double> values = null;
        while (br.ready()) {
            String line = br.readLine();
            String[] tokens = line.split("\t");
            if (tokens.length == 1) {
                values = new HashMap<>();
                emit.put(tokens[0].charAt(0), values);
            }
            else {
                values.put(tokens[0].charAt(0), Double.valueOf(tokens[1]));
            }
        }
    }

到此HMM模型建立完毕，下面用维特比算法就可以组词了。

Viterbi维特比算法

这是一种动态规划算法，其实笔者这学期在北邮学习的《通信原理》课程中就有这种算法的介绍，不过只是简单地将其用于卷积码的译码。
结巴分词的算法到了这一步之后，虽然大部分名字动词形容词都已经完成组词，但可能还存在一些连接词等词语没有组成词，以多个连续单字的形式存在，结巴分词构造了一个HMM（Hidden Markov Model）隐马尔科夫模型来解决这个问题，其中用到了Viterbi算法动态规划路径。该算法将整个句子先都转化为BESBESSBE···这样的多条路径，最后从右向左回溯，找到概率最大的一条路径，再根据BEMS来分成词。代码如下：

public void viterbi(String sentence, List<String> tokens) {
    Vector<Map<Character, Double>> v = new Vector<>();
    Map<Character, Node> path = new HashMap<>();

    v.add(new HashMap<>());
    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;
    }
    double probE = v.get(sentence.length() - 1).get('E');
    double probS = v.get(sentence.length() - 1).get('S');
    Vector<Character> posList = new Vector<>(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));
}

看下面的示意图可能会有一个更清晰的理解：这个算法为每一个字都存储四种可能状态及其概率，每一个字根据发射概率矩阵和转移概率矩阵确定自己的上一个状态是什么，这样一直到最后一个字。最后反着从尾到首串起来。因为每一个字都只有唯一的一个前一状态，因此从后往前只有唯一的一条路径（最后一个字的状态还只可能是E或者S）。

结尾

以上是对Java版结巴分词的学习和算法详细解释，希望以后能将这些算法用于文本的模式识别中去。