分词总结

本文主要是自己在阅读jieba源码的理解做一下分词算法的总结，分为工程和算法两部分进行。

算法

现在的中文分词以规则+统计为主要实现方式。所以大致分为：1、词典的存储方式。2、query表达。3、译码。4、对于单字序列用HMM发现新词。

• 词典的存储方式

1. trier树

lfreq = {}  
    trie = {}  
    ltotal = 0.0  
    with open(f_name, 'rb') as f:  
        lineno = 0   
        for line in f.read().rstrip().decode('utf-8').split('\n'):  
            lineno += 1  
            print "lineno: ", lineno
            print len(trie)
            try:  
                word,freq,_ = line.split(' ')  
                freq = float(freq)  
                lfreq[word] = freq  
                ltotal+=freq  
                p = trie  
                for c in word:  
                    if c not in p:  
                        p[c] ={}  
                    p = p[c]  
                p['']='' #ending flag  

2. 前缀数组

lfreq = {}
        ltotal = 0
        f_name = resolve_filename(f)
        for lineno, line in enumerate(f, 1):
            try:
                line = line.strip().decode('utf-8')
                word, freq = line.split(' ')[:2]
                freq = int(freq)
                lfreq[word] = freq
                ltotal += freq
                for ch in xrange(len(word)):
                    wfrag = word[:ch + 1]
                    if wfrag not in lfreq:
                        lfreq[wfrag] = 0

翻看结巴的发布历史，发现最开始用的trier树的方式，现在采用的是前缀数组的方式进行存储。这儿加一段自己的理解，为什么后来用前缀数组来表示，因为字典树的优势在于其查找的速度上，其复杂度为o（n）（n为query的长度，和树的深度没有关系）。但是python的dict是散列表实现其查找复杂度为O(1),trier树的优势不再存在，但是c++等语言中字典是红黑树实现的，其优势还是比较明显。而前缀数组相较于tier树不用保存单词间的依赖关系，因为其速度和所占用的内存上回更有优势。

• query表达

一般是将输入query转换成有向无环图

这一步的主要作用是将query根据第一步加载的词典生成有向无环图，有向无环图大概长这样：

DAG
0 [0]
1 [1]
2 [2, 4]
3 [3, 4]
4 [4]
5 [5]
6 [6]
7 [7]
8 [8]

即表示的是每一个输入query的token序列的所有成词的方式，后面的译码算法会根据这个图进行译码。常见的译码算法包括最大正向匹配算法，最大概率译码方式。jieba采用的最大概率译码。注意在表示

• 译码

根据query的有向无环图，这儿介绍最大概率译码和最大正向匹配译码

最大正向匹配算法

 dag = self.get_DAG(sentence)
        old_j = -1
        for k, L in iteritems(dag):
            if len(L) == 1 and k > old_j:
                yield sentence[k:L[0] + 1]
                old_j = L[0]
            else:
                if len(L) > 1 and  k > old_j:
                    yield sentence[k:L[-1] + 1]
                    old_j = L[-1]

最大概率

def calc(self, sentence, DAG, route):
        N = len(sentence)
        route[N] = (0, 0)
        logtotal = log(self.total)
        for idx in xrange(N - 1, -1, -1):
            route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                              logtotal + route[x + 1][0], x) for x in DAG[idx])

• HMM发现新词

对于译码出的单字序列使用HMM发现新词。HMM的原理和代码详见我的github：
HMM介绍及code实现