MECAB的算法分析

1 关于Mecab的算法Mecab的算法，为最小开销法，该算法主要利用了单词的产生权重（语法对应为分词，但需要注意的一点是语法上不同类型的词语，即便是构成假名的长度一致，也会存在着差异）以及连接权重（语法对应为同音异意）这两个概念。算法逻辑如下。例： （kurumadematu）下面从左到右开始读取假名，从字典里面取出有记录的假名序列-注意，这里排除了首词为单假名的情况。每读到一个在字典中有对应项的假名序列的时，将该序列压入匹配堆栈的第一组（记录为a0）。上图为分解图，其中方框内的蓝色色的部分为该假名序列的产生权重（请注意，同样字长的假名序列的产生权重随着词性的不同也会有所不同），红色部分则为连接权重（请注意，该权重表述为当前假名序列到句首的连接可能度的总的权重值，在下文，如果没有做特别说明，则“连接权重”则表示的是总的连接度的权重）。而连接线上的蓝色部分，则为该文法段和它的左端文法段的连接权重。（从文法上，可以理解为某一个词和它的前置部分的权重关系，比如果该词位名词则前半部分可能为状语段。）由上图可知，（kurumadematu） 这一个序列，从第一个假名 （ku）开始，最长在 （de） 位置失去了在字典中的匹配记录。则按照匹配堆栈中的记录，有三种选择（堆栈中的记录为a02），分别为（kuruma） 名词 原型为 車 产生权重为2500 连接权重为 3200（kuru）段动词原型为 来 产生权重为450 连接权重为 3150（kuru）五段动词 原型为 繰 产生权重为3000 连接权重为 5700而这里的连接权重，由于该组匹配序列中的数据皆为头序列，因此，此处的连接权重为该数据（匹配项）出现在句首的可能度。在完成了“分词可能数据堆栈”的第一组数据的的可能匹配压栈处理后，接下来则按照第一步的步骤，对截取了第一组数据的假名序列之后的假名序列进行同样的匹配压栈操作。这里可以得到第二组的数据(记录为a12)。根据上图，这个第二组数据将是这样的（de） 格助词，在本例中用来表示手段 产生权重为0连接权重为4200(de) 助动词，产生权重为1300 连接权重为0 (made) 格助词，在本例中用来表示为时间上的终止，产生权重为0 连接权重为4550但正如图所示，这个产生并不是一对一的关系，而是一对多的关系。即使，从a00（(kuruma)）可以产生出a10（(de)）,a11（(de)）两种情况。而a01,a02则只能产生出a12（(made)）这一种可能。因此，完成了这一步之后，需要对所得到的第一组和第二组数据进行一次权重数值上的选取（因为第一组数据和第二组数据，其实是一个笛卡尔集的关系，这样重复下去，将会导致分析结果急剧膨胀。）。这个选取原则，从上图可以看出，是在a0和a1所形成的语法树中，针对于每个独立的叶子，仅保留权重值最小的支路。由于只选用最小权重的树，因此，在形成的文法分析树中，路径为“”且连接权重为7100的部分被删除了，对于“”而言，仅仅保留了连接权重为4500的文法分析树。 注：这里再来看连接权重的概念，该权重其实是由文法权重以及单词的产生权重所计算产生的。在本例子中，只运用到了右端文法段（可参见例子的对句末的权重数字）的连接权重，也即是说本例的扫描只满足“自左向右”的情况。但在Mecab字典里，该权重被分为了两个部分，一个是左连接权重，一个是右连接权重。这两个部分分别对应的是Mecab的安装目录下的“dic/ipadic”中的right-id.def和left-id.def两个文件。其中，left-id.def用来描述的是该数据左侧部分的解析情况，如对于a10（）而言，其左接部分a00（）的权重值应该为a10（）在left-id.def中的对应值。此外，本例中的图仅仅是Mecab的作者为了说明算法而使用的数字，并不是Mecab字典中的真实数字，这里请特别注意。另外，在Google所用的字典中，左右连接权重似乎被统一了起来，以左连接权重（使用左连接权重能更快的提高分析速度。）为主直接使用了连接权重的概念。请参见代码库下的“data/dictionary”。在基础词典满足一定的条件的情况下（具体将在下文做分析），采用“自左向右”（以右连接的数据为主）或者是采用“自由向左”（以左连接的数据为主）在算法的精度上都没有任何的区别。再回到例子本身。现在需要考虑的是第三组匹配数据的情况，也就是a2中的匹配情况。类似a1的情况，a2有两个数据。为了说明方便，命名为a20，和a21。分别是(matu)動詞五段（基本）产生权重1900 连接权重6900(matu)名詞产生权重2500 连接权重 7300a20：由于仅保留最小权重的路径关系，这里，仅仅保留了权重为6900的一条支路。a21由于仅保留最小权重的路径关系，这里，仅仅保留了权重为7300的一条支路。最后，我们将得到一个拥有两条分析路径的分析子树。在这里，在加入了对句末的权重判断之后，由于6900+5007300+960因此，我们再次删除一条路径。从而得到如下的结果：也就是：車待关于权重的使用Mecab的权重计算，在已经存在基础数据上，依赖于Viterbi算法。关于这个算法本身，我们不需要做太多的深究（当前阶段，可以认为这个算法的意思如下：假定系统从开始到完结存在着N个可能的步骤，每个步骤都有a种状态，在针对每个第M步骤的系统状态和M-1步骤都存在着可量化的关系的情况下，选取对系统而言消耗最小的状态a-min。并选择从0到N的所有步骤的a-min值的总和作为系统的定义）。只需要考虑权重的数字的使用就可以了-就是上例的所有图中，红色和蓝色部分的数字的计算。还是再来看上面的例子。 名词 原型为 車 产生权重为2500 连接权重为 3200段动词原型为 来 产生权重为 450 连接权重为 3150五段动词 原型为 繰 产生权重为 3000 连接权重为 5700正如上文所说的，连接权重连接权重的数字，其实是由文法权重和产生权重所计算出来的。而其中的计算关系，请参照下表。第一组数字 a0路径文法权重产生权重产生权重+文法权重（累积）产生权重+文法权重（单独）（名詞700250032003200（動詞変）270045031503150（動詞五段）2700300057005700第二组数字 a1路径文法权重产生权重产生权重+文法权重（累积）产生权重+文法权重（单独）（名詞）（格助詞）1000042001000（名詞）（動助詞）1300045001300（動詞変）（格助詞）1400045501400（動詞五段）（格助詞）1400071001400由上两表可见，作为判断依据的连接到每个节点的连接权重的权重数据，应该是每条支路的产生权重以及文法权重的累积。在此基础上，可以计算出第三组数字 a2的权重数据路径文法权重产生权重产生权重+文法权重（累积）产生权重+文法权重（单独）（名詞）（格助詞）+（動詞五段基本）800190069002700（名詞）（動助詞）+（動詞五段基本）1500190079003400（動詞変）（格助詞）+（動詞五段基本）800190072502700（名詞）（格助詞）+（名詞）600250073003100（名詞）（動助詞）+（名詞）1200250082003700（動詞変）（格助詞）+（名詞）600250076503100到这里，我们得到的两条分词支路如下：（名詞）（格助詞）+（動詞五段基本） 累积权重 6900（名詞）（格助詞）+（名詞）累积权重 7300最后，再加上文末的处理数据，则本次的计算分析便可完成。3 Mecab基础数据的产生需要指出的是，由于Mecab的分词算法的数学基础是Viterbi算法，因此，对于仅仅考虑概率以及权重的Viterbi而言，只要能够确保被分析数据中的每一个元素都来自于Mecab算法的基本词典（这里提下构建基本词典的数据总量。实际上，这个总量是相当的庞大的。在假定日文的词汇-标注为Q-总量为N的情况下，这个数据总量的理想极值应该是N的平方。也就是说，被采样的数据应该为或者接近于Q的自笛卡尔集。这个显然是不可完成的，但至少，在被分析的文本数据达到一定的数据量的情况下，我们可以得到Q的一个真子集。），则采用“自左向右”（以右连接的数据为主）或者是采用“自由向左”（以左连接的数据为主）在算法的精度上都没有任何的区别。这样的说可能有点笼统，下面来看Mecab词典的具体的产生算法。假定被分析的数据为一个长文W，则通过以下步骤，完成对带有权重的数据的计算。1 将W进行分词，得到词表word2 给word中的词加上词性属性，并对word按照词性进行划分。则得到若干词性集合M1,M2,M3.Mn。其中，下标n代表的是词性的分类标签。3 假定存在词a-word，且a-word属于词性集合Mn，则a-word的出现概率a-word-e可以通过下式计算：公式1 a-word-e = a-word在W中出现的总数/Mn集合中存在的元素在W中出现的总的次数4 假定在存在a-word的同时，存在词b-word，且a-word属于词性集合Mn，b-word属于词性集合Mm，且a-word在样本W中出现的次数为f，b-word在样本W中出现且出现在a-word的直接右侧的次数为x， 则a-word在b-word的左侧出现的概率a-b-f-e为：公式2a-b-f-e =x/f5 假定在存在a-word的同时，存在词b-word，且a-word属于词性集合Mn，b-word属于词性集合Mm，且a-word在样本W中出现的次数为f，b-word在样本W中出现且出现在a-word的直接左侧的次数为x， 则a-word在b-word的右侧出现的概率a-b-r-e为：公式3a-b-r-e =x/f6 到现在为止，我们已经获得了三个重要的概率，分别为a-word的出现概率a-word-e，a-word在b-word的左侧出现的概率a-b-f-e，以及在b-word右侧出现的概率a-b-r-e。在这里我们追加两个概念，即对所有的分析词的左侧出现的概率集F以及对所有的分析词在右侧出现的概率集R。7 在每个来自W的词都能保证在W中出现的位置不仅仅为W的文头或者文尾的情况下。集合F和集合R其实是可以互导的。8 从6得到的三个概率其实就足可以作为权重而使用了，但是，为了计算方便-我们可以看到，这些数据在绝对值上显得过小，不方便使用。我们可以采用如下的手段。8.1 对概率进行排序，选出最大的一个概率值max-e。8.2 对max-e取倒，并将该数的整数部分作为权重的第一个数据记号w-q0。8.3 根据概率数据序列（已排序）中的每个数据和max-e的数据的位置差距，分别计算出w-q的值。（从当前公布的文档来看，Mecab是采用该算法来进行从概率到权重的处理，Google不详。）下面用一个例子来说明以上算法（正常情况）。私中国時、中国語使。为了方便说明，在不考虑复合词的情况下，在这个例子里面，名词有如下（括号内为出现次数）：私（1）中国（2）時（1）語（1）则，对于名词“中国”，出现的概率为2/（）0.4 （根据公式1）而对于名词“語”而言，出现在中国右侧的概率则为 1/2 0.5 (根据公式3)正如我们上文所说的，我们完全可以不依据公式2，直接推导出名词“中国”在名词“語”左侧出现的