- 代码(jieba-master)
- 结构
jieba/
analyse/
finalseg/
__init__.py
cut() 提供DAG的cut操作实现
posseg
Viterbi.py
- 新词发现
- HMM模型的Viterbi算法
__init__.py
- 基本所有逻辑都在这里实现
- 解析算法
- trie：基础
- DAG：用于词图扫描
dict.txt
- trie的基础字典，作者收集大量语料分析得到
- 运行方式
- jieba/__init__.py
* 通过trie和DAG提供长度>2的分词效果
* 通过Viterbi提供对新词的二分词
====================================================
结巴中的trie实现是字典，见代码
def gen_trie(f_name): lfreq = {} trie = {} ltotal = 0.0 content = open(f_name,'rb').read().decode('utf-8') for line in content.split("\n"): word,freq,_ = line.split(" ") freq = float(freq) lfreq[word] = freq ltotal+=freq p = trie for c in word: if not c in p: p[c] ={} p = p[c] p['']='' #ending flag return trie, lfreq,ltotal
其中：
trie是一个根据dict.txt生成的前缀树(dict.txt是中文字典，自然生成的trie树也是中文前缀)，末端的叶子以空字符串做标记
注：将dict.txt取几行出来，执行一次gen_trie()就得到形象的结果
lfreq对应trie树，记录整个词的频率评分
ltotal所有频率评分总和
trie树以空间换时间，通过存储字符串的公共前缀来减少查询开销
因此
1.插入、查询都为O(N)
2.内存消耗大26^n
3.对公共前缀重合度小的输入集，trie的效率显得不那么高
优化
1.通过Double Array实现，能大量减少内存使用
====================================================
__init__.py 中的cut()，结巴分词的入口
根据入参选择 trie 或 DAG(默认)
分词过程中都用了 yield 生成器