1 生成有向无环图（DAG）

算法原理

• 利用了词典信息(dict.txt 第一列), 词典给到了潜在的词语，是基于规则的分词。
• 这张图有T(输入句子的长度)+1个节点， 从起点到终点的任何一条路径，代表一种候选分词方案 。

比如，对于"南京长江大桥", 生成的DAG如下:

工程实现

• 利用​前缀词典​(实际上就是一个​HashMap​，存储所有的词前缀，含词自身) 实现高效的词图扫描，构造DAG

  • 通过判断是否为训练语料中的词前缀（含词自身），否的话可快速终止扫描, 而不用扫描到句尾

  • 通过判断词频是否大于0，若是，则加入对应的边，边的Lable是对应的词

    Note

    具体实现是通过一个​HashMap​实现，其中key为词，value为词频，真前缀通过词频=0标识出来

    def get_dag_by_prefix_dict(self, sentence: str) -> Dict[int, List[int]]:
        """
        节点个数为len(sentence)+1, 边 := 节点i:节点j = sentence[i:j]表示潜在的分词
          
        Args:
          sentence: 待分词的句子
          
        Returns:
          i -> [j1, j2, ...], 其中s[i:j1], s[i:j2], ...组成词
        """
        dag = defaultdict(list)
        n = len(sentence)
          
        for i in range(n):  # 将i, j理解为DAG的节点V，sentence[i:j]表示边edge(i, j)的label
            dag[i].append(i + 1)  # edge(i, i+1) = sentence[i] 单字作为词
            for j in range(i + 2, n + 1):  # edge(i, j)
                candidate_word = sentence[i:j]
                if candidate_word in self.freq:
                    if self.freq[candidate_word] > 0:
                        dag[i].append(j)
                else:           # 提前终止, 候选词不是任何词的前缀
                    break
          
        dag = dict(dag)
        return dag

• 通过Trie(字典树)也可以实现，但实测空间效率没有前缀词典高效

  • jieba的历史版本中，曾经使用Trie，但后来被优化为用前缀词典，主要考虑是空间复杂度

  • python实现的Trie, 多层HashMap嵌套，内存占用空间比PrefixDict大很多，C++实现的话，预计效率会高很多

    	内存占用
    Trie	164.27 MB
    prefix_dict	59.43 MB

2 选取一条最优路径

算法原理

• 利用了词频信息(dict.txt 第二列)，基于 Unigram语言模型 ，预估每条候选路径的最大概率，选概率最大的路径，作为最终的分词方案

• 公式如下：

  \[ bestpath = \arg \max_i \prod_{j} p(w_{i, j}) \]

  其中 \(w_{i, j}\) 表示第i条路径中第j条边对应的词

对于上面例子，虽然输入句子长度大小只有7, 但理论上有2^7-1=64条路径, 由于某些组合不能构成词，最终有24条候选路径，也很大。(后面会用动态规划寻找最优路径，而不是遍历所有的路径。)

工程实现

• 利用​动态规划​寻找最优的路径，比暴力搜索所有路径，要高效很多

  • 定义状态dp[i]: 第i个节点开始路径的最大分数(从sentence[i:]开始到句尾)

  • 状态转移方程:

    \[ dp[i] = \max_{j} \big( score(sentence[i:j]) + dp[j]\big) = \max_{j} \big( \log \frac{freq[sentence[i:j]] }{n_{total-word}} + dp[j]\big) \]

​必须用归一化的词频​，否则会导致结果错误：

• 之前的理论公式是基于概率的

• 表面上看，分母似乎是常数项，去掉对结果没影响，但其实不是，因为有累计效应，切分后不同的词长度，分母生效的次数不一样。比如对于词频<中（1） 国（1） 中国（1）>,

  • 以未归一化词频计算：

    • score(中 国) = 1 * 1
    • score(中国) = 1

  • 以归一化词频计算：

    • score(中 国) = 1/3 * 1/3 = 1/9
    • score(中国) = 1/3

