NLP基础：枚举法和维特比搭建分词

标签：NLP 概率 word 枚举法 mem str 字符串分词

文章目录

一. 任务介绍

任务描述
数据集

二. 原理介绍

最大匹配
考虑语义

枚举法

LeetCode 139 单词拆分Ⅰ
LeetCode 140 单词拆分Ⅱ

维特比

三. 实现

1. 基于枚举方法搭建中文分词工具
2. 基于维特比算法来优化

一. 任务介绍

任务描述

利用枚举法来实现分词，也就是首先把所有可能的分词结果列出来，然后通过Unigram模型来选择最好的分词结构（这部分的难点在于怎么生成所有的可能的分词结果）(通过Perplexity来评判何为最好)
利用维特比算法来实现分词。这部分首先需要创建一个有向图，然后根据维特比算法来计算出最好的分词结果，这部分里的创建有向图和维特比部分需要一定的思考

数据集

综合类中文词库.xlsx：包含了中文词及词出现的频率，当做词典来用，也可以用算出每个词在词典中的概率；

NLP基础：枚举法和维特比搭建分词_字符串

二. 原理介绍

总体来说，分词的方法主要有两大类：最大匹配和考虑语义。

最大匹配

最大匹配分为前向最大匹配、后向最大匹配和双向最大匹配，其中三者都是需要用已有的词典来匹配输入，只是区别是顺序不同。以前向最大匹配为例：
例：要分词的句子是"我们经常有意见分歧"，现有的词典为：[我们,经常,有,有意见,意见,分歧]

首先先设置最大匹配长度，max_len = 5;
对要分词的句子从前到后取max_len个字符，第一次取：‘我们经常有’，然后在这个窗口中从后向前逐字符缩小，直到找到词典中符合的词后就停止匹配，依次得到’我们经常’->‘我们经’->‘我们’，于是分词得到’我们’；
从匹配到的词的下一个字符开始，继续取max_len：‘经常有意见’，然后在这个窗口中从后往前逐个字符缩小，最后匹配到’经常’，于是最后的分词结果为：[‘我们’,‘经常’,‘有意见’]

因为最大匹配的分词方法并未考虑到语义，因此这里不再对其进行实现。

考虑语义

枚举法

考虑语义的基本框架就是根据已有的词典对输入句子枚举出所有可能的分割情况，再通过语言模型判断各个分词句子的概率，最终输出最高概率对应的分词表示结果。
那么这里就需要考虑两个问题：
Q1. 如何生成所有可能的分割情况；
Q2. 如何得出各种分词句子的概率；
对于Q1而言，可以通过递归的方式生成所有可能的分割情况，这里可以参考LeetCode139和LeetCode140两道题目，根据字符串来生成所有的分词匹配，详细解释可以看花花视频。

LeetCode 139 单词拆分Ⅰ

给出一个字符串，以及一个字典，判断该字符串能否找到一种划分，使得划分的单词都存在于字典中。

NLP基础：枚举法和维特比搭建分词_nlp_02

class Solution:
  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    def canBreak(s, m, wordDict):
      ‘’‘
      递归终止条件：
      1. 如果memory字典keys中有这个s，那么直接返回这个key代表的状态值；
      2. 如果字符串s在给出的字典wordDict中，那么这个字符串就可以分为空字符串和其本身，可以返回true
      ’‘’
      if s in m: return m[s]
      if s in wordDict:
        m[s] = True
        return True
      # 开始尝试每一个分割点
      for i in range(1, len(s)):
        # 将字符串分为左右两部分,r为右半部分
        r = s[i:]
        # 如果右半部分在字典中，切左半部分有解的话，则认为有解；
        if r in wordDict and canBreak(s[0:i], m, wordDict):
          m[s] = True
          return True
      # 否则无解
      m[s] = False
      return False
    return canBreak(s, {}, set(wordDict))

LeetCode 140 单词拆分Ⅱ

对字符串进行拆分，要求句子中的每个单词都在字典中，输出所有可能的情况。

NLP基础：枚举法和维特比搭建分词_自然语言处理_03

class Solution:
  def wordBreak(self, s, wordDict):
    # 存储为set，用来判断单词是否存在于字典中
    words = set(wordDict)
    # 定义哈希表存储，key为字符串的str，value为字符串的所有解
    mem = {}
    def wordBreak(s):
      # 递归出口:如果字符串s在字典memory中，就返回该字符串的所有解
      if s in mem: return mem[s]
      # 因为mem是解的并集，因此需要当作全局变量使用，中间不能进行改变
      # ans用来存储当前字符串s的解
      ans = []
      # 如果字符串s在字典中，即s可以被分为空字符串和其自身，判断为可以分
      if s in words: ans.append(s)
      # 开始尝试每一个分割点
      for i in range(1, len(s)):
        right = s[i:]
        # 如果右半部分不在字典里，跳过继续遍历
        if right not in words: continue
        ans += [w + ' ' + right for w in wordBreak(s[0:i])]
      mem[s] = ans
      return mem[s]
    return wordBreak(s)

对于Q2，可以通过语言模型的方法得出各个分词句子的概率：
Unigram model方法:

首先通过统计语料库中单个词和总单词数的频率来得出每个分词的概率；
接着通过对每个分词的概率连乘，得到整体句子出现的概率，进而比较句子概率的大小；
为了防止出现Underflow的情况，将求得的概率加上log，变乘为加，即通过Perplexity来比较句子概率的大小。
优化：因为连乘或连加，可能会导致越细化的分割效果越好，那么可以加上平均的操作，除以整句话中分割的单词数。

