聊天机器人-分词

作者: 魏鹏飞 | 来源:发表于2019-10-03 16:17 被阅读0次

定义功能管道

pipeline

Segmentation Method(分词方法)

前向最大匹配
后向最大匹配
...

参考：江州市长江大桥参加了长江大桥的通车仪式

1. 前向最大匹配（forward-max matching）

例子：我们经常有文化差异
词典：[“我们”，“经常”，“有”，“有文化”，“文化”，“差异”]

令：max_length=5，则：

第一步	第二步	第三步	第四步
我们经常有 $\times$	经常有文化 $\times$	有文化差异 $\times$	差异 $\surd$
我们经常 $\times$	经常有文 $\times$	有文化差 $\times$
我们经 $\times$	经常有 $\times$	有文化 $\surd$
我们 $\surd$	经常 $\surd$

结果：我们/经常/有文化/差异

2. 后向最大匹配（backword-max matching）

例子：我们经常有文化差异
词典：[“我们”，“经常”，“有”，“有文化”，“文化”，“差异”]

令：max_length=5，则：

第一步	第二步	第三步	第四步
有文化差异 $\times$	经常有文化 $\times$	我们经常 $\times$	我们 $\surd$
文化差异 $\times$	常有文化 $\times$	们经常 $\times$
化差异 $\times$	有文化 $\surd$	经常 $\surd$
差异 $\surd$

结果：我们/经常/有文化/差异

思考一下这两种算法存在的问题：

不能细分（细分有可能更好）
局部最优
效率低（效率依赖于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 ，高通公司创始人之一，高通首席科学家。他开发了卷积码编码的最大似然算法而享誉全球。

找出递推式
找出终止条件

$f(n)$	函数	函数值	位置
min $f(7)$	$f(7)=min\begin{cases}f(6)+20\\f(5)+1.6\\f(4)+3 \end{cases}$	6.2	5
min $f(6)$	$f(6)=f(5)+2.3$	6.9	5
min $f(5)$	$f(5)=min\begin{cases}f(4)+3\\f(3)+1.6\\f(2)+2.3\end{cases}$	4.6	2
min $f(4)$	$f(4)=f(3)+3$	7.6	3
min $f(3)$	$f(3)=f(2)+2.3$	4.6	2
min $f(2)$	$f(2)=min\begin{cases}f(1)+20\\f(0)+2.3\end{cases}$	2.3	0
min $f(1)$	$f(1)=f(0)+3$	3	1
min $f(0)$	$f(0)=0$	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]
['经常', '有', '意见', '分歧']

聊天机器人-分词

定义功能管道

Segmentation Method(分词方法)

维特比介绍：

编写程序代码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读