异想天开

What's the true meaning of light, Could you tell me why

python的jieba库阅读笔记

日期:2017-04-15 23:15:28
  
最后更新日期:2017-04-18 10:08:38
一. 介绍
见附录1
jieba分词主要用到如下算法:
1. 根据词典构造Trie树
2. 用动态规划查找最大概率(基于词频)的的切分组合
3. 利用HMM模型,使用Viterbi算法发现新词

二. jieba分词例子
pip install jieba安装好jieba库后, 根据下面来测试分词:
[code lang="cpp"]
import jieba
str="惟love与科技不可辜负"
seg_list = jieba.cut(str,cut_all=True)
print "Full Mode:", "/ ".join(seg_list) #全模式

seg_list = jieba.cut(str,cut_all=False)
print "Default Mode:", "/ ".join(seg_list) #精确模式

seg_list = jieba.cut(str) #默认是精确模式
print ", ".join(seg_list)

seg_list = jieba.cut_for_search(str) #搜索引擎模式
print ", ".join(seg_list)
[/code]
查看一下效果:
Building prefix dict from /usr/lib/python2.6/site-packages/jieba/dict.txt ...
Loading model from cache /tmp/jieba.cache
Loading model cost 0.303812980652 seconds.
Prefix dict has been built succesfully.
Full Mode: 惟/ love/ 与/ 科技/ 不可/ 辜负
Default Mode: 惟/ love/ 与/ 科技/ 不可/ 辜负
惟, love, 与, 科技, 不可, 辜负
惟, love, 与, 科技, 不可, 辜负


三.解读
找到python的jieba库的安装路径,在我的系统下如下:
vim /usr/lib/python2.6/site-packages/jieba/__init__.py
1. 加载词典
FREQ, total = gen_pfdict(abs_path)
[code lang="cpp"]
def gen_pfdict(f_name):
lfreq = {}
ltotal = 0
with open(f_name, 'rb') as f:
lineno = 0
for line in f.read().rstrip().decode('utf-8').splitlines():
lineno += 1
try:
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 as e:
logger.debug('%s at line %s %s' % (f_name, lineno, line))
raise e
return lfreq, ltotal
[/code]
这里用了with来代替try... catch。将词频存到dict里面。

找到分词的主函数cut的原型:
def cut(sentence, cut_all=False, HMM=True):
该函数会做一些准备工作,会要经过如下步骤
2. 将字符编码转化为unicode
[code lang="cpp"]
def strdecode(sentence):
if not isinstance(sentence, text_type):
try:
sentence = sentence.decode('utf-8')
except UnicodeDecodeError:
sentence = sentence.decode('gbk', 'ignore')
return sentence
[/code]
转化为unicode后,则可以在中英混合字符串中,根据列表索引取值

3. 剔除标点和分隔符号,将整段汉字分为句子。这里主要利用python的正则表达式库re。
[code lang="cpp"]
if cut_all:
re_han = re_han_cut_all
re_skip = re_skip_cut_all
else:
re_han = re_han_default
re_skip = re_skip_default
blocks = re_han.split(sentence)
if cut_all:
cut_block = __cut_all
elif HMM:
cut_block = __cut_DAG
else:
cut_block = __cut_DAG_NO_HMM
[/code]
上面不同的正则表达式,分别表示为:
re_han_default = re.compile("([\u4E00-\u9FA5a-zA-Z0-9+#&\._]+)", re.U)
re_skip_default = re.compile("(\r\n|\s)", re.U)
re_han_cut_all = re.compile("([\u4E00-\u9FA5]+)", re.U)
re_skip_cut_all = re.compile("[^a-zA-Z0-9+#\n]", re.U)
这样后面再调用match和split进行分块

4. 将句子分隔为词
先用get_DAG构造一个有向无环图(有向无环图表示为经过若干节点,无法回到自身),该有向无环图将一个句子的每个字看成是一个节点,根据词典文件,若节点i到节点j可以构成一个词,那么添加一条有向边。
[code lang="cpp"]
def get_DAG(sentence):
global FREQ
DAG = {}
N = len(sentence)
for k in xrange(N):
tmplist = []
i = k
frag = sentence[k]
while i < N and frag in FREQ:
if FREQ[frag]:
tmplist.append(i)
i += 1
frag = sentence[k:i + 1]
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
[/code]
FREQ是加载词典后,用python的dict实现的Trie树。python里面将复杂数据结构作为参数时是引用。xrange不会生成一个长列表,合格的pythoner需要这么写。

计算最大概率的划分,这里用了log概率,好处不言自明,可以将乘积转化为和差。同时若相邻的AB两字,构成一个词,那么P(AB) > P(A) * P(B)。举个例子,比如中国,P(中国) > P(中) * P(国), 说明两字有一定的相关性,否则为不太可能形成词,至少从词频来看。
[code lang="cpp"]
def calc(sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(total)
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])

[/code]

最后的封装函数如下:
[code lang="cpp"]
def __cut_DAG_NO_HMM(sentence):
DAG = get_DAG(sentence)
route = {}
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 = ''
[/code]
代码的意图:
[code lang="cpp"]
if re_eng.match(l_word) and len(l_word) == 1:
buf += l_word
x = y
[/code]
在词典里面是没有英文单词的,那么出现单词,比如“happy”,Trie树构成词其实是一个个英文字母,那么这里将一个个字母串联成一个词。


附录:
1.jieba介绍