jieba 分词原理

jieba 分词主要包含以下步骤：

• 根据 dict.txt 词典生成 Trie 树，对待分词的句子，依据 Trie 树生成 DAG（有向无环图）
• 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
• 对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法

Jieba 分词结合了基于规则和基于统计两种方法。

• 首先基于前缀词典进行词图扫描。因此，基于前缀词典可以快速构建包含全部可能分词结果的有向无环图，这个图中包含多条分词路径。
• 基于标注语料，使用动态规划的方法可以找出最大概率路径，并将其作为最终的分词结果。
• 对于未登录词，Jieba 是用了基于汉字成词的 HMM 模型，采用 Viterbi 算法进行推导。

Trie 树结构：