首页 > 代码库 > jieba分词源码阅读

jieba分词源码阅读

2024-08-13 08:18:29   220人阅读

jieba是一个开源的中文分词库，这几天看了下源码，就做下记录。

下载jieba后，tree得到主要部分的目录树结构如下：

├── jieba
    │   ├── analyse
    │   │   ├── analyzer.py
    │   │   ├── idf.txt
    │   │   ├── __init__.py
    │   │   ├── textrank.py
    │   │   └── tfidf.py
    │   ├── _compat.py
    │   ├── dict.txt
    │   ├── finalseg
    │   │   ├── __init__.py
    │   │   ├── prob_emit.p
    │   │   ├── prob_emit.py
    │   │   ├── prob_start.p
    │   │   ├── prob_start.py
    │   │   ├── prob_trans.p
    │   │   └── prob_trans.py
    │   ├── __init__.py
    │   ├── __main__.py
    │   └── posseg
    │       ├── char_state_tab.p
    │       ├── char_state_tab.py
    │       ├── __init__.py
    │       ├── prob_emit.p
    │       ├── prob_emit.py
    │       ├── prob_start.p
    │       ├── prob_start.py
    │       ├── prob_trans.p
    │       ├── prob_trans.py
    │       └── viterbi.py
    ├── LICENSE
    ├── MANIFEST.in
    ├── README.md
    ├── setup.py
    └── test

analyse目录下是几个提取文本关键词的算法实现。

dict.txt是总的词库，每行记录了一个词和这个词的词频及词性。

__init__.py是jieba的主要入口

finalseg是如果使用hmm，那么在初步分词之后还要调用这里的代码，主要是对hmm的实现。

然后介绍下主要接口__init__.py中的几个函数：

def gen_pfdict(self, f):
    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
        except ValueError:
            raise ValueError(
                'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    f.close()
    return lfreq, ltotal

gen_pfdict加载dict.txt生成字典树，lfreq存储dict.txt每个词出现了多少次，以及每个词的所有前缀，前缀的频数置为0，ltotal是所有词出现的总次数。得到的字典树存在self.FREQ中。例如对于词"不拘一格"，在字典树lfreq中是这样的{"不" : 0, "不拘" : ,"不拘一" , 0, "不拘一格" : freq} 其中的freq就是在dict.txt中记录的词频。


def get_DAG(self, sentence):
    self.check_initialized()
    DAG = {}
    N = len(sentence)
    for k in xrange(N):
        tmplist = []
        i = k
        frag = sentence[k]
        while i < N and frag in self.FREQ:
            if self.FREQ[frag]:
                tmplist.append(i)
            i += 1
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist
    return DAG

FREQ是根据dict.txt生成的字典树，get_DAG函数是根据FREQ对于每个句子sentence生成一个有向无环图，图信息存在字典DAG中，其中DAG[pos]是一个列表[a, b, c...]，pos从0到len(sentence) - 1，表示sentence[pos : a + 1],sentence[pos, b + 1]...这些单词出现在了dict中。

例如以“但也并不是那么出乎意料或难以置信”这句话作为输入，生成的DAG如下，简单的讲就是把句子中词的位置标记出来

0 [0] 但
1 [1] 也
2 [2] 并
3 [3, 4] 不是
4 [4] 是
5 [5, 6] 那么
6 [6] 么
7 [7, 8, 10] 出乎意料
8 [8] 乎
9 [9, 10] 意料
10 [10] 料
11 [11] 或
12 [12, 13, 15] 难以置信
13 [13] 以
14 [14, 15] 置信
15 [15] 信


接下来就是对句子的切分，即jieba.cut。具体的分词流程概括起来如下: 
1. 给定待分词的句子, 使用正则(re_han)获取匹配的中文字符(和英文字符)切分成的短语列表； 
2. 利用get_DAG(sentence)函数获得待切分句子的DAG，首先检测(check_initialized)进程是否已经加载词库，若未初始化词库则调用initialize函数进行初始化，initialize中判断有无已经缓存的前缀词典cache_file文件，若有相应的cache文件则直接使用 marshal.load 方法加载前缀词典，若无则通过gen_pfdict对指定的词库dict.txt进行计算生成前缀词典，到jieba进程的初始化工作完成后就调用get_DAG获得句子的DAG； 
3. 根据cut_block指定具体的方法(__cut_all,__cut_DAG,__cut_DAG_NO_HMM)对每个短语使用DAG进行分词 ，如cut_block=__cut_DAG时则使用DAG(查字典)和动态规划, 得到最大概率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词； 
4. 使用python的yield 语法生成一个词语生成器, 逐词语返回；


def __cut_all(self, sentence):
    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:
            for j in L:
                if j > k:
                    yield sentence[k:j + 1]
                    old_j = j
__cut_all是全模式切分，其实就是把DAG中的所有组合显示出来。对于上个句子得到的结果如下：但/也/并/不是/那么/出乎/出乎意料/意料/或/难以/难以置信/置信


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])
calc函数根据出现的概率来计算最可能的切词结果，其中单词A的概率为A的出现次数除以所有单词出现的总次数。通过dp计算最大概率的切词方式，route[i][0]表示sentence[i : len]的最大概率，route[i][1]表示sentence[i : len]这个子串的第一个切分位置在哪。


