最大概率分词中，认为每个词的概率都是独立的，但是有一部分词，其切分却与前一个词密切相关，特别是中文分词中更为明显，英文中就是如上一篇文章中的“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)：
#!/usr/怕孤单的发卡/env python#coding=utf-8##############################################################function: max probility segment# a dynamic programming method##input: dict file#output: segmented words, divide by delimiter " "#author: wangliang.f@gmail.com##############################################################import sys import math#global parameterDELIMITER = " " #分词之后的分隔符class DNASegment: def __init__(self): self.word1_dict = {} #记录概率,1-gram self.word1_dict_count = {} #记录词频,1-gram self.word1_dict_count["<S>"] = 8310575403 #开始的<S>的个数 self.word2_dict = {} #记录概率,2-gram self.word2_dict_count = {} #记录词频,2-gram self.gmax_word_length = 0 self.all_freq = 0 #所有词的词频总和,1-gram的 #估算未出现的词的概率,根据beautiful data里面的方法估算 def get_unkonw_word_prob(self, word): return math.log(10./(self.all_freq*10**len(word))) #获得片段的概率 def get_word_prob(self, word): if self.word1_dict.has_key(word): #如果字典包含这个词 prob = self.word1_dict[word] else: prob = self.get_unkonw_word_prob(word) return prob #获得两个词的转移概率 def get_word_trans_prob(self, first_word, second_word): trans_word = first_word + " " + second_word #print trans_word if self.word2_dict_count.has_key(trans_word): trans_prob = math.log(self.word2_dict_count[trans_word]/self.word1_dict_count[first_word]) else: trans_prob = self.get_word_prob(second_word) return trans_prob #寻找node的最佳前驱节点 #方法为寻找所有可能的前驱片段 def get_best_pre_node(self, sequence, node, node_state_list): #如果node比最大词长小，取的片段长度以node的长度为限 max_seg_length = min([node, self.gmax_word_length]) pre_node_list = [] #前驱节点列表 #获得所有的前驱片段，并记录累加概率 for segment_length in range(1,max_seg_length+1): pre_node = segment_start_node #取该片段，则记录对应的前驱节点 if pre_node == 0: #如果前驱片段开始节点是序列的开始节点， #则概率为<S>转移到当前词的概率 #segment_prob = self.get_word_prob(segment) segment_prob = self.get_word_trans_prob("<S>", segment) else: #如果不是序列开始节点，按照二元概率计算 #获得前驱片段的前一个词 pre_pre_node = node_state_list[pre_node]["pre_node"] pre_pre_word = sequence[pre_pre_node:pre_node] segment_prob = self.get_word_trans_prob(pre_pre_word, segment) #当前node一个候选的累加概率值 candidate_prob_sum = pre_node_prob_sum + segment_prob pre_node_list.append((pre_node, candidate_prob_sum)) #找到最大的候选概率值 (best_pre_node, best_prob_sum) = max(pre_node_list,key=lambda d:d[1]) return (best_pre_node, best_prob_sum) #最大概率分词 def mp_seg(self, sequence): sequence = sequence.strip() #初始化 node_state_list = [] #记录节点的最佳前驱，index就是位置信息 #初始节点，也就是0节点信息 ini_state = {} ini_state["pre_node"] = -1 #前一个节点 ini_state["prob_sum"] = 0 #当前的概率总和 node_state_list.append( ini_state ) #字符串概率为2元概率 #P(a b c) = P(a|<S>)P(b|a)P(c|b) #逐个节点寻找最佳前驱节点 for node in range(1,len(sequence) + 1): #寻找最佳前驱，并记录当前最大的概率累加值 (best_pre_node, best_prob_sum) = self.get_best_pre_node(sequence, node, node_state_list) #添加到队列 cur_node = {} cur_node["pre_node"] = best_pre_node cur_node["prob_sum"] = best_prob_sum node_state_list.append(cur_node) #print "cur node list",node_state_list # step 2, 获得最优路径,从后到前 best_path = [] node = len(sequence) #最后一个点 best_path.append(node) while True: pre_node = node_state_list[node]["pre_node"] if pre_node == -1: break node = pre_node best_path.append(node) best_path.reverse() # step 3, 构建切分 word_list = [] for i in range(len(best_path)-1): left = best_path[i] word_list.append(word) seg_sequence = DELIMITER.join(word_list) return seg_sequence #加载词典，为词t词频的格式 def initial_dict(self, gram1_file, gram2_file): #读取1_gram文件 dict_file = open(gram1_file, "r") for line in dict_file: sequence = line.strip() key = sequence.split('t')[0] value = float(sequence.split('t')[1]) self.word1_dict_count[key] = value #计算频率 self.all_freq = sum(self.word1_dict_count.itervalues()) #所有词的词频 self.gmax_word_length = 20 self.all_freq = 1024908267229.0 #计算1gram词的概率 for key in self.word1_dict_count: self.word1_dict[key] = math.log(self.word1_dict_count[key]/self.all_freq) #读取2_gram_file，同时计算转移概率 dict_file = open(gram2_file, "r") for line in dict_file: sequence = line.strip() key = sequence.split('t')[0] value = float(sequence.split('t')[1]) first_word = key.split(" ")[0] second_word = key.split(" ")[1] self.word2_dict_count[key] = float(value) if self.word1_dict_count.has_key(first_word): self.word2_dict[key] = math.log(value/self.word1_dict_count[first_word]) #取自然对数 else: self.word2_dict[key] = self.word1_dict[second_word]#testif __name__=='__main__': myseg = DNASegment() myseg.initial_dict("count_1w.txt","count_2w.txt") sequence = "itisatest" seg_sequence = myseg.mp_seg(sequence) print "original sequence: " + sequence print "segment result: " + seg_sequence sequence = "tositdown" seg_sequence = myseg.mp_seg(sequence) print "original sequence: " + sequence 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
等