快速形式匹配及其性能評價分析

于俊婷　劉伍穎　易綿竹　何宏業(yè)

摘要：句子匹配問題及其評價極具研究價值。本文針對存在天然空格分隔符的語言提出一種快速形式匹配算法，該算法將字符進行打包，充分利用單詞中字符的內聚性，使源句子與目標句子在形式上進行快速匹配，有效提高匹配性能，縮短匹配時間。我們在雙語句子數(shù)據(jù)集上進行了實驗，并采用BLEU、ROUGE_L和ROUGE_S三種評價指標進行評價。實驗結果表明快速形式匹配能夠在縮短87.6%時間的前提下將傳統(tǒng)Levenshtein匹配的平均BLEU4值提升12.5%，ROUGE_L的F值提升17.7%，ROUGE_S的F值提升16.0%；在進行句子匹配性能評價時，ROUGE_L能夠以較短的時間獲取較高的性能評估值，性能最優(yōu)，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]，即針對同一個譯文測試集，比較機器輸出的候選譯文與人工參考譯文之間的相似度。例如基于譯文中不同長度連續(xù)子串計算候選譯文和參考譯文之間相似度的BLEU評價算法[2]，基于最長公共子串計算譯文相似度的ROUGE_L評價算法[3][4]以及基于不連續(xù)二元子串計算譯文相似度的ROUGE_S評價算法[3][4]等。

在已有的相似度計算方法中，傳統(tǒng)Levenshtein編輯距離能夠語言無關地度量各種句子之間的相似度，廣泛應用于各種句子匹配算法中。其中語言無關的優(yōu)點是基于單個字符實現(xiàn)的，在大數(shù)據(jù)時代針對特定語言存在進一步提高計算效率的空間。為了應對大數(shù)據(jù)量、高速率信息處理的需求，我們針對存在天然空格分隔符的語言提出一種快速形式匹配算法，它能夠充分利用單詞中字符的內聚性提高句子匹配效率。

2 快速形式匹配

傳統(tǒng)Levenshtein匹配算法是基于字符來計算兩個字符串之間的編輯距離，即將兩個字符串序列匹配時需要進行編輯操作（插入、刪除和替換）的最少次數(shù)[5]。編輯距離越短，這兩個字符串的相似度越高；編輯距離為零，意味著這兩個字符串可以完全匹配。而且字符串A和字符串B之間的距離與字符串B和字符串A之間的距離相等。對于存在天然空格分隔符的語言（比如，英語、俄語），傳統(tǒng)Levenshtein匹配打破了單詞字符之間的內聚性，降低了匹配效率?？焖傩问狡ヅ渌惴▽⒆址M行打包，充分利用字符間的內聚性，使源句子與目標句子在形式上進行快速匹配，有效提高匹配性能，縮短匹配時間。

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同樣的過程。

傳統(tǒng)Levenshtein匹配主要在LDCalculator模塊上不同于快速形式匹配。傳統(tǒng)Levenshtein匹配中LDCalculator模塊的兩個輸入源句子在字符級進行計算，而快速形式匹配在單詞級進行計算。其他部分的實現(xiàn)均相同，并且這兩個算法所用到的語料庫和其他實驗條件也是相同的。

2.2算法

快速形式匹配算法的偽代碼如表1所示，主要包含兩個main函數(shù)：ldcalculate和evaluationcalculate。

當一個源語言文本輸入時，ldcalculate函數(shù)將語料庫中的源語言文本以"＼n"為標志切分成源語言句子；并且計算語料庫中每兩個源語言句子的Levenshtein距離，即計算句子i和句子j的Levenshtein距離的二維矩陣dij。

然后，通過MinLD模塊得到最小的Levenshtein距離以及對應的目標語言句子集合，當源句子ss1對應的目標句子和目標句子集合輸入，evaluationcalculate函數(shù)分別計算BLEU4值以及ROUGE_L和ROUGE_S的F值。

快速形式匹配算法很好地保持了單詞中字符的內聚性，它的時空復雜度主要取決于二維矩陣dij的存儲空間和ldcalculate函數(shù)的循環(huán)次數(shù)。理論上來說，快速形式匹配的存儲空間分別正比于最長源語言句子中單詞數(shù)目的平方，而傳統(tǒng)Levenshtein匹配的存儲空間正比于最長源語言句子中字符數(shù)目的平方。快速形式匹配的時間復雜度正比于語料庫中源語言句子數(shù)目和最長源語言句子中單詞數(shù)目乘積的平方，傳統(tǒng)Levenshtein匹配的時間復雜度正比于語料庫中源語言句子數(shù)目和最長源語言句子中字符數(shù)目乘積的平方。因此，快速形式匹配的空間復雜度為O（w2），傳統(tǒng)Levenshtein匹配為O（c2）；快速形式匹配的時間復雜度為O（n2w2），傳統(tǒng)Levenshtein匹配為O（n2c2）。其中，n為語料庫中源語言句子的數(shù)目，w為最長源語言句子中單詞數(shù)目，c為最長源語言句子中字符數(shù)目，w明顯小于c。因此，快速形式匹配的時間復雜度和空間復雜度都要優(yōu)于傳統(tǒng)Levenshtein匹配。