def __cut_DAG_NO_HMM(self, sentence):
        DAG = self.get_DAG(sentence)
        route = {}
        self.calc(sentence, DAG, route)
        x = 0
        N = len(sentence)
        buf = ''
        while x < N:
            y = route[x][1] + 1
            l_word = sentence[x:y]
            if re_eng.match(l_word) and len(l_word) == 1:
                buf += l_word
                x = y
            else:
                if buf:
                    yield buf
                    buf = ''
                yield l_word
                x = y
        if buf:
            yield buf
            buf = ''

__cut_DAG_NO_HMM是不使用hmm的精确模式，首先调用calc，得到的route[i][1]中保存的是切分的位置信息，然后遍历输出切分方式。

def __cut_DAG(self, sentence):
    DAG = self.get_DAG(sentence)
    route = {}
    self.calc(sentence, DAG, route)
    x = 0
    buf = ''
    N = len(sentence)
    while x < N:
        y = route[x][1] + 1
        l_word = sentence[x:y]
        if y - x == 1:
            buf += l_word
        else:
            if buf:
                if len(buf) == 1:
                    yield buf
                    buf = ''
                else:
                    if not self.FREQ.get(buf):
                        recognized = finalseg.cut(buf)
                        for t in recognized:
                            yield t
                    else:
                        for elem in buf:
                            yield elem
                    buf = ''
            yield l_word
        x = y

    if buf:
        if len(buf) == 1:
            yield buf
        elif not self.FREQ.get(buf):
            recognized = finalseg.cut(buf)
            for t in recognized:
                yield t
        else:
            for elem in buf:
                yield elem

__cut_DAG同时使用最大概率路径和hmm，对于利用动态规划计算出的最大概率切分后，用buf将连续的单字收集以及未登录词收集起来，再调用finalseg.cut利用hmm进行分词。


然后是final_seg的__init__.py

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]  # tabular
    path = {}
    for y in states:  # init
        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
        path[y] = [y]
    for t in xrange(1, len(obs)):
        V.append({})
        newpath = {}
        for y in states:
            em_p = emit_p[y].get(obs[t], MIN_FLOAT)
            (prob, state) = max(
                [(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
            V[t][y] = prob
            newpath[y] = path[state] + [y]
        path = newpath

    (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')

    return (prob, path[state])
HMM中的viterbi算法的实现函数，是viterbi算法给定了模型参数和观察序列之后求隐藏状态序列，其中对于分词，观察序列就是句子本身，而隐藏序列就是一个由{B, M, E, S}组成的序列，B表示词的开始，M表示词的中间，E表示词的结尾，S表示单字成词。
函数的输入参数中obs是输入的观察序列，即句子本身，states表示隐藏状态的集合，即{B, M, E, S}，start_p表示第一个字分别处于{B, M, E, S}这几个隐藏状态的概率，trans_p是状态转移矩阵，记录了隐藏状态之间的转化概率，例如trans_p[‘B’][‘E’]代表的含义就是从状态B转移到状态E的概率，emit_p是发射概率矩阵，表示从一个隐藏状态转移到一个观察状态的概率，例如P[‘B’][‘\u4e00’]代表的含义就是’B’状态下观测的字为’\u4e00’(对应的汉字为’一’)的概率大小。
V是一个列表，V[i][j]表示对于子观察序列obs[0 ~ i]，在第i个位置时隐藏状态为j的最大概率，其实就是个简单dp。
path是记录了状态转移的路径。

def __cut(sentence):
    global emit_P
    prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
    begin, nexti = 0, 0
    # print pos_list, sentence
    for i, char in enumerate(sentence):
        pos = pos_list[i]
        if pos == 'B':
            begin = i
        elif pos == 'E':
            yield sentence[begin:i + 1]
            nexti = i + 1
        elif pos == 'S':
            yield char
            nexti = i + 1
    if nexti < len(sentence):
        yield sentence[nexti:]
通过调用viterbi算法得到概率和path之后，对sentence进行分词。


参考：

http://www.cnblogs.com/lrysjtu/p/4529325.html

http://blog.csdn.net/daniel_ustc/article/details/48195287

jieba分词源码阅读


联系
我们