中文分词：采用二元词图以及viterbi算法.docx

中文分词：采用二元词图以及viterbi算法说明： 本程序为中科院研究生院刘群老师的课程《计算语言学》的一个课程作业。所以，语料库来源于刘群老师，格式是1998年1月人民日报语料库经过编码后的格式。 语料库格式见/finallyliuyu/archive/2010/05/10/1732141.html正向最大匹配。关于二元词图以及Viterbi算法的入门性质介绍见二元词图，Viterbi算法入门简介??下面简单说一下：二元分词的思路。1.??建立词图：?词图上的节点为单字（如果此单字在字典中出现，它的初始概率就由语料库计算，否则赋极小值，1/N。N为训练语料库中所有词的总和，如果词重复出现，其重数也要计算在内）以及对于这个句子所有可能出现的词，如果这个词在语料库中出现过，我们就把它加到词图上去。?2.??如何找到一个句子的所有可能分词？采用如下方法：首先对单词词典建立一个一级Trie树，即把词语按首字相同进行分组。对于句子中的每个字，我们看看以此字开头的词语的最大长度为多少，然后在句子中以此字为起始节点，每次取两个字，三个字……到最大长度位置，并且看看这些生成的词在词典里是否出现，如果出现则加入词图。3.??为刚才生成的词图建立一个拓扑序（Topological order）。我的方法如下：从句首到句尾，每一个汉字表征一个hierachy.?将词图中的词归类到各个hierachy。?比如句子为”我是一个大好人大大的好人”。则词图中以”我”字结尾的词归到Hierachy0,以“是”字结尾的词归到Hierachy1……以此类推。4.??维特比算法实现为了简单起见，把双字词典也建立成了前缀Trie树。维特比算法属于动态规划范畴。一个问题能够用动态规划问题建模，它必须能够满足以下两个条件：子结构最优，子问题交叠。也就是说：1一个问题的最优解是由最优的子问题的最优解构成；2求解此问题最优解的方法过程，对于求解子问题也适用，也就是可递归性。建立一个变量??optimalCandidates，保存每个hierachy上的最优节点。再用上面的句子举例。“我是一个大好人大大的好人”。第一个好字，属于hierachy5，它的最优解可以由?optimalCandidates[0], optimalCandidates[1], optimalCandidates[2], optimalCandidates[3], optimalCandidates[4],中的某些来生成。对属于每个hierachy的词，按照它的长度，找到它的上一个hierachy。例如上面例子中的好字所属的hierchay中有一个词是“大好”。那么这个词就回溯到hierachy3，看看P（大好|optimalCandates[3]）的概率值。假设?“好”字hierachy还有一个词是“学习好”这个词可以回溯到hierachy2，但是不做处理，因为“学”字和”个”字,不相等。综上，就是我的二元分词法梗概。我的方法有一个缺陷，就是非常耗时。首先在建立字典上耗时，然后就是建立词图，需要不断查字典也比较耗时。1。首先建立词典。此处词典要理解为：对训练语料库中的词进行词频等信息的统计后形成的数据结构，和“新华字典”中的字典意义不一样。我的实现中建立了两个词典：“单词”词典统计每个词的出现次数，“双词”词典统计每两个词连续出现的次数(因为采用的是二元语法模型)。然后又分别对单词词典，双词词典形成一级Trie树，或者叫做“带首字索引”的字典。代码如下?从训练语料库建立“单词”词典#?-*-?coding:?cp936?-*-import?reimport?cPickle?as?mypickledef?datafile(name,sep=|):?for?line?in?file(name):?yield?line.split(sep)candidates=datafile(rC:\Python26\Bigramwordsegemtation\data\training.txt)p1=pile((^\s+|\s+$))p2=pile(\d)#p3=pile(\s+)mySingleWordDict={}#myDoubleWordDict={}for?m?in?candidates:?#singleline=[]?for?e?in?m:?e=p1.sub(,e)?if?p2.match(e):?#e=p3.sub(_,e)?mySingleWordDict[e]=float(mySingleWordDict.get(e,0)+1)?print?词为%s,个数为%s%(e,mySingleWordDict[e])N=sum(mySingleWordDict.itervalues())for?key?in?