2.3 計算粒度選擇

為了選取合適的計算粒度，我們在具有4.00GB的內存和CPU為Intel Core i5-2520M的計算機上對快速形式匹配和傳統(tǒng)Levenshtein匹配進行了實驗比較，并分別采用BLEU、ROUGE_L、ROUGE_S三種指標進行評價，得到各自的性能評估值和運行時間。

首先采用BLEU對語料庫中經(jīng)過去重的俄漢雙語對齊平行語料的快速形式匹配和傳統(tǒng)Levenshtein匹配的性能進行評價。其中包含52892個俄漢句對，并對其按俄語句子長度進行排序。通過計算語料庫中每兩個俄語句子的Levenshtein距離得到52892組實驗結果（包括最大BLEU4值和運行時間），為方便結果展示，將每1000個實驗結果取平均值作為該組的最終結果，得到53組BLEU4和運行時間。同理，分別采用ROUGE_L和ROUGE_S對快速形式匹配和傳統(tǒng)Levenshtein匹配的性能進行評價，分別得到53組F值和運行時間。三種評價指標的最終性能評估值（包括BLEU的BLEU4，ROUGE_L的F值以及ROUGE_S的F值） 如表2所示，表3為三種評價指標的運行時間（其中KFM表示快速形式匹配，TLM表示傳統(tǒng)Levenshtein匹配）。

從表2中三種不同評價指標所得實驗結果可以看出，快速形式匹配的性能明顯優(yōu)于傳統(tǒng)Levenshtein匹配的性能；從具有最大性能評估值的輸出相似句子可以看出，快速形式匹配的輸出相似句子與源句子具有相似的形式架構，而傳統(tǒng)Levenshtein匹配沒有此相似度，原因是字符匹配破壞了詞的內部結構。

表3運行時間數(shù)據(jù)中可以看出：1） 同樣的實驗條件下，傳統(tǒng)Levenshtein匹配比快速形式匹配花費更多的時間，例如采用ROUGE_L進行評價時，傳統(tǒng)Levenshtein匹配花費的總時間為227502936ms，快速形式匹配僅花費了28057625ms，是傳統(tǒng)Levenshtein匹配花費時間的1/8；2） 快速形式匹配在整個實驗過程中最長運行時間與最短運行時間的時間差遠小于傳統(tǒng)Levenshtein匹配的時間差；傳統(tǒng)Levenshtein匹配的變化趨勢比快速形式匹配快，當增加相同的字符時，傳統(tǒng)Levenshtein匹配的運行時間增加比快速形式匹配大；3） 隨著句子長度的增加，快速形式匹配的運行時間比傳統(tǒng)Levenshtein匹配變化小，傳統(tǒng)Levenshtein匹配更容易受到字符數(shù)目的影響。

綜上所述，在選擇計算粒度時，快速形式匹配更適用于存在天然空格分隔符的語言，它比傳統(tǒng)Levenshtein匹配更能夠提高句子匹配性能，充分利用單詞中字符的內聚性，以最小的時間代價獲得高效的性能評估值。傳統(tǒng)Levenshtein匹配比快速形式匹配更容易受到字符數(shù)目的影響，將字符進行打包能夠縮短運行時間，提高整體的句子匹配效率。

3 快速形式匹配性能評價分析

3.1 實驗條件及語料

實驗均在具有4.00GB的內存和CPU為Intel Core i5-2520M的計算機上運行。對快速形式匹配進行實驗，分別采用BLEU、ROUGE_L、ROUGE_S三種評價指標對其句子匹配性能進行評價，得到各自的性能評估值和運行時間，并對實驗結果進行分析比較。

雙語句子數(shù)據(jù)集采用星漢句庫，其中包含新聞領域的52892個俄漢雙語對齊句對。這些句子按照俄語句子長度進行排序，并且已經(jīng)被去重處理，形式上各不相同。

3.2評測

我們分別采用經(jīng)典BLEU，ROUGE_L，ROUGE_S來評測快速形式匹配的運行結果。

