3.1.2　基于图的n-gram最大匹配

基于n-gram的评测算法中，较大的n-gram共现的机会很小，因此会对n实施限定，从而不能发现较长n-gram的匹配。GTM（Generative Topographic Mapping）算法利用图的最大匹配来计算共现的n-gram，不限制n的最大值。图3-2描述了GTM计算待评文档和参考文档n-gram共现的方法（Turian et al.，2003）。

图3-2　GTM计算最大匹配n-gram算法

设待评文档的内容为HCBAICDE，参考文档为ABCDEFBAIC，待评文档和参考文档有3处最大匹配的区域（图中灰色部分），长度分别为1，2，4。最终最大匹配长度（Maximum Matching Size，MMS）为所有最大匹配的平均长度：。待评文档T在给定参考文档R下的准确率（Precision）和召回率（Recall）分别定义为：

根据定义式可以计算出，上图中待评文档的准确率为4.6/8＝0.575，召回率为4.6/10＝0.46。

GTM算法中，关键问题是找到最大匹配区域MMS。MMS的计算步骤是：

首先在参考文档和待评文档构成的坐标栅格中查找相同的词，每个相同的位置称为一个hit（图中以黑点表示），但只有在行列中不重复的hit才能称为匹配，以防止重复计数（图中B就属于这种情况）。之后查找由平行于主对角线连续hit构成的区域。如果一个区域部分的和另一较大的区域冲突，则非冲突部分构成MMS（如图中面积为1和2的区域）。

据文献介绍，GTM算法比BLEU和NIST算法对机器翻译的评测更接近人工评测，但是计算MMS是个NP完备难题（NP completed），需要花费的代价很大。