devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

分词学习(3)，基于ngram语言模型的n元分词_n元语法分词怎么计算

作者：繁依Fanyi0 | 2024-04-01 07:50:35

赞

踩

n元语法分词怎么计算

           最大概率分词中，认为每个词的概率都是独立的，但是有一部分词，其切分却与前一个词密切相关，特别是中文分词中更为明显，英文中就是如上一篇文章中的“tositdown”的例子。

         这样就可以使用2元模型，就是如一个分割形式"ab cde f"的概率，

如果按照1-gram计算：P(ab cde f) = P(ab)*P(cde)*P(f)

如果按照2-gram计算：P(ab cde f) = P(ab|<s>)*P(cde|ab)P(f|cde)

基本的方法和最大概率分词差不多，就是计算片段概率的时候，需要知道选择的前驱节点的前驱节点位置，这样才能计算转移概率。具体如下图所示：




确定当前节点4的状态，就是根据几个概率累计值，取最大的，即可确定前驱节点和当前节点的累积概率

上代码(Python)：

[python] view plain copy
  1. #!/usr/bin/env python  
  2. #coding=utf-8  
  3. #############################################################  
  4. #function: max probility segment  
  5. #          a dynamic programming method  
  6. #  
  7. #input: dict file  
  8. #output: segmented words, divide by delimiter "\ "  
  9. #author: wangliang.f@gmail.com  
  10. ##############################################################  
  11. import sys   
  12. import math  
  13.   
  14. #global parameter  
  15. DELIMITER = " " #分词之后的分隔符  
  16.   
  17. class DNASegment:  
  18.     def __init__(self):  
  19.         self.word1_dict = {} #记录概率,1-gram  
  20.         self.word1_dict_count = {} #记录词频,1-gram  
  21.         self.word1_dict_count["<S>"] = 8310575403 #开始的<S>的个数   
  22.   
  23.         self.word2_dict = {} #记录概率,2-gram  
  24.         self.word2_dict_count = {} #记录词频,2-gram  
  25.   
  26.   
  27.         self.gmax_word_length = 0  
  28.         self.all_freq = 0 #所有词的词频总和,1-gram的  
  29.   
  30.     #估算未出现的词的概率,根据beautiful data里面的方法估算  
  31.     def get_unkonw_word_prob(self, word):  
  32.         return math.log(10./(self.all_freq*10**len(word)))  
  33.   
  34.     #获得片段的概率  
  35.     def get_word_prob(self, word):  
  36.         if self.word1_dict.has_key(word): #如果字典包含这个词  
  37.             prob = self.word1_dict[word]  
  38.         else:  
  39.             prob = self.get_unkonw_word_prob(word)  
  40.         return prob  
  41.   
  42.   
  43.     #获得两个词的转移概率  
  44.     def get_word_trans_prob(self, first_word, second_word):  
  45.         trans_word =  first_word + " " + second_word  
  46.         #print trans_word  
  47.         if self.word2_dict_count.has_key(trans_word):  
  48.             trans_prob = \  
  49.     math.log(self.word2_dict_count[trans_word]/self.word1_dict_count[first_word])  
  50.         else:  
  51.             trans_prob = self.get_word_prob(second_word)  
  52.         return trans_prob  
  53.   
  54.     #寻找node的最佳前驱节点  
  55.     #方法为寻找所有可能的前驱片段  
  56.     def get_best_pre_node(self, sequence, node, node_state_list):  
  57.         #如果node比最大词长小，取的片段长度以node的长度为限  
  58.         max_seg_length = min([node, self.gmax_word_length])  
  59.         pre_node_list = [] #前驱节点列表  
  60.   
  61.         #获得所有的前驱片段，并记录累加概率  
  62.         for segment_length in range(1,max_seg_length+1):  
  63.   
  64.             pre_node = segment_start_node  #取该片段，则记录对应的前驱节点  
  65.   
  66.             if pre_node == 0:  
  67.                 #如果前驱片段开始节点是序列的开始节点，  
  68.                 #则概率为<S>转移到当前词的概率  
  69.                 #segment_prob = self.get_word_prob(segment)  
  70.                 segment_prob = \  
  71.                         self.get_word_trans_prob("<S>", segment)  
  72.             else: #如果不是序列开始节点，按照二元概率计算  
  73.                 #获得前驱片段的前一个词  
  74.                 pre_pre_node = node_state_list[pre_node]["pre_node"]  
  75.                 pre_pre_word = sequence[pre_pre_node:pre_node]  
  76.                 segment_prob = \  
  77.                         self.get_word_trans_prob(pre_pre_word, segment)  
  78.   
  79.   
  80.             #当前node一个候选的累加概率值  
  81.             candidate_prob_sum = pre_node_prob_sum + segment_prob  
  82.   
  83.             pre_node_list.append((pre_node, candidate_prob_sum))  
  84.   
  85.         #找到最大的候选概率值  
  86.         (best_pre_node, best_prob_sum) = \  
  87.                 max(pre_node_list,key=lambda d:d[1])  
  88.         return (best_pre_node, best_prob_sum)  
  89.   
  90.     #最大概率分词  
  91.     def mp_seg(self, sequence):  
  92.         sequence = sequence.strip()  
  93.   
  94.         #初始化  
  95.         node_state_list = [] #记录节点的最佳前驱，index就是位置信息  
  96.         #初始节点，也就是0节点信息  
  97.         ini_state = {}  
  98.         ini_state["pre_node"] = -1 #前一个节点  
  99.         ini_state["prob_sum"] = 0 #当前的概率总和  
  100.         node_state_list.append( ini_state )  
  101.         #字符串概率为2元概率  
  102.         #P(a b c) = P(a|<S>)P(b|a)P(c|b)  
  103.   
  104.         #逐个节点寻找最佳前驱节点  
  105.         for node in range(1,len(sequence) + 1):  
  106.             #寻找最佳前驱，并记录当前最大的概率累加值  
  107.             (best_pre_node, best_prob_sum) = \  
  108.                     self.get_best_pre_node(sequence, node, node_state_list)  
  109.   
  110.             #添加到队列  
  111.             cur_node = {}  
  112.             cur_node["pre_node"] = best_pre_node  
  113.             cur_node["prob_sum"] = best_prob_sum  
  114.             node_state_list.append(cur_node)  
  115.             #print "cur node list",node_state_list  
  116.   
  117.         # step 2, 获得最优路径,从后到前  
  118.         best_path = []  
  119.         node = len(sequence) #最后一个点  
  120.         best_path.append(node)  
  121.         while True:  
  122.             pre_node = node_state_list[node]["pre_node"]  
  123.             if pre_node == -1:  
  124.                 break  
  125.             node = pre_node  
  126.             best_path.append(node)  
  127.         best_path.reverse()  
  128.   
  129.         # step 3, 构建切分  
  130.         word_list = []  
  131.         for i in range(len(best_path)-1):  
  132.             left = best_path[i]  
  133.             word_list.append(word)  
  134.   
  135.         seg_sequence = DELIMITER.join(word_list)  
  136.         return seg_sequence  
  137.   
  138.     #加载词典，为词\t词频的格式  
  139.     def initial_dict(self, gram1_file, gram2_file):  
  140.         #读取1_gram文件  
  141.         dict_file = open(gram1_file, "r")  
  142.         for line in dict_file:  
  143.             sequence = line.strip()  
  144.             key = sequence.split('\t')[0]  
  145.             value = float(sequence.split('\t')[1])  
  146.             self.word1_dict_count[key] = value  
  147.         #计算频率  
  148.         self.all_freq = sum(self.word1_dict_count.itervalues()) #所有词的词频  
  149.         self.gmax_word_length = 20  
  150.         self.all_freq = 1024908267229.0  
  151.         #计算1gram词的概率  
  152.         for key in self.word1_dict_count:  
  153.             self.word1_dict[key] = math.log(self.word1_dict_count[key]/self.all_freq)  
  154.   
  155.         #读取2_gram_file，同时计算转移概率  
  156.         dict_file = open(gram2_file, "r")  
  157.         for line in dict_file:  
  158.             sequence = line.strip()  
  159.             key = sequence.split('\t')[0]  
  160.             value = float(sequence.split('\t')[1])  
  161.             first_word = key.split(" ")[0]  
  162.             second_word = key.split(" ")[1]  
  163.             self.word2_dict_count[key] = float(value)  
  164.             if self.word1_dict_count.has_key(first_word):  
  165.                 self.word2_dict[key] = \  
  166.                     math.log(value/self.word1_dict_count[first_word])  #取自然对数  
  167.             else:  
  168.                 self.word2_dict[key] = self.word1_dict[second_word]  
  169. #test  
  170. if __name__=='__main__':  
  171.     myseg = DNASegment()  
  172.     myseg.initial_dict("count_1w.txt","count_2w.txt")  
  173.     sequence = "itisatest"  
  174.     seg_sequence = myseg.mp_seg(sequence)  
  175.     print "original sequence: " + sequence  
  176.     print "segment result: " + seg_sequence  
  177.   
  178.     sequence = "tositdown"  
  179.     seg_sequence = myseg.mp_seg(sequence)  
  180.     print "original sequence: " + sequence  
  181.     print "segment result: " + seg_sequence  

可以看到

这样，itistst，仍然可以分成 it is a test

而前面分错的tositedown，则正确的分为to sit down

代码和字典见附件：http://pan.baidu.com/s/1bnw197L

        但这样的分词显然还有一些问题，就是一个词是由前一个或者几个词决定的，这样可以去除一部分歧义问题，但是ngram模型还是基于马尔科夫模型的，其基本原理就是无后效性，就是后续的节点的状态不影响前面的状态，就是先前的分词形式一旦确定，无论后续跟的是什么词，都不会再有变化，这在现实中显然是不成立的。因此就有一些可以考虑到后续词的算法，如crf等方法，局可以参考相应的资料，这些算法，用几十行python代码一般很难写出来，因此，一般会使用具体的代码包来做。如crf++,http://crfpp.googlecode.com/svn/trunk/doc/index.html

等

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/347842
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号