def find_optimal_path_dp(self, sentence, dag) -> Tuple[float, List[int]]:
    """
    寻找最大概率路径
    """
    n = len(sentence)
    # 图论:    从节点i到节点n的最大分数(log p), 最大分数对应的i+1个节点(下一步位置)
    # 物理意义: 以sentence[i]为始点，到句尾的最大分数; 最有路径中，以sentence[i]开始的词结束位置
      
    # dp[i] = \max_{k} score(i, k) + dp[k]
    dp = [(None, None) for i in range(n + 1)]
    dp[n] = 0, None
    for i in range(n - 1, -1, -1):
        tmp = []
        for j in dag[i]:
            candidate_word = sentence[i:j]
            tmp.append(
                (np.log(self.freq.get(candidate_word, 1)) - np.log(self.n_word) + dp[j][0], j)
            )
        dp[i] = max(tmp)
      
    path = [0]
    i = 0
    while i < n:
        next_i = dp[i][1]
        path.append(next_i)
        i = next_i
    return dp[0], path

3 对于未登录词，用HMM模型分词

​算法原理​

HMM假设自己是上帝, 认为句子的生成过程是这样子的:

• 抛一个4面的骰子，决定第一个字的隐状态(BMES中的某一个, B词开始位置, M词中间位置, E词结束位置, S单字词), 这个骰子通过​初始概率​矩阵来表示。
• 有4个V面的骰子, 对应四个状态，在已知某隐状态的情况下，抛对应的骰子，决定产生的下一个字什么。这4个骰子对应的是​发射概率​矩阵。
• 另外还有4个4面的筛子, 这个筛子用来决定隐状态中间如何转换，对应的是​转移概率​矩阵。

Note

​工程实现​

虽然每个隐状态序列的概率很容易计算，但架不住隐状态序列可能性太多了(\(4^T\), T为句子长度)，此时通过动态规划（或者在状态转移中的一个特殊名词，维特比译码算法）来求解，可以将复杂度降低到 \(4^2*T\) 。

• 状态定义：\(score_{t, s}\) 时刻t到达状态s的最优路径得分

• 状态转移方程：

  \[ score_{t,s} = \mathop{\max}\limits_{s'} score_{t-1, s'} + p_{t-1, s'}^{trans} + p^{emit}_{s, sentence[t]} \]

  def viterbi(sentence, states, p_start, p_trans, p_emit):
      """
      维特比译码: 根据显状态序列sentence和HMM(p_start, p_trans, p_emit), 利用动态规划算法找出最优路径
      
      Args:
        sentence: 观察到的显状态序列
        states: 隐状态值集合
        p_start: 初始概率矩阵
        p_trans: 转移概率矩阵
        p_emit: 发射概率矩阵
      
      Returns:
        (best_score, best_path)
      
      """
      T = len(sentence)
      score = [{} for _ in range(T)]  # score[t][s] ~ 时刻t到达状态s的最优路径得分
      bp = [{} for _ in range(T)]     # bp[t][s] ~ 时刻t状态s最优路径的上一状态
      
      t = 0                   # 起点
      for s in states:
          score[t][s], bp[t][s] = p_start[s] + p_emit[s].get(sentence[t], MIN_FLOAT), None
      
      for t in range(1, T):   # 递归
          for s in states:
              score[t][s], bp[t][s] = max((score[t - 1][s_prev] + p_trans[s_prev][s] + p_emit[s].get(sentence[t], MIN_FLOAT), s_prev)
                                          for s_prev in states if s in p_trans[s_prev])
      
      t = T                   # 终点
      best_score, best_bp = max((score[t - 1][s], s) for s in "ES")  # 最后一个词的隐状态只能为E或S
      
      # 根据backpoint恢复最优路径
      best_path = [best_bp]
      pointer = best_bp
      for t in range(T - 1, 0, -1):
          prev = bp[t][pointer]
          best_path.append(prev)
          pointer = prev
      best_path = best_path[::-1]
      return best_score, best_path

4 总结

整个流程近似伪代码如下：

def problem_chinese_tokenize(sentence:str, word2freq:Dict[str, int]) -> str:  
    dag = get_dag(sentence, word2freq) # 构造DAG 
    best_path = find_optimal_path(sentence, dag) # 寻找最优路径
    best_path = adjust_by_hmm(best_path)         # HMM调整

    result = " ".join(edge["label"] for edege in best_path)
    return result

核心点：

• ​DAG有向无环图表示所有可能的分词路径​

• ​*动态规划 ：无论是DAG中寻找最优路径，还是HMM中解码，都依赖于动态规划

  • 本质上是很多路径中的计算过程可以复用，通过动态规划，将这些可以复用的状态记录下来，下次直接用

当然，最新版本的jieba还支持百度LAC算法（基于深度学习的序列标注模型）。

5 更新日志

• 2020-12-06 增加寻找最大路径时，对归一化频率的的说明（n_{total_word}），这一项不是常数，必须加上，否则会导致结果错误。