维特比

上述枚举法的缺点在于：当要分词的句子很长时，那么排列组合生成所有可能分割的可能性也会很多，而这生成所有可能性的操作是递归生成的，所以需要考虑能否将每个分词的概率提前算出，然后将哪个分词方法的概率最大的问题转换为求由第一个词到最后一个词的最短路径问题。

那么这个问题也可以分为两步：
Q1. 如何将每个分词的概率提前算出，并用其目标结果的最小化代替最大化；
和枚举的方法一样，通过对给出的词库频率统计，统计出每个词的概率。根据词典，输入的句子和 word_prob来创建带权重的有向图，没有值的边要么去掉，要么给一个非常大的值。

Q2. 如何求一个节点到最后一个节点的最短路径：
通过维特比算法来找出其中最好的PATH，也就是最好的句子。
动规开始时从左到右来填写负概率，并记录带方向的指针，记录完后，根据指针的反方向进行推导，得出最短路径。

三. 实现

1. 基于枚举方法搭建中文分词工具

第一步：从xlsx中读取所有中文词，并且算出每个单词的频率计算-log值

# 读取词典
print("Reading dic...")
# 获取一个Book对象
workbook = xlrd.open_workbook("./data/综合类中文词库.xlsx")
dic_words = []  # 保存词典库中读取的单词
dic_freq = []
# 获取第一个sheet对象的列表
booksheet = workbook.sheet_by_index(0)
rows = booksheet.get_rows()
for row in rows:
    dic_words.append(row[0].value)
    dic_freq.append(int(row[2].value.strip()))
dic_freq = np.array(dic_freq)
dic_freq = list(dic_freq/np.sum(dic_freq))
# 统计每一个单词出现的概率
word_prob = dict(zip(dic_words, dic_freq))
# 计算-log(x)
for word in word_prob.keys():
    word_prob[word]= round(-math.log(word_prob[word]),2)
print("len:" + str(len(dic_words)))

NLP基础：枚举法和维特比搭建分词_最大匹配_04

NLP基础：枚举法和维特比搭建分词_字符串_05

第二步：计算所有可能的分词结果，要保证每个分完的词存在于词典里：

def wordBreak(s, wordDict):
    words = set(wordDict)
    mem = {}
    def wordBreak(s):
        if s in mem: return mem[s]
            ans = []
        if s in words: ans.append(s)
        for i in range(1, len(s)):
            right = s[i:]
            if right not in words: continue        
            ans += [w + " " + right for w in wordBreak(s[0:i])]
        mem[s] = ans
        return mem[s]
    return wordBreak(s)

第三步：编写word_segment_naive函数来实现对输入字符串的分词

#  分数（10）
## TODO 请编写word_segment_naive函数来实现对输入字符串的分词
def word_segment_naive(input_str):
    """
    1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。
    2. 针对于每一个返回结果，计算句子的概率
    3. 返回概率最高的最作为最后结果
    
    input_str: 输入字符串   输入格式：“今天天气好”
    best_segment: 最好的分词结果  输出格式：["今天"，"天气"，"好"]
    """
    # TODO： 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里 
    res = wordBreak(input_str, dic_words)
    segments = [i.split(' ') for i in res]  # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)
    # 格式为：segments = [["今天"，“天气”，“好”],["今天"，“天“，”气”，“好”],["今“，”天"，“天气”，“好”],...]
    # TODO: 第二步：循环所有的分词结果，并计算出概率最高的分词结果，并返回
    best_segment = []
    best_score = math.inf  # 因为是-log,故将best_score设为无穷大
    for seg in segments:
        score = 0
        for word in seg:
            if word in word_prob.keys():
                score += word_prob[word]    
            else:
                # 如果没有的话就记为0.00001
                score += round(-math.log(0.00001),2)
        if score < best_score:
            best_score = score
            best_segment = seg
    return best_segment

测试结果如下：

NLP基础：枚举法和维特比搭建分词_字符串_06

2. 基于维特比算法来优化

编写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 ={}
    N = len(input_str)
    for i in range(N,0,-1):
        k=i-1
        in_list=[]
        flag=input_str[k:i]
        while k>=0 and flag in dic_words:
            in_list.append(k)
            k-=1
            flag = input_str[k:i]
        graph[i]=in_list
    
    #TODO： 第二步： 利用维特比算法来找出最好的PATH， 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。
    mem=[0]* (N+1)
    last_index=[0]*(N+1)
    for i in range(1,N+1):
        min_dis=math.inf
        for j in graph[i]:
            if input_str[j:i] in word_prob.keys():
                #      有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在
                #      词典里存在的，统一用概率值0.00001。
                if min_dis > mem[j]+round(word_prob[input_str[j:i]],1):
                    min_dis=mem[j]+round(word_prob[input_str[j:i]],1)
                    last_index[i]=j
            else:
                if min_dis > mem[j]+round(-math.log(0.00001),1):
                    min_dis=mem[j]+round(-math.log(0.00001),1)
                    last_index[i]=j
        mem[i]=min_dis
    
    # TODO: 第三步： 根据最好的PATH, 返回最好的切分
    best_segment=[]
    j=N
    while True:
        best_segment.append(input_str[last_index[j]:j])
        j=last_index[j]
        if j==0 and last_index[j]==0:
            break
    best_segment.reverse()
    return best_segment

枚举法的时间复杂度为n方logn，维特比方法的时间复杂度为n方.

标签：NLP,概率,word,枚举法,mem,str,字符串,分词
From： https://blog.51cto.com/u_15955938/6039468