jieba分词

分词介绍

所谓分词就是将构成一个完整句子的所有词语分割开。对于中文来说，单个的字并不是组成句子含义的最小单元，对于理解句子含义来说，最小单元是词语，因此将一个完整的句子分解成为词语是理解句子含义的首要步骤。值得注意的是，相比于英文来说，分词是中文特有的步骤，因为英文每个词语之间已经有天然的空格作为词与词之间的间隔，无需再次对于词语划分，但中文的词语之间并没有明显的分隔，这对我们的翻译、信息检索、关键词提取等文本处理带来不小的麻烦。因此，对于中文做文本处理，首要的工作是词语的划分，也就是分词。

jieba分词

jieba分词是比较流行的中文分词开源库，可以实现中文分词，涉及到的主要算法有以下几种：

• 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
• 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
• 对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法

结巴分词的主要步骤为：

1. 根据统计词典构建词的前缀词典
2. 根据前缀词典，对句子进行正向匹配，构建有向无环图
3. 使用动态规划的方法，在有向无环图上寻找概率最大的分词形式

jieba分词原理详解

下面结合具体例子介绍分词的原理，以“我在学习结巴分词”为例：

1、构建前缀词典

jieba为用户提供了三个词典，dict.text.big和dict.text.small以及默认字典dict.txt，big的词汇量584429，small的词汇量109750，dict的词汇量349046
jieba读取词典中的每一个词语，为每一个词语构建前缀词表。如“结巴分词”构建的词表为：“结”“结巴”“结巴分”“结巴分词”。对于存在于词典中的词语，词频为词典中词语的词频，对于未登录的词语（词典中没有收录的词语），词频设置为0。
构建前缀词典的目的是为了后边计算每一条路径的概率时使用。

def pre_dict(path):
    """
    构建前缀词典
    :param path: 词典路径
    :return: word_dcit词典和total总的词频
    """
    word_dict = dict()
    # 统计词频
    total = 0
    file_obj = open(path, 'rb')
    for lineno, line in enumerate(file_obj, 1):
        line = line.strip().decode('utf-8')
        word, freq, _ = line.split()  # 获取词汇和词频
        word_dict[word] = int(freq)
        total += int(freq)
        n = len(word)
        # 构建每个词前缀词，未登录词词频设置为0
        for ch in range(n):
            pre_word = word[:ch + 1]
            if pre_word not in word_dict:
                word_dict[pre_word] = 0  # 未登录词词频为0
    return word_dict, total
if __name__ == '__main__':
    path = './dict.txt'
    word_dict, total = pre_dict(path)
    print(word_dict)
    print(total)

2、构建有向无环图

代码：

def get_dag(text, word_dict):
    """
    有向无环图
    :param text: 语料
    :param word_dict: 前缀词典
    :return: 有向无环图的字典
    """
    dag_dict = dict()
    n = len(text)
    # 遍历文本的每个字
    for i in range(n):
        # 每个字可能构成词典中存在后缀词的下表列表
        temp_list = list()
        word = text[i]
        k = i
        # 构成每个字的后缀词
        # 判断词是否存在词典中
        while k < n and word in word_dict:
            # 判断该词词频大于0，加入列表中
            if word_dict[word]:
                temp_list.append(k)
            k += 1
            # 下一个词
            word = text[i:k + 1]
        # 如果temp_list列表为空，则后缀词不存在
        if not temp_list:
            temp_list.append(i)
        # 添加所有可能成词的索引到字典
        dag_dict[i] = temp_list
    return dag_dict
if __name__ == '__main__':
    path = './dict.txt'
    word_dict, total = pre_dict(path)
    text = '我在学习结巴分词'
    dag_dict = get_dag(text, word_dict)
    print(dag_dict)

jieba对于每个字进行正向匹配，得到所有可能的有向无环图，在python中，有向无环图是通过字典的形式实现的。例如上面的例子，输出为：{0: [0], 1: [1], 2: [2, 3], 3: [3], 4: [4, 5, 7], 5: [5], 6: [6, 7], 7: [7]}
其中key为构成词语的初始（第一个字）的位置，value为词语到达的最后的位置。

3、动态规划最大概率路径

如上面所说的例子，构建有向无环图，此时有如下10种分词方式：

• 我/在/学/习/结/巴/分/词
• 我/在/学习/结/巴/分/词
• 我/在/学习/结巴/分/词
• 我/在/学习/结巴/分词
• 我/在/学/习/结巴/分/词
• 我/在/学/习/结巴分词
• 我/在/学习/结巴分词
• 我/在/学习/结/巴/分词
• 我/在/学/习/结/巴/分词
• 我/在/学/习/结巴/分词

jieba通过动态规划，找到其中最大的一种可能性，并输出结果。这里用到了从后向前的动态规划的解法，并用对数概率计算，这样可以防止数据下溢（因为对于巨大的语料库来说，单个的词语出现的频率是比较低的，会出现很小的浮点数，容易造成数据下溢），并且将乘法操作转化为加法操作。如下的例子“结巴分词”，（并不是真实的数据）用到的公式为 score(char) = log(freq(char)) - log(total) + score(char+1)

词语      出现的对数概率
“词”      -1
“分”      -0.2
“分词”    -0.1
“巴”      -1
“结”      -0.2
“结巴”    -0.1
“结巴分词” -0.01

score（词） = -1；
score（分） = -0.2 + score（词） = -1.2；score（分词）= -0.1 所以选择分词方式为“分词”而不是“分/词”
score（巴） = -1 ；此处划分为“巴/分词”
score（结） = -0.2+score（巴）= -1.2；score（结巴）= -0.1 ； score（结巴分词）= -0.01 选择最大概率“结巴分词”