定义功能管道
pipeline
Segmentation Method(分词方法)
- 前向最大匹配
- 后向最大匹配
- ...
参考：江州市长江大桥参加了长江大桥的通车仪式
1. 前向最大匹配（forward-max matching）
例子：我们经常有文化差异
词典：[“我们”，“经常”，“有”，“有文化”，“文化”，“差异”]
令：max_length=5，则：
| 第一步 | 第二步 | 第三步 | 第四步 |
|---|---|---|---|
| 我们经常有 |
经常有文化 |
有文化差异 |
差异 |
| 我们经常 |
经常有文 |
有文化差 |
|
| 我们经 |
经常有 |
有文化 |
|
| 我们 |
经常 |
结果：我们/经常/有文化/差异
2. 后向最大匹配（backword-max matching）
例子：我们经常有文化差异
词典：[“我们”，“经常”，“有”，“有文化”，“文化”，“差异”]
令：max_length=5，则：
| 第一步 | 第二步 | 第三步 | 第四步 |
|---|---|---|---|
| 有文化差异 |
经常有文化 |
我们经常 |
我们 |
| 文化差异 |
常有文化 |
们经常 |
|
| 化差异 |
有文化 |
经常 |
|
| 差异 |
结果：我们/经常/有文化/差异
思考一下这两种算法存在的问题：
- 不能细分（细分有可能更好）
- 局部最优
- 效率低（效率依赖于max_length）
- 歧义（不能考虑语义）
最好能上层看到语义
根据上述分词方法或其它方法，对于上面句子可能有多种分词结果：
- s1 = 我们/经常/有文化/差异
- s2 = 我们/经常/有/文化/差异
3. Incorporate Semantic（考虑语义）
例子：经常有文化差异
词典：[“经常”，“经”，“有”，“有文化”，“文化”，“差异”，“文”， “化”，“化差异”， “差”]
概率：[0.1，0.05，0.1，0.1，0.2，0.2，0.05，0.05，0.05，0.1]
-log(x)：[2.3，3，2.3，2.3，1.6，1.6，3，3，3，2.3]
输入---(第一阶段)--->生成所有可能的分割---(第二阶段)--->选择其中最合适的
第一阶段有大量分割方式：
- 我们/经常/有/文化/差异
------> S1 - 我们/经常/有/文化/差异
------> S2 - 我们/经常/有/文/化/差异
------> S3 - 我/们/经/常/有/文/化/差/异
------> S4 - ...
------> Sn
第二阶段计算概率（时间复杂度较高）：
同一个句子，多种分词结果，如何评估得出最合适的那个呢？
答案：最好的工具就是语言模型(Language Model)，P(我们/经常/有/文化/差异) = 0.6 > P(我们/经常/有文化/差异) = 0.4
Unigram：P(我们,经常，有，文化，差异)=P(我们)*P(经常)*P(有)*P(文化)*P(差异)
FSM
上述FSM（Finite State Machine）如何求出最短路径呢？
答案：维特比算法（Viterbi）
维特比介绍：
维特比
安德鲁·维特比（Andrew J. Viterbi），CDMA之父，IEEE Fellow ，高通公司创始人之一，高通首席科学家。他开发了卷积码编码的最大似然算法而享誉全球。
- 找出递推式
- 找出终止条件
| 函数 | 函数值 | 位置 | |
|---|---|---|---|
| min |
6.2 | 5 | |
| min |
6.9 | 5 | |
| min |
4.6 | 2 | |
| min |
7.6 | 3 | |
| min |
4.6 | 2 | |
| min |
2.3 | 0 | |
| min |
3 | 1 | |
| min |
0 | 0 |
则：最短路线是：7 <------ 5 <------ 2 <------ 0
编写程序代码
- 方法一
import xlrd
# 基于枚举方法来搭建中文分词工具
# 获取一个Book对象
workbook = xlrd.open_workbook('data/综合类中文词库.xlsx')
dic_words = set() # 保存词典库中读取的单词
# 获取一个sheet对象的列表
booksheet = workbook.sheet_by_index(0)
for row in booksheet.get_rows():
dic_words.add(row[0].value)
print('len:' + str(len(dic_words)))
# 以下是每一个单词出现的概率。为了问题的简化，我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的，统一把概率设置成为0.00001
# 比如 p("学院")=p("概率")=...0.00001
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}
print (sum(word_prob.values()))
# 前向最大匹配（贪心法）
def forward_max_match(sentence, wordDict):
max_length = 5
res = []
while len(sentence) > 0:
try_word = sentence[0:max_length]
while try_word not in wordDict:
if len(try_word) == 1:
break
try_word = try_word[0:len(try_word)-1]
res.append(try_word)
sentence = sentence[len(try_word):]
return res
# forward_max_match('北京的天气真好啊', dic_words)
# 后向最大匹配（贪心法）
def backword_max_match(sentence, wordDict):
max_length = 5
res = []
while len(sentence) > 0:
try_word = sentence[-max_length:]
while try_word not in wordDict:
if len(try_word) == 1:
break
try_word = try_word[1:]
res.append(try_word)
sentence = sentence[0:len(sentence)-len(try_word)]
# 反转列表
res.reverse()
return res
# backword_max_match('北京的天气真好啊', dic_words)
# 暴力求解（递归）
def word_break(sentence, wordDict):
def cut_sentences(sentence):
result = []
if not sentence:
return ['']
for cur in range(1, len(sentence)+1):
word = sentence[0:cur]
if word in wordDict:
result += [word + (tail and ',' + tail) for tail in cut_sentences(sentence[cur:])]
return result
new_sentence = []
for line in cut_sentences(sentence):
line = line.split(',')
new_sentence.append(line)
return new_sentence
word_break('北京的天气真好啊', dic_words)
word_break('今天的课程内容很有意思', dic_words)
from math import log
## TODO: 编写word_segment_naive函数来实现对输入字符串的分词
def word_segment_naive(input_str):
"""
1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。
2. 针对于每一个返回结果，计算句子的概率
3. 返回概率最高的最作为最后结果
input_str: 输入字符串 输入格式：“今天天气好”
best_segment: 最好的分词结果 输出格式：["今天"，"天气"，"好"]
"""
# TODO: 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里，这个结果有可能会非常多。
segments = word_break(input_str, dic_words) # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)
# 格式为：segments = [["今天"，“天气”，“好”],["今天"，“天“，”气”，“好”],["今“，”天"，“天气”，“好”],...]
# print(segments)
# TODO: 第二步：循环所有的分词结果，并计算出概率最高的分词结果，并返回
best_segment = []
best_score = float('inf')
for seg in segments:
current_score = 0.0
for word in seg:
if word in word_prob:
current_score -= log(word_prob.get(word))
else:
current_score -= log(0.00001)
if best_score > current_score:
best_score = current_score
best_segment = seg
return best_segment
# 测试
print (word_segment_naive("北京的天气真好啊"))
print (word_segment_naive("今天的课程内容很有意思"))
print (word_segment_naive("经常有意见分歧"))
# 结果
len:298032
1.0000000000000002
['北京', '的', '天气', '真好', '啊']
['今天', '的', '课程', '内容', '很', '有意思']
['经常', '有', '意见', '分歧']
- 方法二
from math import log
import xlrd
# 基于维特比算法来搭建中文分词工具
# 获取一个Book对象
workbook = xlrd.open_workbook('data/综合类中文词库.xlsx')
dic_words = set() # 保存词典库中读取的单词
# 获取一个sheet对象的列表
booksheet = workbook.sheet_by_index(0)
for row in booksheet.get_rows():
dic_words.add(row[0].value)
print('len:' + str(len(dic_words)))
# 以下是每一个单词出现的概率。为了问题的简化，我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的，统一把概率设置成为0.00001
# 比如 p("学院")=p("概率")=...0.00001
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}
print (sum(word_prob.values()))
## TODO 编写word_segment_viterbi函数来实现对输入字符串的分词
def word_segment_viterbi(input_str):
"""
1. 基于输入字符串，词典，以及给定的unigram概率来创建DAG(有向图）。
2. 编写维特比算法来寻找最优的PATH
3. 返回分词结果
input_str: 输入字符串 输入格式：“今天天气好”
best_segment: 最好的分词结果 输出格式：["今天"，"天气"，"好"]
"""
# TODO: 第一步：根据词典，输入的句子，以及给定的unigram概率来创建带权重的有向图（Directed Graph） 参考：课程内容
# 有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在
# 词典里存在的，统一用概率值0.00001。
# 注意：思考用什么方式来存储这种有向图比较合适？ 不一定有只有一种方式来存储这种结构。
graph = {}
for i in range(len(input_str)-1, -1, -1):
temp_list = []
k = i
# 位置k形成的片段
frag = input_str[k]
while k >= 0 and frag in dic_words:
# 将该片段加入到有向无环图中
temp_list.append(k)
k -= 1
# 产生新的片段
frag = input_str[k:i+1]
if not temp_list:
temp_list.append(i)
# 片段末尾位置加1
graph[i+1] = temp_list
# print(graph)
# TODO： 第二步： 利用维特比算法来找出最好的PATH， 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。
# hint: 思考为什么不用相乘: p(w1)p(w2)...而是使用negative log sum: -log(w1)-log(w2)-...
path_f = [0]
value_f = [0]
for i in range(1, len(graph)+1):
min_path = float('inf')
min_value = float('inf')
for j in graph.get(i):
current_value = 0.0
word = input_str[j:i]
if word in word_prob:
current_value = -log(word_prob.get(word)) + value_f[j]
else:
current_value = -log(0.00001) + value_f[j]
if min_value > current_value:
min_value = current_value
min_path = j
path_f.append(min_path)
value_f.append(min_value)
# print(path_f)
# print(value_f)
# 获取最好的path
best_path = []
k = len(path_f)-1
best_path.append(k)
while k>0:
k = path_f[k]
best_path.append(k)
best_path.reverse()
print(best_path)
# TODO: 第三步： 根据最好的PATH, 返回最好的切分
best_segment = []
for k in range(len(best_path)-1):
best_segment.append(input_str[best_path[k]:best_path[k+1]])
return best_segment
# 测试
print(word_segment_viterbi("北京的天气真好啊"))
print(word_segment_viterbi("今天的课程内容很有意思"))
print(word_segment_viterbi("经常有意见分歧"))
# 结果
len:298032
1.0000000000000002
[0, 2, 3, 5, 7, 8]
['北京', '的', '天气', '真好', '啊']
[0, 2, 3, 5, 7, 8, 11]
['今天', '的', '课程', '内容', '很', '有意思']
[0, 2, 3, 5, 7]
['经常', '有', '意见', '分歧']
