本文主要是自己在閱讀jieba源碼的理解做一下分詞算法的總結(jié)，分為工程和算法兩部分進(jìn)行。
算法
現(xiàn)在的中文分詞以規(guī)則+統(tǒng)計(jì)為主要實(shí)現(xiàn)方式。所以大致分為：1、詞典的存儲(chǔ)方式。2、query表達(dá)。3、譯碼。4、對(duì)于單字序列用HMM發(fā)現(xiàn)新詞。
- 詞典的存儲(chǔ)方式
- trier樹
lfreq = {}
trie = {}
ltotal = 0.0
with open(f_name, 'rb') as f:
lineno = 0
for line in f.read().rstrip().decode('utf-8').split('\n'):
lineno += 1
print "lineno: ", lineno
print len(trie)
try:
word,freq,_ = line.split(' ')
freq = float(freq)
lfreq[word] = freq
ltotal+=freq
p = trie
for c in word:
if c not in p:
p[c] ={}
p = p[c]
p['']='' #ending flag
- 前綴數(shù)組
lfreq = {}
ltotal = 0
f_name = resolve_filename(f)
for lineno, line in enumerate(f, 1):
try:
line = line.strip().decode('utf-8')
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
翻看結(jié)巴的發(fā)布?xì)v史，發(fā)現(xiàn)最開始用的trier樹的方式，現(xiàn)在采用的是前綴數(shù)組的方式進(jìn)行存儲(chǔ)。這兒加一段自己的理解，為什么后來(lái)用前綴數(shù)組來(lái)表示，因?yàn)樽值錁涞膬?yōu)勢(shì)在于其查找的速度上，其復(fù)雜度為o（n）（n為query的長(zhǎng)度，和樹的深度沒(méi)有關(guān)系）。但是python的dict是散列表實(shí)現(xiàn)其查找復(fù)雜度為O(1),trier樹的優(yōu)勢(shì)不再存在，但是c++等語(yǔ)言中字典是紅黑樹實(shí)現(xiàn)的，其優(yōu)勢(shì)還是比較明顯。而前綴數(shù)組相較于tier樹不用保存單詞間的依賴關(guān)系，因?yàn)槠渌俣群退加玫膬?nèi)存上回更有優(yōu)勢(shì)。
- query表達(dá)
一般是將輸入query轉(zhuǎn)換成有向無(wú)環(huán)圖
這一步的主要作用是將query根據(jù)第一步加載的詞典生成有向無(wú)環(huán)圖，有向無(wú)環(huán)圖大概長(zhǎng)這樣：
DAG
0 [0]
1 [1]
2 [2, 4]
3 [3, 4]
4 [4]
5 [5]
6 [6]
7 [7]
8 [8]
即表示的是每一個(gè)輸入query的token序列的所有成詞的方式，后面的譯碼算法會(huì)根據(jù)這個(gè)圖進(jìn)行譯碼。常見的譯碼算法包括最大正向匹配算法，最大概率譯碼方式。jieba采用的最大概率譯碼。注意在表示
- 譯碼
根據(jù)query的有向無(wú)環(huán)圖，這兒介紹最大概率譯碼和最大正向匹配譯碼
最大正向匹配算法
dag = self.get_DAG(sentence)
old_j = -1
for k, L in iteritems(dag):
if len(L) == 1 and k > old_j:
yield sentence[k:L[0] + 1]
old_j = L[0]
else:
if len(L) > 1 and k > old_j:
yield sentence[k:L[-1] + 1]
old_j = L[-1]
最大概率
def calc(self, sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(self.total)
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])
- HMM發(fā)現(xiàn)新詞
對(duì)于譯碼出的單字序列使用HMM發(fā)現(xiàn)新詞。HMM的原理和代碼詳見我的github：
HMM介紹及code實(shí)現(xiàn)