由于BLEU要用到N-gram準確率pN，當參考譯文句子過短，比如長度為3時，則4-gram的出現(xiàn)次數(shù)為零（即分母為零），為了解決這種零計數(shù)的問題，我們對N-gram準確率pN進行修正，如式（1）所示，采用加1平滑技術：分別給候選譯文和參考譯文中N-gram出現(xiàn)的數(shù)目加1[6]。

設定N-gram最大階數(shù)為4，統(tǒng)一權值為wN=1/N。

ROUGE-L把最長公共子串 （Longest Common Substring， LCS）應用到評價算法中，同時避免了BLEU無法捕捉遠距離不連續(xù)語言單元之間的關系的缺點，將召回率與準確率同時考慮進去，取其F值進行測度。設定參考譯文中某個句子X的長度為m，候選譯文中的相應句子Y的長度為n，則ROUGE-L的計算公式為：

其中，LCS（X，Y）為X和Y最長公共子串的長度，F(xiàn)lcs為準確率Plcs和召回率Rlcs的調和平均值，即為ROUGE_L的F值，把準確率和召回率同時考慮其中，避免了BLEU忽略召回率的缺點。

ROUGE_S利用Skip-bigram的匹配實現(xiàn)對遠距離詞匯關系的捕捉，每個句子長度為len的句子都有C（len，2）個skip-bigrams（即不連續(xù)的順序二元組）。類似于ROUGE_L，ROUGE_S的計算公式如下：

其中，SKIP2（X，Y）為參考譯文X和候選譯文Y中能夠匹配的順序二元組的數(shù)目，C（m，2）和C（n，2）為組合公式，F(xiàn)skip2為準確率P skip2和召回率R skip2的調和平均值，即為ROUGE_S的F值。

3.3 實驗結果

由于BLEU、ROUGE_L和ROUGE_S均是基于字符串匹配的自動評價方法，而且是根據(jù)候選譯文和參考譯文的相似度給每一個候選譯文分配一個分數(shù)。它們的操作原理區(qū)別于相似度計算方法的不同：BLEU基于連續(xù)N元子串的準確率計算相似度；ROUGE_L采用最長公共子串的F測度計算相似度；ROUGE_S采用不連續(xù)二元子串的F測度計算相似度，同時考慮了準確率和召回率的影響。因此本文通過對其最終得分的情況評價各自的性能優(yōu)劣。由表1和表2可以看出，快速形式匹配能夠以較小的時間代價獲取較高的匹配性能，比傳統(tǒng)Levenshtein匹配更適合俄語這種存在天然空格分隔符的語言，因此采用BLEU、ROUGE_L和ROUGE_S分別對快速形式匹配性能進行評價，所得不同句組的性能評估值和運行時間的變化曲線如圖3所示。

從圖3（a）中性能評估值的變化曲線可以看出，橫坐標為句子分組序列號，縱坐標為每個句組的平均性能評估值：（1） BLEU、ROUGE_L和ROUGE_S的性能在整個變化區(qū)間上具有相同的變化趨勢；（2） 同樣的實驗條件下，ROUGE_L的性能最好，BLEU次之，ROUGE_S第三，例如在第13句組中，BLEU4的值為0.31，ROUGE_L的F值為0.40，ROUGE_S的F值為0.19；（3） 整個數(shù)據(jù)集上，BLEU4的平均值為0.26，ROUGE_L的F均值為0.31，ROUGE_S的F均值為0.16，ROUGE_L的整體句子匹配性能最優(yōu)。

圖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元子串匹配次之，不連續(xù)順序二元組的查找與匹配性能第三。

綜合上述實驗分析，在進行句子匹配性能評價時，ROUGE_L能夠以較短的時間獲取較高的性能評估值，性能最優(yōu)，BLEU次之，ROUGE_S性能第三；通過尋找候選譯文和參考譯文的最長公共子串比較相似度這一方法具有更高的匹配效率，能夠很好地適應大數(shù)據(jù)時代海量數(shù)據(jù)高效率檢索的需求。

4 結束語

本文研究了快速形式匹配算法及其評價。對于存在天然空格分隔符的語言而言，快速形式匹配能夠很好地利用單詞字符之間的內聚性，提高句子匹配的效率。而且在評價算法匹配性能時，ROUGE_L能夠以較小的時間代價獲得較高的匹配性能。在大數(shù)據(jù)時代，快速形式匹配以及ROUGE_L具有很好的應用優(yōu)勢。

除了淺層形式匹配之外，在下一步的研究工作中我們將引入深層語義匹配，并對句子匹配評價指標的改進進行深入研究。

參考文獻：

[1] 王博. 機器翻譯系統(tǒng)的自動評價及診斷方法研究[D]. 哈爾濱工業(yè)大學，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.