今天是周日，天氣很潮濕，回南天的廣州，即使天氣再惡劣，也不能阻止學(xué)習(xí)的我。。。
每一個(gè)入門自然語(yǔ)言的的人在學(xué)習(xí)的第一步都是從分詞開(kāi)始的，就類似編程的"Hello World"。以下是用兩種方法實(shí)現(xiàn)分詞，分別是基于枚舉法和維特比算法。
一、基于枚舉方法來(lái)搭建中文分詞工具
最簡(jiǎn)單的分詞是不依賴語(yǔ)句關(guān)系的，每一個(gè)詞都是獨(dú)立的，叫unigram
語(yǔ)言模型有unigram->bi-gram->n-gram 從簡(jiǎn)單到難，n表示依賴n級(jí)
此項(xiàng)目所需數(shù)據(jù)：
- 中文詞庫(kù)詞庫(kù)，當(dāng)作字典來(lái)用
- 以變量的方式提供了部分unigram概率 word_prob，也可以用詞庫(kù)的計(jì)算詞頻。
- 舉個(gè)例子： 給定詞典=[我們 學(xué)習(xí) 人工 智能 人工智能 未來(lái) 是]， 另外我們給定unigram概率：p(我們)=0.25, p(學(xué)習(xí))=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未來(lái))=0.1, p(是)=0.15
Step 1: 對(duì)于給定字符串：”我們學(xué)習(xí)人工智能，人工智能是未來(lái)“, 找出所有可能的分割方式
- [我們，學(xué)習(xí)，人工智能，人工智能，是，未來(lái)]
- [我們，學(xué)習(xí)，人工，智能，人工智能，是，未來(lái)]
- [我們，學(xué)習(xí)，人工，智能，人工，智能，是，未來(lái)]
- [我們，學(xué)習(xí)，人工智能，人工，智能，是，未來(lái)] .......
Step 2: 我們也可以計(jì)算出每一個(gè)切分之后句子的概率
- p(我們，學(xué)習(xí)，人工智能，人工智能，是，未來(lái))= -log p(我們)-log p(學(xué)習(xí))-log p(人工智能)-log p(人工智能)-log p(是)-log p(未來(lái))
- p(我們，學(xué)習(xí)，人工，智能，人工智能，是，未來(lái))=-log p(我們)-log p(學(xué)習(xí))-log p(人工)-log p(智能)-log p(人工智能)-log p(是)-log p(未來(lái))
- p(我們，學(xué)習(xí)，人工，智能，人工，智能，是，未來(lái))=-log p(我們)-log p(學(xué)習(xí))-log p(人工)-log p(智能)-log p(人工)-log p(智能)-log p(是)-log p(未來(lái))
- p(我們，學(xué)習(xí)，人工智能，人工，智能，是，未來(lái))=-log p(我們)-log p(學(xué)習(xí))-log p(人工智能)-log p(人工)-log p(智能)-log(是)-log p(未來(lái)) .....
Step 3: 返回第二步中概率最大的結(jié)果,就是-log和最小的。
TODO: 第一步： 從dict.xlsx中讀取所有中文詞。
import xlrd
import math
excel_data = xlrd.open_workbook('./data/dict.xlsx')
sheet_name = excel_data.sheet_by_index(0)
col_data = sheet_name.col_values(0)
dic_words = col_data # 保存詞典庫(kù)中讀取的單詞
以下是計(jì)算的時(shí)候出現(xiàn)用得到的詞頻，分出來(lái)的詞計(jì)算時(shí)，符合下面的就用下面的詞頻，否則就統(tǒng)一設(shè)置成0.00001
由于很多詞都是0.00001，計(jì)算出來(lái)太多小數(shù)點(diǎn)，所以進(jìn)行l(wèi)og取值，好看一點(diǎn)。
word_prob = {"北京":0.03,"的":0.08,"天":0.005,"氣":0.005,"天氣":0.06,"真":0.04,"好":0.05,"真好":0.04,"啊":0.01,"真好啊":0.02,
"今":0.01,"今天":0.07,"課程":0.06,"內(nèi)容":0.06,"有":0.05,"很":0.03,"很有":0.04,"意思":0.06,"有意思":0.005,"課":0.01,
"程":0.005,"經(jīng)常":0.08,"意見(jiàn)":0.08,"意":0.01,"見(jiàn)":0.005,"有意見(jiàn)":0.02,"分歧":0.04,"分":0.02, "歧":0.005}
#因?yàn)橛?jì)算出來(lái)都是負(fù)數(shù)，所以加個(gè)-負(fù)號(hào)得正，todo 計(jì)算-log(x)
for word in word_prob.keys():
word_prob[word] = round(-math.log(word_prob[word]),1)
print(word_prob.values())
下面獲取輸入的句子，得到所有的分詞，主要用到的辦法是遞歸法：
def word_break(input_str,dic_words):
def sentences(cur):
result = []
if cur<len(input_str):
for next in range(cur+1,len(input_str)+1):
if(input_str[cur:next] in dic_words):
result = result+[input_str[cur:next]+(tail and ','+tail) for tail in sentences(next)]
else:
return ['']
return result
word_seg = []
for line in sentences(0):
line = line.split(',')
word_seg.append(line)
return word_seg
- 對(duì)于輸入字符串做分詞，并返回所有可行的分詞之后的結(jié)果。
- 針對(duì)于每一個(gè)返回結(jié)果，計(jì)算句子的概率
- 返回概率最高的最作為最后結(jié)果
def word_segment_naive(input_str):
"""
1. 對(duì)于輸入字符串做分詞，并返回所有可行的分詞之后的結(jié)果。
2. 針對(duì)于每一個(gè)返回結(jié)果，計(jì)算句子的概率
3. 返回概率最高的最作為最后結(jié)果
input_str: 輸入字符串 輸入格式：“今天天氣好”
best_segment: 最好的分詞結(jié)果 輸出格式：["今天"，"天氣"，"好"]
"""
TODO： 第一步： 計(jì)算所有可能的分詞結(jié)果，要保證每個(gè)分完的詞存在于詞典里，這個(gè)結(jié)果有可能會(huì)非常多。
segments = word_break(input_str,dic_words) # 存儲(chǔ)所有分詞的結(jié)果。如果次字符串不可能被完全切分，則返回空列表(list)
格式為：segments = [["今天"，“天氣”，“好”],["天"，“天“，”氣”，“好”],["今“，”天"，“天氣”，“好”],...]
TODO: 第二步：循環(huán)所有的分詞結(jié)果，并計(jì)算出概率最高的分詞結(jié)果，并返回
best_segment = []
best_score = math.inf #無(wú)限大
for seg in segments:
score = 0
# TODO ...
for word in seg:
if word in word_prob.keys():
score+=word_prob[word]
else:
score+=round(-math.log(0.00001),1)
#每次都判斷score的值，得到最小的即是概率最大的
if score < best_score:
best_score=score
best_segment = seg
return best_segment
測(cè)試結(jié)果
print (word_segment_naive("你經(jīng)常做主"))
print (word_segment_naive("今天的課程內(nèi)容很有意思"))
print (word_segment_naive("經(jīng)常有意見(jiàn)分歧"))
最佳分詞結(jié)果如下圖所示：
總結(jié)：枚舉法分詞不但時(shí)間復(fù)雜度高，空間復(fù)雜度也是很高，如果數(shù)據(jù)量很大的情況下，是非常不樂(lè)觀的一個(gè)實(shí)現(xiàn)方法，是否有比這個(gè)更好的方法呢？當(dāng)然有，算法如此強(qiáng)大，只要有發(fā)現(xiàn)。那么接下來(lái)看看維特比算法（vitebi）實(shí)現(xiàn)分詞工具。
二、基于維特比算法來(lái)優(yōu)化上述流程
維特比算法用的是動(dòng)態(tài)規(guī)劃算法，通過(guò)解決小問(wèn)題成就大問(wèn)題。
維特比算法實(shí)現(xiàn)分詞是根據(jù)前綴字典，生成所有的可能分詞的有向無(wú)環(huán)圖（DAG），什么叫有向無(wú)環(huán)圖（DAG），如下圖所示：
DAG圖.png
- Step 1: 根據(jù)詞典，輸入的句子和 word_prob來(lái)創(chuàng)建帶權(quán)重的有向圖（Directed Graph）
- Step 2: 編寫維特比算法（viterebi）算法來(lái)找出其中最好的PATH， 也就是最好的句子切分
- Step 3: 返回結(jié)果
1.創(chuàng)建DAG
def DAG(sentence):
DAG = {}
N = len(sentence)
for k in range(N):
tmplist = []
i = k
frag = sentence[k]
while i<N:
if frag in word_prob.keys():
tmplist.append(i)
i+=1
frag = sentence[k:i+1]
# 如果都沒(méi)有分到的話，就自己
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
print(DAG('今天的課程內(nèi)容很有意思'))
輸出的結(jié)果：{0: [0, 1], 1: [1], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6], 6: [6], 7: [7], 8: [8, 9, 10], 9: [9, 10], 10: [10]}
就是找出所有分詞情況的有向圖，比如0:[0,1]表示0是開(kāi)始的詞的位置，后面是可以跟哪個(gè)位置的詞組成的下標(biāo)。其表示的意思是”經(jīng)，經(jīng)?！敖?jīng)常就有兩種表示方式。
- 找出最好句子切分
def best_path(sentence,DAG):
N=len(sentence)
route={}
route[N] = (0, 0)
for idx in range(N - 1, -1, -1):
distance = (((word_prob.get(sentence[idx:x+1]) or 0) + route[x+1][0],x) for x in DAG[idx])
route[idx] = min(distance)
# 得到最大概率值和詞的末位
print(route)
return route
- 找出最好的切分
# TODO: 第三步： 根據(jù)最好的PATH, 返回最好的切分
N = len(input_str)
seg = []
x=0
while x<N:
y = route[x][1]+1
seg.append(input_str[x:y])
x = y
print(seg)
- 測(cè)試
# 測(cè)試
print (word_segment_viterbi("北京的天氣真好啊"))
print (word_segment_viterbi("今天的課程內(nèi)容很有意思"))
print (word_segment_viterbi("經(jīng)常有意見(jiàn)分歧"))
['北京', '的', '天氣', '真好', '啊']
['今天', '的', '課程', '內(nèi)容', '很', '有意思']
['經(jīng)常', '有', '意見(jiàn)', '分歧']'
TODO: 第一種方法和第二種方法的時(shí)間復(fù)雜度和空間復(fù)雜度分別是多少？
- 第一個(gè)方法：
時(shí)間復(fù)雜度=N^2logN , 空間復(fù)雜度= O(N) - 第二個(gè)方法：
時(shí)間復(fù)雜度= N^2, 空間復(fù)雜度= O(1)
所以明顯用維特比算法在時(shí)間和空間上都是很節(jié)省的。
