论文部分内容阅读
摘要：句子匹配问题及其评价极具研究价值。本文针对存在天然空格分隔符的语言提出一种快速形式匹配算法，该算法将字符进行打包，充分利用单词中字符的内聚性，使源句子与目标句子在形式上进行快速匹配，有效提高匹配性能，缩短匹配时间。我们在双语句子数据集上进行了实验，并采用BLEU、ROUGE_L和ROUGE_S三种评价指标进行评价。实验结果表明快速形式匹配能够在缩短87.6%时间的前提下将传统Levenshtein匹配的平均BLEU4值提升12.5%，ROUGE_L的F值提升17.7%，ROUGE_S的F值提升16.0%；在进行句子匹配性能评价时，ROUGE_L能够以较短的时间获取较高的性能评估值，性能最优，BLEU性能次之，ROUGE_S性能第三。
关键词：快速形式匹配；BLEU4；ROUGE_L；ROUGE_S；评价
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）19-0162-07
Fast Formal Match and Performance Evaluation Analysis
YU Jun-ting1， LIU Wu-ying2， YI Mian-zhu1， HE Hong-ye1
（1. Luoyang University of Foreign Languages， Luoyang 471003， China；2 .Language Engineering and Computing Laboratory， Guangdong University of Foreign Studies， Guangzhou 510420， China）
Abstract： Sentence matching and its evaluation are worth well to research. This paper addresses the languages with natural space separators， proposes a fast formal match algorithm， which wraps characters and takes advantage of character cohesion in word. This algorithm can match the source sentence and target sentence fast at form， improve matching performance effectively and shorten matching time. We perform experiments in bilingual sentence data set and take the BLEU， ROUGE_L， ROUGE_S as evaluation metrics. And the results show that fast formal match can improve the average BLEU4 of traditional Levenshtein match by 12.5% with the 87.6% shortening of the runtime， and the improvement of ROUGE_L’s F value is 17.7% and that of ROUGE_S’s is 16.0%. At the evaluation of sentence matching， ROUGE_L can improve the performance evaluation with greatly reducing time costs， whose performance is the best. And that of BLEU is worse， the ROUGE_S’s is the third one.
Key words： Fast Formal Match； BLEU4； ROUGE_L； ROUGE_S； Evaluation
1 概述
句子匹配是指利用计算机算法从句子集合中自动找出与源句子形式、句法、语义相似的目标句子，通常包括浅层形式匹配、句法匹配和深层语义匹配等类型。浅层形式匹配往往不需要复杂的深层标注和手工对齐，计算效率比较高，因此具有更加广泛的适用性。迄今为止，人们提出了很多句子匹配算法。比较这些句子匹配算法的性能极具研究价值。目前主流的句子匹配评价方法就是将评价问题转化为相似度计算问题[1]，即针对同一个译文测试集，比较机器输出的候选译文与人工参考译文之间的相似度。例如基于译文中不同长度连续子串计算候选译文和参考译文之间相似度的BLEU评价算法[2]，基于最长公共子串计算译文相似度的ROUGE_L评价算法[3][4]以及基于不连续二元子串计算译文相似度的ROUGE_S评价算法[3][4]等。
在已有的相似度计算方法中，传统Levenshtein编辑距离能够语言无关地度量各种句子之间的相似度，广泛应用于各种句子匹配算法中。其中语言无关的优点是基于单个字符实现的，在大数据时代针对特定语言存在进一步提高计算效率的空间。为了应对大数据量、高速率信息处理的需求，我们针对存在天然空格分隔符的语言提出一种快速形式匹配算法，它能够充分利用单词中字符的内聚性提高句子匹配效率。
2 快速形式匹配
传统Levenshtein匹配算法是基于字符来计算两个字符串之间的编辑距离，即将两个字符串序列匹配时需要进行编辑操作（插入、删除和替换）的最少次数[5]。编辑距离越短，这两个字符串的相似度越高；编辑距离为零，意味着这两个字符串可以完全匹配。而且字符串A和字符串B之间的距离与字符串B和字符串A之间的距离相等。对于存在天然空格分隔符的语言（比如，英语、俄语），传统Levenshtein匹配打破了单词字符之间的内聚性，降低了匹配效率。快速形式匹配算法将字符进行打包，充分利用字符间的内聚性，使源句子与目标句子在形式上进行快速匹配，有效提高匹配性能，缩短匹配时间。 2.1基本流程
对于存在天然空格分隔符的语言，为了提高句子匹配性能，我们通过将字符打包，提出了快速形式匹配算法，基本流程框图如图1所示。
快速形式匹配基本流程图主要包括5个处理模块：LDCalculator、MinLD、SentenceRetriever、EvaluationCalculator和MaxEvaluation。LDCalculator模块接收来自语料库的两个源句子，并计算它们的Levenshtein距离。比如，LDCalculator分别接收句对， ， ... ， ，通过计算得到Levenshtein距离集合{d12， d13， ... ， d1N}。MinLD模块计算Levenshtein距离集合中的最小Levenshtein距离，通过检索语料库得到最小Levenshtein距离对应的源句子集合{ss11， ss12， ... ， ss1m}并将其送入SentenceRetriever模块。SentenceRetriever模块将这些源句子集合翻译成目标句子集合{ts11， ts12， ... ， ts1m}。EvaluationCalculator模块接收源句子ss1对应的目标句子ts1和目标句子集合{ts11， ts12， ... ， ts1m}，分别计算每组目标句对， ， ... ， 的性能评估值集合{EV11， EV12， ... ， EV41m}（本文中性能评估值分别为BLEU的BLEU4，ROUGE_L的F值和ROUGE_S的F值）。最后，MaxEvaluation计算性能评估值集合的最大值并输出最大的性能评估值（EV1）。同时，我们记录这一匹配过程的运行时间。这样，我们完成了源句子ss1的流程，语料库中剩余的其他源句子将运行和源句子ss1同样的过程。
传统Levenshtein匹配主要在LDCalculator模块上不同于快速形式匹配。传统Levenshtein匹配中LDCalculator模块的两个输入源句子在字符级进行计算，而快速形式匹配在单词级进行计算。其他部分的实现均相同，并且这两个算法所用到的语料库和其他实验条件也是相同的。
2.2算法
快速形式匹配算法的伪代码如表1所示，主要包含两个main函数：ldcalculate和evaluationcalculate。
当一个源语言文本输入时，ldcalculate函数将语料库中的源语言文本以"＼n"为标志切分成源语言句子；并且计算语料库中每两个源语言句子的Levenshtein距离，即计算句子i和句子j的Levenshtein距离的二维矩阵dij。
然后，通过MinLD模块得到最小的Levenshtein距离以及对应的目标语言句子集合，当源句子ss1对应的目标句子和目标句子集合输入，evaluationcalculate函数分别计算BLEU4值以及ROUGE_L和ROUGE_S的F值。
快速形式匹配算法很好地保持了单词中字符的内聚性，它的时空复杂度主要取决于二维矩阵dij的存储空间和ldcalculate函数的循环次数。理论上来说，快速形式匹配的存储空间分别正比于最长源语言句子中单词数目的平方，而传统Levenshtein匹配的存储空间正比于最长源语言句子中字符数目的平方。快速形式匹配的时间复杂度正比于语料库中源语言句子数目和最长源语言句子中单词数目乘积的平方，传统Levenshtein匹配的时间复杂度正比于语料库中源语言句子数目和最长源语言句子中字符数目乘积的平方。因此，快速形式匹配的空间复杂度为O（w2），传统Levenshtein匹配为O（c2）；快速形式匹配的时间复杂度为O（n2w2），传统Levenshtein匹配为O（n2c2）。其中，n为语料库中源语言句子的数目，w为最长源语言句子中单词数目，c为最长源语言句子中字符数目，w明显小于c。因此，快速形式匹配的时间复杂度和空间复杂度都要优于传统Levenshtein匹配。
2.3 计算粒度选择
为了选取合适的计算粒度，我们在具有4.00GB的内存和CPU为Intel Core i5-2520M的计算机上对快速形式匹配和传统Levenshtein匹配进行了实验比较，并分别采用BLEU、ROUGE_L、ROUGE_S三种指标进行评价，得到各自的性能评估值和运行时间。
首先采用BLEU对语料库中经过去重的俄汉双语对齐平行语料的快速形式匹配和传统Levenshtein匹配的性能进行评价。其中包含52892个俄汉句对，并对其按俄语句子长度进行排序。通过计算语料库中每两个俄语句子的Levenshtein距离得到52892组实验结果（包括最大BLEU4值和运行时间），为方便结果展示，将每1000个实验结果取平均值作为该组的最终结果，得到53组BLEU4和运行时间。同理，分别采用ROUGE_L和ROUGE_S对快速形式匹配和传统Levenshtein匹配的性能进行评价，分别得到53组F值和运行时间。三种评价指标的最终性能评估值（包括BLEU的BLEU4，ROUGE_L的F值以及ROUGE_S的F值） 如表2所示，表3为三种评价指标的运行时间（其中KFM表示快速形式匹配，TLM表示传统Levenshtein匹配）。
从表2中三种不同评价指标所得实验结果可以看出，快速形式匹配的性能明显优于传统Levenshtein匹配的性能；从具有最大性能评估值的输出相似句子可以看出，快速形式匹配的输出相似句子与源句子具有相似的形式架构，而传统Levenshtein匹配没有此相似度，原因是字符匹配破坏了词的内部结构。
表3运行时间数据中可以看出：1） 同样的实验条件下，传统Levenshtein匹配比快速形式匹配花费更多的时间，例如采用ROUGE_L进行评价时，传统Levenshtein匹配花费的总时间为227502936ms，快速形式匹配仅花费了28057625ms，是传统Levenshtein匹配花费时间的1/8；2） 快速形式匹配在整个实验过程中最长运行时间与最短运行时间的时间差远小于传统Levenshtein匹配的时间差；传统Levenshtein匹配的变化趋势比快速形式匹配快，当增加相同的字符时，传统Levenshtein匹配的运行时间增加比快速形式匹配大；3） 随着句子长度的增加，快速形式匹配的运行时间比传统Levenshtein匹配变化小，传统Levenshtein匹配更容易受到字符数目的影响。 综上所述，在选择计算粒度时，快速形式匹配更适用于存在天然空格分隔符的语言，它比传统Levenshtein匹配更能够提高句子匹配性能，充分利用单词中字符的内聚性，以最小的时间代价获得高效的性能评估值。传统Levenshtein匹配比快速形式匹配更容易受到字符数目的影响，将字符进行打包能够缩短运行时间，提高整体的句子匹配效率。
3 快速形式匹配性能评价分析
3.1 实验条件及语料
实验均在具有4.00GB的内存和CPU为Intel Core i5-2520M的计算机上运行。对快速形式匹配进行实验，分别采用BLEU、ROUGE_L、ROUGE_S三种评价指标对其句子匹配性能进行评价，得到各自的性能评估值和运行时间，并对实验结果进行分析比较。
双语句子数据集采用星汉句库，其中包含新闻领域的52892个俄汉双语对齐句对。这些句子按照俄语句子长度进行排序，并且已经被去重处理，形式上各不相同。
3.2评测
我们分别采用经典BLEU，ROUGE_L，ROUGE_S来评测快速形式匹配的运行结果。
由于BLEU要用到N-gram准确率pN，当参考译文句子过短，比如长度为3时，则4-gram的出现次数为零（即分母为零），为了解决这种零计数的问题，我们对N-gram准确率pN进行修正，如式（1）所示，采用加1平滑技术：分别给候选译文和参考译文中N-gram出现的数目加1[6]。
设定N-gram最大阶数为4，统一权值为wN=1/N。
ROUGE-L把最长公共子串 （Longest Common Substring， LCS）应用到评价算法中，同时避免了BLEU无法捕捉远距离不连续语言单元之间的关系的缺点，将召回率与准确率同时考虑进去，取其F值进行测度。设定参考译文中某个句子X的长度为m，候选译文中的相应句子Y的长度为n，则ROUGE-L的计算公式为：
其中，LCS（X，Y）为X和Y最长公共子串的长度，Flcs为准确率Plcs和召回率Rlcs的调和平均值，即为ROUGE_L的F值，把准确率和召回率同时考虑其中，避免了BLEU忽略召回率的缺点。
ROUGE_S利用Skip-bigram的匹配实现对远距离词汇关系的捕捉，每个句子长度为len的句子都有C（len，2）个skip-bigrams（即不连续的顺序二元组）。类似于ROUGE_L，ROUGE_S的计算公式如下：
其中，SKIP2（X，Y）为参考译文X和候选译文Y中能够匹配的顺序二元组的数目，C（m，2）和C（n，2）为组合公式，Fskip2为准确率P skip2和召回率R skip2的调和平均值，即为ROUGE_S的F值。
3.3 实验结果
由于BLEU、ROUGE_L和ROUGE_S均是基于字符串匹配的自动评价方法，而且是根据候选译文和参考译文的相似度给每一个候选译文分配一个分数。它们的操作原理区别于相似度计算方法的不同：BLEU基于连续N元子串的准确率计算相似度；ROUGE_L采用最长公共子串的F测度计算相似度；ROUGE_S采用不连续二元子串的F测度计算相似度，同时考虑了准确率和召回率的影响。因此本文通过对其最终得分的情况评价各自的性能优劣。由表1和表2可以看出，快速形式匹配能够以较小的时间代价获取较高的匹配性能，比传统Levenshtein匹配更适合俄语这种存在天然空格分隔符的语言，因此采用BLEU、ROUGE_L和ROUGE_S分别对快速形式匹配性能进行评价，所得不同句组的性能评估值和运行时间的变化曲线如图3所示。
从图3（a）中性能评估值的变化曲线可以看出，横坐标为句子分组序列号，纵坐标为每个句组的平均性能评估值：（1） BLEU、ROUGE_L和ROUGE_S的性能在整个变化区间上具有相同的变化趋势；（2） 同样的实验条件下，ROUGE_L的性能最好，BLEU次之，ROUGE_S第三，例如在第13句组中，BLEU4的值为0.31，ROUGE_L的F值为0.40，ROUGE_S的F值为0.19；（3） 整个数据集上，BLEU4的平均值为0.26，ROUGE_L的F均值为0.31，ROUGE_S的F均值为0.16，ROUGE_L的整体句子匹配性能最优。
图3（b）运行时间变化曲线可以看出，横坐标为句子分组序列号，纵坐标为每个句组运行的平均时间：（1） 将整个语料库中的52892个句对进行匹配并评价，BLEU花费总时间为28409492ms，ROUGE_L为28057625ms，ROUGE_S为31327056ms，ROUGE_L所花费的时间最少，BLEU次之，而ROUGE_S花费的时间要大于BLEU和ROUGE_L所花费的时间；（2） 整个实验过程的时间分为两部分：Levenshtein匹配时间和性能评价时间，三种评价指标采用的均是快速形式匹配算法，因此在Levenshtein匹配阶段不存在时间差异，而在评价过程中N元子串的查找和匹配阶段时间有不同，寻找最长公共子串的时间最短，效率最高，N元子串匹配次之，不连续顺序二元组的查找与匹配性能第三。
综合上述实验分析，在进行句子匹配性能评价时，ROUGE_L能够以较短的时间获取较高的性能评估值，性能最优，BLEU次之，ROUGE_S性能第三；通过寻找候选译文和参考译文的最长公共子串比较相似度这一方法具有更高的匹配效率，能够很好地适应大数据时代海量数据高效率检索的需求。
4 结束语
本文研究了快速形式匹配算法及其评价。对于存在天然空格分隔符的语言而言，快速形式匹配能够很好地利用单词字符之间的内聚性，提高句子匹配的效率。而且在评价算法匹配性能时，ROUGE_L能够以较小的时间代价获得较高的匹配性能。在大数据时代，快速形式匹配以及ROUGE_L具有很好的应用优势。 除了浅层形式匹配之外，在下一步的研究工作中我们将引入深层语义匹配，并对句子匹配评价指标的改进进行深入研究。
参考文献：
[1] 王博. 机器翻译系统的自动评价及诊断方法研究[D]. 哈尔滨工业大学，2010.
[2] Kishore Papineni， Salim Roukos， Todd Ward， et al. BLEU： a Method for Automatic Evaluation of Machine Translation. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics， Philadelphia， USA，2002：311-318.
[3] Lin C Y. ROUGE： A Package for Automatic Evaluation of Summaries. In Proceedings of the Workshop on Text Summarization Branches Out， post-conference workshop of ACL 2004， Barcelona， Spain，2004.
[4] Lin C Y， Och F J. Automatic Evaluation of Machine Translation Quality Using Longest Common Subsequence and Skip-Bigram Statistics. In Proceedings of ACL，2004.
[5] 米成刚，杨雅婷，周喜，等. 基于字符串相似度的维吾尔语中汉语借词识别[J]. 中文信息学报，2013，27（5）：173-179.
[6] Chin-Yew Lin， Franz Josef Och.ORANGE： a Method for Evaluating Automatic Evaluation Metrics for Machine Translation. Proceedings of the 20th International Conference on Computational Linguistics， Geneva， Switzerland，2004.
[7] Spence Green， Daniel Cer， Christopher D. Manning. Phrasal： A Toolkit for New Directions in Statistical Machine Translation. WMT2014， Baltimore， USA， 2014.
关键词：快速形式匹配；BLEU4；ROUGE_L；ROUGE_S；评价
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）19-0162-07
Fast Formal Match and Performance Evaluation Analysis
YU Jun-ting1， LIU Wu-ying2， YI Mian-zhu1， HE Hong-ye1
（1. Luoyang University of Foreign Languages， Luoyang 471003， China；2 .Language Engineering and Computing Laboratory， Guangdong University of Foreign Studies， Guangzhou 510420， China）
Abstract： Sentence matching and its evaluation are worth well to research. This paper addresses the languages with natural space separators， proposes a fast formal match algorithm， which wraps characters and takes advantage of character cohesion in word. This algorithm can match the source sentence and target sentence fast at form， improve matching performance effectively and shorten matching time. We perform experiments in bilingual sentence data set and take the BLEU， ROUGE_L， ROUGE_S as evaluation metrics. And the results show that fast formal match can improve the average BLEU4 of traditional Levenshtein match by 12.5% with the 87.6% shortening of the runtime， and the improvement of ROUGE_L’s F value is 17.7% and that of ROUGE_S’s is 16.0%. At the evaluation of sentence matching， ROUGE_L can improve the performance evaluation with greatly reducing time costs， whose performance is the best. And that of BLEU is worse， the ROUGE_S’s is the third one.
Key words： Fast Formal Match； BLEU4； ROUGE_L； ROUGE_S； Evaluation
1 概述
句子匹配是指利用计算机算法从句子集合中自动找出与源句子形式、句法、语义相似的目标句子，通常包括浅层形式匹配、句法匹配和深层语义匹配等类型。浅层形式匹配往往不需要复杂的深层标注和手工对齐，计算效率比较高，因此具有更加广泛的适用性。迄今为止，人们提出了很多句子匹配算法。比较这些句子匹配算法的性能极具研究价值。目前主流的句子匹配评价方法就是将评价问题转化为相似度计算问题[1]，即针对同一个译文测试集，比较机器输出的候选译文与人工参考译文之间的相似度。例如基于译文中不同长度连续子串计算候选译文和参考译文之间相似度的BLEU评价算法[2]，基于最长公共子串计算译文相似度的ROUGE_L评价算法[3][4]以及基于不连续二元子串计算译文相似度的ROUGE_S评价算法[3][4]等。
在已有的相似度计算方法中，传统Levenshtein编辑距离能够语言无关地度量各种句子之间的相似度，广泛应用于各种句子匹配算法中。其中语言无关的优点是基于单个字符实现的，在大数据时代针对特定语言存在进一步提高计算效率的空间。为了应对大数据量、高速率信息处理的需求，我们针对存在天然空格分隔符的语言提出一种快速形式匹配算法，它能够充分利用单词中字符的内聚性提高句子匹配效率。
2 快速形式匹配
传统Levenshtein匹配算法是基于字符来计算两个字符串之间的编辑距离，即将两个字符串序列匹配时需要进行编辑操作（插入、删除和替换）的最少次数[5]。编辑距离越短，这两个字符串的相似度越高；编辑距离为零，意味着这两个字符串可以完全匹配。而且字符串A和字符串B之间的距离与字符串B和字符串A之间的距离相等。对于存在天然空格分隔符的语言（比如，英语、俄语），传统Levenshtein匹配打破了单词字符之间的内聚性，降低了匹配效率。快速形式匹配算法将字符进行打包，充分利用字符间的内聚性，使源句子与目标句子在形式上进行快速匹配，有效提高匹配性能，缩短匹配时间。 2.1基本流程
对于存在天然空格分隔符的语言，为了提高句子匹配性能，我们通过将字符打包，提出了快速形式匹配算法，基本流程框图如图1所示。
快速形式匹配基本流程图主要包括5个处理模块：LDCalculator、MinLD、SentenceRetriever、EvaluationCalculator和MaxEvaluation。LDCalculator模块接收来自语料库的两个源句子，并计算它们的Levenshtein距离。比如，LDCalculator分别接收句对
传统Levenshtein匹配主要在LDCalculator模块上不同于快速形式匹配。传统Levenshtein匹配中LDCalculator模块的两个输入源句子在字符级进行计算，而快速形式匹配在单词级进行计算。其他部分的实现均相同，并且这两个算法所用到的语料库和其他实验条件也是相同的。
2.2算法
快速形式匹配算法的伪代码如表1所示，主要包含两个main函数：ldcalculate和evaluationcalculate。
当一个源语言文本输入时，ldcalculate函数将语料库中的源语言文本以"＼n"为标志切分成源语言句子；并且计算语料库中每两个源语言句子的Levenshtein距离，即计算句子i和句子j的Levenshtein距离的二维矩阵dij。
然后，通过MinLD模块得到最小的Levenshtein距离以及对应的目标语言句子集合，当源句子ss1对应的目标句子和目标句子集合输入，evaluationcalculate函数分别计算BLEU4值以及ROUGE_L和ROUGE_S的F值。
快速形式匹配算法很好地保持了单词中字符的内聚性，它的时空复杂度主要取决于二维矩阵dij的存储空间和ldcalculate函数的循环次数。理论上来说，快速形式匹配的存储空间分别正比于最长源语言句子中单词数目的平方，而传统Levenshtein匹配的存储空间正比于最长源语言句子中字符数目的平方。快速形式匹配的时间复杂度正比于语料库中源语言句子数目和最长源语言句子中单词数目乘积的平方，传统Levenshtein匹配的时间复杂度正比于语料库中源语言句子数目和最长源语言句子中字符数目乘积的平方。因此，快速形式匹配的空间复杂度为O（w2），传统Levenshtein匹配为O（c2）；快速形式匹配的时间复杂度为O（n2w2），传统Levenshtein匹配为O（n2c2）。其中，n为语料库中源语言句子的数目，w为最长源语言句子中单词数目，c为最长源语言句子中字符数目，w明显小于c。因此，快速形式匹配的时间复杂度和空间复杂度都要优于传统Levenshtein匹配。
2.3 计算粒度选择
为了选取合适的计算粒度，我们在具有4.00GB的内存和CPU为Intel Core i5-2520M的计算机上对快速形式匹配和传统Levenshtein匹配进行了实验比较，并分别采用BLEU、ROUGE_L、ROUGE_S三种指标进行评价，得到各自的性能评估值和运行时间。
首先采用BLEU对语料库中经过去重的俄汉双语对齐平行语料的快速形式匹配和传统Levenshtein匹配的性能进行评价。其中包含52892个俄汉句对，并对其按俄语句子长度进行排序。通过计算语料库中每两个俄语句子的Levenshtein距离得到52892组实验结果（包括最大BLEU4值和运行时间），为方便结果展示，将每1000个实验结果取平均值作为该组的最终结果，得到53组BLEU4和运行时间。同理，分别采用ROUGE_L和ROUGE_S对快速形式匹配和传统Levenshtein匹配的性能进行评价，分别得到53组F值和运行时间。三种评价指标的最终性能评估值（包括BLEU的BLEU4，ROUGE_L的F值以及ROUGE_S的F值） 如表2所示，表3为三种评价指标的运行时间（其中KFM表示快速形式匹配，TLM表示传统Levenshtein匹配）。
从表2中三种不同评价指标所得实验结果可以看出，快速形式匹配的性能明显优于传统Levenshtein匹配的性能；从具有最大性能评估值的输出相似句子可以看出，快速形式匹配的输出相似句子与源句子具有相似的形式架构，而传统Levenshtein匹配没有此相似度，原因是字符匹配破坏了词的内部结构。
表3运行时间数据中可以看出：1） 同样的实验条件下，传统Levenshtein匹配比快速形式匹配花费更多的时间，例如采用ROUGE_L进行评价时，传统Levenshtein匹配花费的总时间为227502936ms，快速形式匹配仅花费了28057625ms，是传统Levenshtein匹配花费时间的1/8；2） 快速形式匹配在整个实验过程中最长运行时间与最短运行时间的时间差远小于传统Levenshtein匹配的时间差；传统Levenshtein匹配的变化趋势比快速形式匹配快，当增加相同的字符时，传统Levenshtein匹配的运行时间增加比快速形式匹配大；3） 随着句子长度的增加，快速形式匹配的运行时间比传统Levenshtein匹配变化小，传统Levenshtein匹配更容易受到字符数目的影响。 综上所述，在选择计算粒度时，快速形式匹配更适用于存在天然空格分隔符的语言，它比传统Levenshtein匹配更能够提高句子匹配性能，充分利用单词中字符的内聚性，以最小的时间代价获得高效的性能评估值。传统Levenshtein匹配比快速形式匹配更容易受到字符数目的影响，将字符进行打包能够缩短运行时间，提高整体的句子匹配效率。
3 快速形式匹配性能评价分析
3.1 实验条件及语料
实验均在具有4.00GB的内存和CPU为Intel Core i5-2520M的计算机上运行。对快速形式匹配进行实验，分别采用BLEU、ROUGE_L、ROUGE_S三种评价指标对其句子匹配性能进行评价，得到各自的性能评估值和运行时间，并对实验结果进行分析比较。
双语句子数据集采用星汉句库，其中包含新闻领域的52892个俄汉双语对齐句对。这些句子按照俄语句子长度进行排序，并且已经被去重处理，形式上各不相同。
3.2评测
我们分别采用经典BLEU，ROUGE_L，ROUGE_S来评测快速形式匹配的运行结果。
由于BLEU要用到N-gram准确率pN，当参考译文句子过短，比如长度为3时，则4-gram的出现次数为零（即分母为零），为了解决这种零计数的问题，我们对N-gram准确率pN进行修正，如式（1）所示，采用加1平滑技术：分别给候选译文和参考译文中N-gram出现的数目加1[6]。
设定N-gram最大阶数为4，统一权值为wN=1/N。
ROUGE-L把最长公共子串 （Longest Common Substring， LCS）应用到评价算法中，同时避免了BLEU无法捕捉远距离不连续语言单元之间的关系的缺点，将召回率与准确率同时考虑进去，取其F值进行测度。设定参考译文中某个句子X的长度为m，候选译文中的相应句子Y的长度为n，则ROUGE-L的计算公式为：
其中，LCS（X，Y）为X和Y最长公共子串的长度，Flcs为准确率Plcs和召回率Rlcs的调和平均值，即为ROUGE_L的F值，把准确率和召回率同时考虑其中，避免了BLEU忽略召回率的缺点。
ROUGE_S利用Skip-bigram的匹配实现对远距离词汇关系的捕捉，每个句子长度为len的句子都有C（len，2）个skip-bigrams（即不连续的顺序二元组）。类似于ROUGE_L，ROUGE_S的计算公式如下：
其中，SKIP2（X，Y）为参考译文X和候选译文Y中能够匹配的顺序二元组的数目，C（m，2）和C（n，2）为组合公式，Fskip2为准确率P skip2和召回率R skip2的调和平均值，即为ROUGE_S的F值。
3.3 实验结果
由于BLEU、ROUGE_L和ROUGE_S均是基于字符串匹配的自动评价方法，而且是根据候选译文和参考译文的相似度给每一个候选译文分配一个分数。它们的操作原理区别于相似度计算方法的不同：BLEU基于连续N元子串的准确率计算相似度；ROUGE_L采用最长公共子串的F测度计算相似度；ROUGE_S采用不连续二元子串的F测度计算相似度，同时考虑了准确率和召回率的影响。因此本文通过对其最终得分的情况评价各自的性能优劣。由表1和表2可以看出，快速形式匹配能够以较小的时间代价获取较高的匹配性能，比传统Levenshtein匹配更适合俄语这种存在天然空格分隔符的语言，因此采用BLEU、ROUGE_L和ROUGE_S分别对快速形式匹配性能进行评价，所得不同句组的性能评估值和运行时间的变化曲线如图3所示。
从图3（a）中性能评估值的变化曲线可以看出，横坐标为句子分组序列号，纵坐标为每个句组的平均性能评估值：（1） BLEU、ROUGE_L和ROUGE_S的性能在整个变化区间上具有相同的变化趋势；（2） 同样的实验条件下，ROUGE_L的性能最好，BLEU次之，ROUGE_S第三，例如在第13句组中，BLEU4的值为0.31，ROUGE_L的F值为0.40，ROUGE_S的F值为0.19；（3） 整个数据集上，BLEU4的平均值为0.26，ROUGE_L的F均值为0.31，ROUGE_S的F均值为0.16，ROUGE_L的整体句子匹配性能最优。
图3（b）运行时间变化曲线可以看出，横坐标为句子分组序列号，纵坐标为每个句组运行的平均时间：（1） 将整个语料库中的52892个句对进行匹配并评价，BLEU花费总时间为28409492ms，ROUGE_L为28057625ms，ROUGE_S为31327056ms，ROUGE_L所花费的时间最少，BLEU次之，而ROUGE_S花费的时间要大于BLEU和ROUGE_L所花费的时间；（2） 整个实验过程的时间分为两部分：Levenshtein匹配时间和性能评价时间，三种评价指标采用的均是快速形式匹配算法，因此在Levenshtein匹配阶段不存在时间差异，而在评价过程中N元子串的查找和匹配阶段时间有不同，寻找最长公共子串的时间最短，效率最高，N元子串匹配次之，不连续顺序二元组的查找与匹配性能第三。
综合上述实验分析，在进行句子匹配性能评价时，ROUGE_L能够以较短的时间获取较高的性能评估值，性能最优，BLEU次之，ROUGE_S性能第三；通过寻找候选译文和参考译文的最长公共子串比较相似度这一方法具有更高的匹配效率，能够很好地适应大数据时代海量数据高效率检索的需求。
4 结束语
本文研究了快速形式匹配算法及其评价。对于存在天然空格分隔符的语言而言，快速形式匹配能够很好地利用单词字符之间的内聚性，提高句子匹配的效率。而且在评价算法匹配性能时，ROUGE_L能够以较小的时间代价获得较高的匹配性能。在大数据时代，快速形式匹配以及ROUGE_L具有很好的应用优势。 除了浅层形式匹配之外，在下一步的研究工作中我们将引入深层语义匹配，并对句子匹配评价指标的改进进行深入研究。
参考文献：
[1] 王博. 机器翻译系统的自动评价及诊断方法研究[D]. 哈尔滨工业大学，2010.
[2] Kishore Papineni， Salim Roukos， Todd Ward， et al. BLEU： a Method for Automatic Evaluation of Machine Translation. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics， Philadelphia， USA，2002：311-318.
[3] Lin C Y. ROUGE： A Package for Automatic Evaluation of Summaries. In Proceedings of the Workshop on Text Summarization Branches Out， post-conference workshop of ACL 2004， Barcelona， Spain，2004.
[4] Lin C Y， Och F J. Automatic Evaluation of Machine Translation Quality Using Longest Common Subsequence and Skip-Bigram Statistics. In Proceedings of ACL，2004.
[5] 米成刚，杨雅婷，周喜，等. 基于字符串相似度的维吾尔语中汉语借词识别[J]. 中文信息学报，2013，27（5）：173-179.
[6] Chin-Yew Lin， Franz Josef Och.ORANGE： a Method for Evaluating Automatic Evaluation Metrics for Machine Translation. Proceedings of the 20th International Conference on Computational Linguistics， Geneva， Switzerland，2004.
[7] Spence Green， Daniel Cer， Christopher D. Manning. Phrasal： A Toolkit for New Directions in Statistical Machine Translation. WMT2014， Baltimore， USA， 2014.