今天是周日，天气很潮湿，回南天的广州，即使天气再恶劣，也不能阻止学习的我。。。
每一个入门自然语言的的人在学习的第一步都是从分词开始的，就类似编程的"Hello World"。以下是用两种方法实现分词，分别是基于枚举法和维特比算法。
一、基于枚举方法来搭建中文分词工具
最简单的分词是不依赖语句关系的，每一个词都是独立的，叫unigram
语言模型有unigram->bi-gram->n-gram 从简单到难，n表示依赖n级
此项目所需数据：
- 中文词库词库，当作字典来用
- 以变量的方式提供了部分unigram概率 word_prob，也可以用词库的计算词频。
- 举个例子： 给定词典=[我们 学习 人工 智能 人工智能 未来 是]， 另外我们给定unigram概率：p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15
Step 1: 对于给定字符串：”我们学习人工智能，人工智能是未来“, 找出所有可能的分割方式
- [我们，学习，人工智能，人工智能，是，未来]
- [我们，学习，人工，智能，人工智能，是，未来]
- [我们，学习，人工，智能，人工，智能，是，未来]
- [我们，学习，人工智能，人工，智能，是，未来] .......
Step 2: 我们也可以计算出每一个切分之后句子的概率
- p(我们，学习，人工智能，人工智能，是，未来)= -log p(我们)-log p(学习)-log p(人工智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们，学习，人工，智能，人工智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们，学习，人工，智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工)-log p(智能)-log p(是)-log p(未来)
- p(我们，学习，人工智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工智能)-log p(人工)-log p(智能)-log(是)-log p(未来) .....
Step 3: 返回第二步中概率最大的结果,就是-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 # 保存词典库中读取的单词
以下是计算的时候出现用得到的词频，分出来的词计算时，符合下面的就用下面的词频，否则就统一设置成0.00001
由于很多词都是0.00001，计算出来太多小数点，所以进行log取值，好看一点。
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,"内容":0.06,"有":0.05,"很":0.03,"很有":0.04,"意思":0.06,"有意思":0.005,"课":0.01,
"程":0.005,"经常":0.08,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.02,"分歧":0.04,"分":0.02, "歧":0.005}
#因为计算出来都是负数，所以加个-负号得正，todo 计算-log(x)
for word in word_prob.keys():
word_prob[word] = round(-math.log(word_prob[word]),1)
print(word_prob.values())
image.png
下面获取输入的句子，得到所有的分词，主要用到的办法是递归法：
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
- 对于输入字符串做分词，并返回所有可行的分词之后的结果。
- 针对于每一个返回结果，计算句子的概率
- 返回概率最高的最作为最后结果
def word_segment_naive(input_str):
"""
1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。
2. 针对于每一个返回结果，计算句子的概率
3. 返回概率最高的最作为最后结果
input_str: 输入字符串 输入格式：“今天天气好”
best_segment: 最好的分词结果 输出格式：["今天"，"天气"，"好"]
"""
TODO： 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里，这个结果有可能会非常多。
segments = word_break(input_str,dic_words) # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)
格式为：segments = [["今天"，“天气”，“好”],["天"，“天“，”气”，“好”],["今“，”天"，“天气”，“好”],...]
TODO: 第二步：循环所有的分词结果，并计算出概率最高的分词结果，并返回
best_segment = []
best_score = math.inf #无限大
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
测试结果
print (word_segment_naive("你经常做主"))
print (word_segment_naive("今天的课程内容很有意思"))
print (word_segment_naive("经常有意见分歧"))
最佳分词结果如下图所示：
分词.png
总结：枚举法分词不但时间复杂度高，空间复杂度也是很高，如果数据量很大的情况下，是非常不乐观的一个实现方法，是否有比这个更好的方法呢？当然有，算法如此强大，只要有发现。那么接下来看看维特比算法（vitebi）实现分词工具。
二、基于维特比算法来优化上述流程
维特比算法用的是动态规划算法，通过解决小问题成就大问题。
维特比算法实现分词是根据前缀字典，生成所有的可能分词的有向无环图（DAG），什么叫有向无环图（DAG），如下图所示：
DAG图.png
- Step 1: 根据词典，输入的句子和 word_prob来创建带权重的有向图（Directed Graph）
- Step 2: 编写维特比算法（viterebi）算法来找出其中最好的PATH， 也就是最好的句子切分
- Step 3: 返回结果
1.创建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]
# 如果都没有分到的话，就自己
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
print(DAG('今天的课程内容很有意思'))
输出的结果：{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是开始的词的位置，后面是可以跟哪个位置的词组成的下标。其表示的意思是”经，经常“经常就有两种表示方式。
- 找出最好句子切分
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: 第三步： 根据最好的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)
- 测试
# 测试
print (word_segment_viterbi("北京的天气真好啊"))
print (word_segment_viterbi("今天的课程内容很有意思"))
print (word_segment_viterbi("经常有意见分歧"))
['北京', '的', '天气', '真好', '啊']
['今天', '的', '课程', '内容', '很', '有意思']
['经常', '有', '意见', '分歧']'
TODO: 第一种方法和第二种方法的时间复杂度和空间复杂度分别是多少？
- 第一个方法：
时间复杂度=N^2logN , 空间复杂度= O(N) - 第二个方法：
时间复杂度= N^2, 空间复杂度= O(1)
所以明显用维特比算法在时间和空间上都是很节省的。
