基于雙語(yǔ)URL匹配模式可信度的平行網(wǎng)頁(yè)識(shí)別研究

章成志,馬舒天,揭春雨,姚旭晨,3

(1. 南京理工大學(xué) 信息管理系，江蘇 南京，210094;2. 香港城市大學(xué) 翻譯及語(yǔ)言學(xué)系，香港;3. 百度在線網(wǎng)絡(luò)技術(shù)(北京)有限公司，北京 100085)

0 引言

平行語(yǔ)料庫(kù)是指兩種或多種語(yǔ)言在段落、句子甚至單詞短語(yǔ)層面上互為翻譯的語(yǔ)料。作為自然語(yǔ)言處理領(lǐng)域中的寶貴資源，平行語(yǔ)料在統(tǒng)計(jì)機(jī)器翻譯[1]和跨語(yǔ)言檢索[2]等任務(wù)中扮演著重要的角色。已有的平行語(yǔ)料庫(kù)，無論在語(yǔ)種數(shù)量、語(yǔ)料規(guī)模、質(zhì)量還是覆蓋領(lǐng)域等方面，都仍需不斷完善擴(kuò)充，以滿足實(shí)際需求。

過往的研究利用雙語(yǔ)或多語(yǔ)網(wǎng)站來獲取平行語(yǔ)料(包括雙語(yǔ)平行和雙語(yǔ)混合網(wǎng)頁(yè))，并搭建了一些雙語(yǔ)網(wǎng)頁(yè)獲取系統(tǒng)，如STRAND[3]、BITS[4]、PTMiner[5]、PTI[6]及WPDE[7]等。另外一種代表性方法則依據(jù)URL組成的模式，通過啟發(fā)式規(guī)則從雙語(yǔ)網(wǎng)站上自動(dòng)發(fā)現(xiàn)雙語(yǔ)網(wǎng)頁(yè)，相比手工制定啟發(fā)式規(guī)則，通過機(jī)器自動(dòng)發(fā)現(xiàn)規(guī)則，能在一定程度上減少計(jì)算資源的開銷[8-9]。

本文基于后一種方法，對(duì)雙語(yǔ)URL匹配模式探測(cè)、模式可信度計(jì)算及應(yīng)用等方面，進(jìn)行比較全面的設(shè)計(jì)和實(shí)驗(yàn)[8-10]。首先，計(jì)算雙語(yǔ)URL匹配模式的可信度；其次，在此基礎(chǔ)上提出四種雙語(yǔ)網(wǎng)頁(yè)識(shí)別方法；然后，利用搜索引擎以及少量的高可信度雙語(yǔ)URL匹配模式快速識(shí)別雙語(yǔ)網(wǎng)頁(yè)，以降低對(duì)匹配模式的過分依賴；最后，利用網(wǎng)頁(yè)鏈接與高可信度的URL匹配模式計(jì)算候選網(wǎng)頁(yè)對(duì)的雙語(yǔ)相似度，由此來過濾非雙語(yǔ)網(wǎng)頁(yè)對(duì)，以進(jìn)一步提高候選雙語(yǔ)網(wǎng)頁(yè)對(duì)的準(zhǔn)確率。通過一系列實(shí)驗(yàn)，我們驗(yàn)證了所提方法的有效性。

1 相關(guān)研究概述

STRAND[3]是最早用于識(shí)別雙語(yǔ)平行網(wǎng)頁(yè)的系統(tǒng)之一，該系統(tǒng)通過搜索引擎檢索指向不同語(yǔ)種版本鏈接的網(wǎng)頁(yè)，然后將文本語(yǔ)種比較、URL配對(duì)以及文本長(zhǎng)度作為判別特征，生成候選平行網(wǎng)頁(yè)對(duì)，最后利用網(wǎng)頁(yè)結(jié)構(gòu)進(jìn)行過濾。PTMiner[5]首先利用鏈接錨文本來識(shí)別候選雙語(yǔ)網(wǎng)站，通過搜索引擎得到這些網(wǎng)站下的網(wǎng)頁(yè)，并利用URL模式找出平行對(duì)，最后通過網(wǎng)頁(yè)內(nèi)外部特征進(jìn)行過濾。類似的挖掘系統(tǒng)還有BITS[4]、PTI[6]、WPDE[7]等。另外，平行網(wǎng)頁(yè)的識(shí)別方法也在不斷更新，例如通過DOM樹對(duì)齊模型來識(shí)別互譯文本和兩個(gè)平行DOM樹之間的鏈接[11]，利用HTML結(jié)構(gòu)實(shí)現(xiàn)平行網(wǎng)頁(yè)的遞歸訪問，使用URL模式優(yōu)化遍歷平行網(wǎng)站的拓?fù)漤樞?，來獲取平行網(wǎng)頁(yè)[12]。另外，網(wǎng)頁(yè)之間的鏈接關(guān)系也被用于計(jì)算網(wǎng)頁(yè)之間的相似程度，迭代挖掘出平行網(wǎng)頁(yè)[13]。

這些方法大多獨(dú)立于語(yǔ)言，具體步驟為: 抓取和識(shí)別候選雙語(yǔ)網(wǎng)站、提取候選平行網(wǎng)頁(yè)對(duì)，進(jìn)而驗(yàn)證。其中，平行網(wǎng)頁(yè)網(wǎng)址的先驗(yàn)知識(shí)常用于網(wǎng)頁(yè)抓取或過濾。已有研究主要依靠?jī)深愋畔慝@取平行網(wǎng)頁(yè): 一是單個(gè)網(wǎng)頁(yè)信息，包括網(wǎng)址和網(wǎng)頁(yè)內(nèi)容；二是多個(gè)網(wǎng)頁(yè)信息，主要是網(wǎng)頁(yè)之間的鏈接關(guān)系。也有很多研究者利用搜索引擎檢索表示語(yǔ)言類別的錨文本來定位候選雙語(yǔ)網(wǎng)站。此外，網(wǎng)址中是否含有預(yù)先定義的雙語(yǔ)URL模式也常被用來判斷候選平行網(wǎng)頁(yè)。然而，這些預(yù)定義的規(guī)則不可能涵蓋所有情況，很多網(wǎng)站甚至沒有任何關(guān)于語(yǔ)言類別的錨文本標(biāo)記。因此，我們?cè)噲D通過機(jī)器自動(dòng)發(fā)現(xiàn)規(guī)則，來降低基于雙語(yǔ)URL匹配模式的方法對(duì)外部先驗(yàn)知識(shí)的依賴性[8-9]。同時(shí)，我們還依據(jù)少量匹配模式，快速識(shí)別雙語(yǔ)網(wǎng)頁(yè)[10]。另外，為進(jìn)一步提高這些方法所識(shí)別出的候選雙語(yǔ)網(wǎng)頁(yè)對(duì)的準(zhǔn)確率，我們提出非雙語(yǔ)網(wǎng)頁(yè)對(duì)過濾算法。

2 研究總體框架

如圖1所示，雙語(yǔ)網(wǎng)頁(yè)在雙語(yǔ)網(wǎng)站上有多種出現(xiàn)模式，根據(jù)源語(yǔ)言與目標(biāo)語(yǔ)言網(wǎng)頁(yè)結(jié)構(gòu)對(duì)應(yīng)強(qiáng)度的不同，可以分為強(qiáng)、弱和無對(duì)應(yīng)關(guān)系的雙語(yǔ)網(wǎng)頁(yè)(深層網(wǎng)頁(yè))。我們根據(jù)網(wǎng)頁(yè)的URL結(jié)構(gòu)，計(jì)算雙語(yǔ)URL匹配模式可信度，并據(jù)此提出五種識(shí)別雙語(yǔ)網(wǎng)頁(yè)的算法，開發(fā)了相應(yīng)的雙語(yǔ)網(wǎng)頁(yè)獲取與評(píng)估系統(tǒng)Pupsniffer*https: //code.google.com/p/pupsniffer/。該系統(tǒng)基于先前工作[8]并對(duì)其算法進(jìn)行了優(yōu)化，是一個(gè)很有用的多語(yǔ)網(wǎng)頁(yè)自動(dòng)挖掘工具[9]。

圖1 候選雙語(yǔ)網(wǎng)站的網(wǎng)頁(yè)對(duì)應(yīng)結(jié)構(gòu)示意圖

如圖2所示，Pupsniffer系統(tǒng)分為三個(gè)模塊，第一個(gè)模塊是雙語(yǔ)網(wǎng)頁(yè)挖掘，根據(jù)所給的種子網(wǎng)站列表進(jìn)行網(wǎng)頁(yè)爬取，結(jié)合鏈接分析與雙語(yǔ)URL匹配模式，利用五個(gè)主要算法獲取雙語(yǔ)網(wǎng)頁(yè)，即: 基于模式局部可信度的雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法[8]和兩個(gè)優(yōu)化方法，分別是弱匹配模式救回算法和深層雙語(yǔ)網(wǎng)頁(yè)檢測(cè)算法，以及深層雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)增量算法[9]和僅考慮少量先驗(yàn)知識(shí)的雙語(yǔ)網(wǎng)頁(yè)獲取方法[10]。第二個(gè)模塊是非雙語(yǔ)網(wǎng)頁(yè)的過濾，利用網(wǎng)頁(yè)鏈接，以及雙語(yǔ)URL匹配模式進(jìn)行過濾(圖2⑥)。第三個(gè)模塊是候選雙語(yǔ)網(wǎng)頁(yè)測(cè)評(píng)，即對(duì)所得到的雙語(yǔ)網(wǎng)頁(yè)URL進(jìn)行隨機(jī)抽樣并人工測(cè)評(píng)，最后得到測(cè)評(píng)結(jié)果。

圖2 雙語(yǔ)網(wǎng)頁(yè)獲取與評(píng)估系統(tǒng)總體框架圖

3 雙語(yǔ)URL匹配模式的可信度計(jì)算方法

針對(duì)某個(gè)網(wǎng)站下采集得到的網(wǎng)頁(yè)，我們首先對(duì)其內(nèi)容進(jìn)行簡(jiǎn)單的語(yǔ)言識(shí)別，即: 網(wǎng)頁(yè)內(nèi)容中超過50%的字符為英文字母，則判斷該網(wǎng)頁(yè)為英文網(wǎng)頁(yè)，否則為中文網(wǎng)頁(yè)[8]。然后，我們對(duì)網(wǎng)頁(yè)URL進(jìn)行切分等預(yù)處理，得到兩個(gè)字符串單元集合，即網(wǎng)址路徑的單元集合和網(wǎng)址文件名的單元集合，接著分別對(duì)這兩個(gè)集合及其總集合進(jìn)行雙語(yǔ)URL匹配模式的識(shí)別[8]。

定義1(雙語(yǔ)URL匹配模式): 給定一個(gè)雙語(yǔ)網(wǎng)站的源語(yǔ)言與目標(biāo)語(yǔ)言網(wǎng)頁(yè)URL集合為U和U′，相應(yīng)的字符串單元集合為T和T′，若從一個(gè)候選雙語(yǔ)URL對(duì)π=〈u,u′〉∈U×U′中抽去一個(gè)單元對(duì)k=〈t,t′〉∈T×T′后，剩下的單元集合相同，即u-{t}=u′-{t′}，則該單元對(duì)k記為一個(gè)候選的雙語(yǔ)URL匹配模式。

相應(yīng)地，一個(gè)雙語(yǔ)URL匹配模式k=〈t,t′〉的得分計(jì)算可形式化為:

(1)

其中，u-{t}和u′-{t′}分別為從網(wǎng)址u和u′中抽去模式〈t,t′〉中的字串t和t′后剩下的單元集合。舉例來說，給出如下一對(duì)網(wǎng)址:

英文URL: http: //www.legco.gov.hk/yr99-00/english/fc/esc/minutes/es061099.htm

中文URL: http: //www.legco.gov.hk/yr99-00/chinese/fc/esc/minutes/es061099.htm

其中所含的“english”和“chinese”兩個(gè)字符串顯示出這兩個(gè)網(wǎng)址所對(duì)應(yīng)的語(yǔ)種及平行關(guān)系，根據(jù)以上定義，我們將“”這樣的字符串單元對(duì)選為一個(gè)候選雙語(yǔ)URL對(duì)的匹配模式，或稱匹配鍵(key)。遍歷一個(gè)雙語(yǔ)網(wǎng)站中所有的候選雙語(yǔ)URL對(duì)后，每個(gè)匹配鍵得到一個(gè)總得分，即其在該網(wǎng)站中可能匹配上的雙語(yǔ)URL對(duì)的總數(shù)。

定義2(雙語(yǔ)URL匹配模式的頻次): 雙語(yǔ)URL匹配模式k(簡(jiǎn)稱模式k)的頻次為遍歷給定網(wǎng)站w中所有的候選雙語(yǔ)URL對(duì)后模式k的總得分，即其在w中可能匹配上的雙語(yǔ)URL對(duì)的總對(duì)數(shù)，計(jì)算如式(2)所示。

(2)

定義3(雙語(yǔ)URL匹配模式的局部可信度): 模式k的局部可信度為給定網(wǎng)站w中k可能匹配上的雙語(yǔ)網(wǎng)頁(yè)數(shù)與w中URL總數(shù)的比值，計(jì)算如式(3)所示。

(3)

其中，N(k,w)為網(wǎng)站w中k可能匹配上的雙語(yǔ)網(wǎng)頁(yè)數(shù)，是雙語(yǔ)URL對(duì)數(shù)目的兩倍，即:N(k,w)=2*pπ∈U×U′(k,w)，|w|為網(wǎng)站w的網(wǎng)頁(yè)總數(shù)。

通常，在某一個(gè)網(wǎng)站上可信度高的雙語(yǔ)URL匹配模式，不一定在所有的網(wǎng)站上都具有較高的可信度，而在大多數(shù)網(wǎng)站上都出現(xiàn)的匹配模式一般來說其可信度都較高?；谶@個(gè)假設(shè)，我們給出雙語(yǔ)URL匹配模式的全局可信度概念。

定義4(雙語(yǔ)URL匹配模式的全局可信度): 對(duì)候選網(wǎng)站集合W中每個(gè)網(wǎng)站，將模式k可能匹配上的URL總數(shù)歸一化后，與k的局部可信度相乘，然后對(duì)所有乘積求和，該乘積和稱為模式k的全局可信度，計(jì)算如式(4)所示。

(4)

其中，N為候選網(wǎng)站集合W中所有網(wǎng)站網(wǎng)頁(yè)總數(shù)，wi為候選網(wǎng)站集合中第i個(gè)網(wǎng)站。由于N為常量值，不影響模式k全局可信度的排序結(jié)果，實(shí)驗(yàn)中無需加入計(jì)算。

定義5(網(wǎng)站的雙語(yǔ)可信度): 網(wǎng)站w的雙語(yǔ)可信度為其中所有雙語(yǔ)URL匹配模式的局部可信度最大值，計(jì)算如式(5)所示。

C(w)=maxkC(k,w)

(5)

4 基于雙語(yǔ)URL匹配模式可信度的雙語(yǔ)網(wǎng)頁(yè)識(shí)別方法

在雙語(yǔ)URL匹配模式可信度計(jì)算的基礎(chǔ)上，我們提出四種適用于不同場(chǎng)景的雙語(yǔ)網(wǎng)頁(yè)識(shí)別方法。

4.1 基于雙語(yǔ)URL匹配模式局部可信度的雙語(yǔ)網(wǎng)頁(yè)識(shí)別算法

基于雙語(yǔ)URL匹配模式局部可信度的雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法(圖2①)假設(shè)雙語(yǔ)網(wǎng)站中的雙語(yǔ)平行網(wǎng)頁(yè)對(duì)通常包含固定的URL匹配模式。該算法原理如下:

給定從雙語(yǔ)網(wǎng)站w采集到的所有URL地址，若其中的一對(duì)網(wǎng)址u與v只有一處不同，則此不同處為可能的雙語(yǔ)URL匹配模式。然后，我們計(jì)算網(wǎng)站w中的雙語(yǔ)匹配模式的局部可信度，給定閾值(實(shí)驗(yàn)中設(shè)為0.1)，得到雙語(yǔ)匹配模式局部可信度超過該閾值的候選雙語(yǔ)匹配模式，最后根據(jù)候選模式，得到候選雙語(yǔ)網(wǎng)頁(yè)[8]。

4.2 弱匹配模式救回算法

在初始算法中，設(shè)置局部可信度閾值顯然會(huì)過濾掉局部可信度低但全局可信度可能較高的雙語(yǔ)匹配模式及其對(duì)應(yīng)的雙語(yǔ)網(wǎng)頁(yè)。為此，我們提出兩種方法來解決這一問題。

首先，對(duì)于這樣的匹配模式，我們?cè)O(shè)定一個(gè)全局可信度閾值θ(實(shí)驗(yàn)中設(shè)為500)*我們給出θ=100時(shí)對(duì)應(yīng)的雙語(yǔ)匹配模式及其全局可信度: http: //mega.lt.cityu.edu.hk/～czhang22/pupsniffer-eval/Data/Pattern_Credibility_LargeThan100.txt，若其可信度不低于θ，則仍保留該匹配模式及其對(duì)應(yīng)的雙語(yǔ)網(wǎng)頁(yè)。

其次，對(duì)于兩種可信度都較低但當(dāng)前網(wǎng)站對(duì)應(yīng)域名的可信度較高*我們通過雙語(yǔ)URL匹配模式的可信度與域名進(jìn)行關(guān)聯(lián)統(tǒng)計(jì)，得到URL集合中每個(gè)域名的可信度。的情況，由于這種類型的網(wǎng)站可能包含大量的雙語(yǔ)URL對(duì)，例如“gov.hk”域名，我們降低局部可信度閾值，從而獲取更多可能的雙語(yǔ)網(wǎng)頁(yè)。

4.3 深層雙語(yǔ)網(wǎng)頁(yè)檢測(cè)算法

有些網(wǎng)頁(yè)只有通過數(shù)據(jù)庫(kù)檢索才能臨時(shí)生成，這類網(wǎng)頁(yè)稱為深層網(wǎng)頁(yè)*https: //en.wikipedia.org/wiki/Deep_web_%28search%29。在雙語(yǔ)網(wǎng)站中，深層網(wǎng)頁(yè)包括如下幾種情況: (1)全子樹深層網(wǎng)頁(yè)，即網(wǎng)站的單語(yǔ)子目錄無法被抓?。?2)部分子樹深層網(wǎng)頁(yè)，即部分子樹對(duì)應(yīng)網(wǎng)頁(yè)不能被抓?。?3)部分節(jié)點(diǎn)深層網(wǎng)頁(yè)，即雙語(yǔ)網(wǎng)站的某些網(wǎng)頁(yè)無法被抓取，尤其是動(dòng)態(tài)創(chuàng)建的網(wǎng)頁(yè)。

我們利用全局可信度高的雙語(yǔ)URL匹配模式，生成深層網(wǎng)頁(yè)URL對(duì)應(yīng)的另一語(yǔ)種的網(wǎng)頁(yè)URL。實(shí)驗(yàn)中我們?nèi)∪挚尚哦惹?0位的雙語(yǔ)匹配模式進(jìn)行深層雙語(yǔ)網(wǎng)頁(yè)檢測(cè)。例如，中文網(wǎng)頁(yè)http: //www.fehd.gov.hk/tc_chi/LLB_web/cagenda_20070904.htm所對(duì)應(yīng)的英文網(wǎng)頁(yè)如果爬蟲爬不到，則選擇全局可信度高的雙語(yǔ)匹配模式“”，用“english”替換“tc_chi”來生成英文URL*對(duì)應(yīng)英文URL為: http: //www.fehd.gov.hk/english/LLB_web/cagenda_20070904.htm，目前該網(wǎng)頁(yè)已失效。，然后用超文本傳輸協(xié)議檢查生成的URL是否有效，若有效，則收集到候選雙語(yǔ)網(wǎng)頁(yè)對(duì)中。目前，大多數(shù)雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)方法都是基于網(wǎng)頁(yè)結(jié)構(gòu)和內(nèi)容的相似度計(jì)算，而沒有事先獲得候選URL對(duì)，因此都無法發(fā)現(xiàn)深層雙語(yǔ)網(wǎng)頁(yè)。我們把深層雙語(yǔ)網(wǎng)頁(yè)檢測(cè)整合到雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)方法中，可挖掘出更多高可信度的雙語(yǔ)網(wǎng)頁(yè)。

4.4 深層雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)增量算法

雙語(yǔ)網(wǎng)站往往與其他的雙語(yǔ)網(wǎng)站存在鏈接關(guān)系。因此，如果給定雙語(yǔ)網(wǎng)站列表，可以通過解析網(wǎng)站中的網(wǎng)頁(yè)來采集外部網(wǎng)站，從而發(fā)現(xiàn)更多的雙語(yǔ)網(wǎng)站?；谠撓敕?，我們利用鏈接分析，結(jié)合網(wǎng)站可信度獲得更多的候選雙語(yǔ)網(wǎng)頁(yè)。

定義6(網(wǎng)站的鏈出數(shù)): 給定種子網(wǎng)站集合Wseed={w1，w2，...，wi，…，wN}，其中網(wǎng)站wi的鏈出數(shù)是指從網(wǎng)站wi鏈接到Wseed中其他網(wǎng)站的數(shù)量總和，記為L(zhǎng)inkout(wi)。

定義7(網(wǎng)站的權(quán)威度): 網(wǎng)站wi的權(quán)威度為其PageRank值[14]，記作PR(wi)。

定義8(考慮可信度的網(wǎng)站權(quán)威度): 考慮可信度的網(wǎng)站wi權(quán)威度為wi可信度與其PageRank值的乘積，即加權(quán)的(weighted)PR值，記作WPR(wi)，計(jì)算公式如式(6)所示。

WPR(wi)=C(wi)PR(wi)

(6)

為了減少系統(tǒng)開銷，Linkout(wi)和PR(wi)的計(jì)算僅依據(jù)種子網(wǎng)站之間的鏈接關(guān)系。根據(jù)定義6～8，網(wǎng)站wi包含Linkout(wi)、PR(wi)和WPR(wi)三個(gè)量值。依此，我們分別使用這三個(gè)指標(biāo)來度量一個(gè)相關(guān)外部網(wǎng)站的可信度，即其各指標(biāo)的總和: ∑Linkout、∑PR和∑WPR值。

使用這些指標(biāo)的雙語(yǔ)網(wǎng)頁(yè)獲取增量算法的具體步驟如表1所示。在每次迭代中，計(jì)算相關(guān)參數(shù)并得到新的候選種子網(wǎng)站及其網(wǎng)頁(yè)。其中，預(yù)設(shè)的從外部網(wǎng)站選取候選網(wǎng)站的個(gè)數(shù)K可以換成一個(gè)適當(dāng)?shù)谋壤担驗(yàn)樗缅噙x指標(biāo)的一個(gè)經(jīng)驗(yàn)閾值。在我們的實(shí)驗(yàn)中，為了簡(jiǎn)化處理過程，該算法一次運(yùn)行中同時(shí)計(jì)算三個(gè)遴選指標(biāo)并輸出結(jié)果，K設(shè)定為500，迭代次數(shù)設(shè)定為1次。

我們邀請(qǐng)了兩位碩士研究生分別評(píng)估這樣獲得的候選相關(guān)雙語(yǔ)網(wǎng)站的前500個(gè)。依照上述三個(gè)指標(biāo)，圖3顯示所識(shí)別的前N個(gè)候選網(wǎng)站中真正雙語(yǔ)網(wǎng)站的數(shù)量走勢(shì)，圖4顯示所識(shí)別的雙語(yǔ)網(wǎng)站的正確率?？梢钥闯?，∑WPR指標(biāo)優(yōu)于其他兩種指標(biāo)，在前500個(gè)候選網(wǎng)站中，識(shí)別出為真雙語(yǔ)網(wǎng)站的準(zhǔn)確率接近50%。

表1 深層雙語(yǔ)網(wǎng)站發(fā)現(xiàn)增量算法描述

圖3 前N個(gè)候選網(wǎng)站中真正雙語(yǔ)網(wǎng)站的數(shù)量走勢(shì)

圖4 前N個(gè)候選雙語(yǔ)網(wǎng)站的正確率

4.5 基于少量先驗(yàn)知識(shí)的雙語(yǔ)網(wǎng)頁(yè)獲取算法

為降低對(duì)初始種子網(wǎng)站和雙語(yǔ)URL匹配模式的過度依賴，我們利用搜索引擎的優(yōu)勢(shì)，僅依據(jù)少量的高可信度雙語(yǔ)URL匹配模式，快速識(shí)別雙語(yǔ)網(wǎng)頁(yè)[10]，具體步驟如下:

(1) 獲取雙語(yǔ)URL匹配模式中目標(biāo)語(yǔ)言的標(biāo)識(shí)符

URL中標(biāo)識(shí)語(yǔ)種類型的字符串通常為該語(yǔ)言的英文單詞或縮寫，例如英文網(wǎng)頁(yè)URL中可能包含“english”“eng”“en”等字符串。為此，我們可從雙語(yǔ)URL匹配模式中獲取目標(biāo)語(yǔ)言的標(biāo)識(shí)符。根據(jù)雙語(yǔ)匹配模式及其全局可信度的計(jì)算結(jié)果，得到可信度排名靠前的雙語(yǔ)URL模式，如“”“” “”等，其英文標(biāo)識(shí)分別為“en”“eng”“english”。

(2) 依據(jù)搜索引擎快速獲取候選雙語(yǔ)種子站點(diǎn)

通過搜索引擎的搜索規(guī)則，構(gòu)造查詢式，我們可以快速獲取候選的雙語(yǔ)種子站點(diǎn)。例如: 通過“site:”限定方式，可將搜索范圍限定在香港政府(gov.hk)、教育(edu.hk)等類型的網(wǎng)站；通過“inurl:”來保證URL中含有“en”“eng”“english”等語(yǔ)言標(biāo)識(shí)符；此外通過“filetype:”限定URL對(duì)應(yīng)的文件類型。通過查詢式“inurl: en site: gov.hk filetype: html”，我們能在Google上快速得到香港政府相關(guān)網(wǎng)頁(yè)，在此基礎(chǔ)上得到候選雙語(yǔ)種子站點(diǎn)列表。

(3) 獲取候選雙語(yǔ)網(wǎng)頁(yè)

依據(jù)雙語(yǔ)匹配模式的全局可信度計(jì)算結(jié)果，我們得到與目標(biāo)語(yǔ)言標(biāo)識(shí)對(duì)應(yīng)的排名前N(實(shí)驗(yàn)中設(shè)為5)的雙語(yǔ)URL匹配模式。對(duì)候選雙語(yǔ)網(wǎng)站的目標(biāo)語(yǔ)言網(wǎng)址，按照可信度由高到低的順序，將目標(biāo)語(yǔ)言標(biāo)識(shí)符替換為源語(yǔ)言標(biāo)識(shí)符，從而得到候選的源語(yǔ)言網(wǎng)頁(yè)URL。根據(jù)HTTP協(xié)議判斷源語(yǔ)言網(wǎng)頁(yè)URL是否有效，將有效的URL對(duì)作為候選的雙語(yǔ)網(wǎng)頁(yè)URL。

5 基于網(wǎng)頁(yè)鏈接與雙語(yǔ)URL匹配模式的非雙語(yǔ)網(wǎng)頁(yè)對(duì)過濾方法

一對(duì)平行雙語(yǔ)網(wǎng)頁(yè)所具有的網(wǎng)頁(yè)鏈接往往互為平行網(wǎng)頁(yè)。我們還可以根據(jù)識(shí)別出的候選平行網(wǎng)頁(yè)對(duì)中各自的網(wǎng)頁(yè)鏈接，借助少量高可信度雙語(yǔ)URL匹配模式計(jì)算候選網(wǎng)頁(yè)對(duì)中源語(yǔ)言與目標(biāo)語(yǔ)言網(wǎng)頁(yè)的雙語(yǔ)相似度。然后，通過閾值進(jìn)一步從候選網(wǎng)頁(yè)對(duì)中過濾出非雙語(yǔ)網(wǎng)頁(yè)，以提高準(zhǔn)確率。

定義9(候選雙語(yǔ)網(wǎng)頁(yè)對(duì)的雙語(yǔ)相似度): 給定一對(duì)候選雙語(yǔ)網(wǎng)頁(yè)對(duì)(目標(biāo)語(yǔ)言網(wǎng)頁(yè)wT和源語(yǔ)言網(wǎng)頁(yè)wS)，其雙語(yǔ)相似度定義為它們的網(wǎng)頁(yè)鏈接(分別為L(zhǎng)T和LS)中共同網(wǎng)頁(yè)的相似度與利用雙語(yǔ)URL匹配模式匹配上的雙語(yǔ)網(wǎng)頁(yè)相似度之和:

(7)

其中，α是兩者的相對(duì)權(quán)重(實(shí)驗(yàn)中，設(shè)為0.5)，Sim_Same(LT,LS)為L(zhǎng)T和LS中共同網(wǎng)頁(yè)對(duì)的總網(wǎng)頁(yè)數(shù)與LT和LS總網(wǎng)頁(yè)數(shù)的比值:

(8)

對(duì)LT和LS中所有能夠利用雙語(yǔ)URL匹配模式匹配得上的雙語(yǔ)網(wǎng)頁(yè)對(duì)π，將其匹配模式k匹配上的URL總數(shù)N(k,π)=2×p(k,LT∪LS)與k的全局可信度C(k)相乘，將所有這樣的乘積和與總網(wǎng)頁(yè)數(shù)的比值記作:

(9)

這個(gè)基于雙語(yǔ)相似度的非雙語(yǔ)網(wǎng)頁(yè)對(duì)過濾算法適用于以上所有的雙語(yǔ)網(wǎng)頁(yè)對(duì)發(fā)現(xiàn)算法的輸出。

6 結(jié)果評(píng)估與分析

我們對(duì)上面提出的四種雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)方法、基于少量先驗(yàn)知識(shí)的雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法以及基于網(wǎng)頁(yè)鏈接及匹配模式的非雙語(yǔ)網(wǎng)頁(yè)對(duì)過濾方法，進(jìn)行一系列實(shí)驗(yàn)，本節(jié)報(bào)告試驗(yàn)結(jié)果，并進(jìn)行評(píng)估與分析。

6.1 基于四種不同雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)

實(shí)驗(yàn)中，我們基于12 800個(gè)種子網(wǎng)站分別對(duì)以上四種方法所發(fā)現(xiàn)的雙語(yǔ)網(wǎng)頁(yè)進(jìn)行質(zhì)量評(píng)估。這些種子網(wǎng)站來源于香港，從如下兩個(gè)途徑獲得: 一個(gè)是香港網(wǎng)站目錄*http: //www.852.com/，截止2010年7月17日，該目錄列出了9 922個(gè)網(wǎng)站；另一個(gè)是香港萬維網(wǎng)數(shù)據(jù)庫(kù)*http: //www.cuhk.edu.hk/hkwww.htm，注: 該網(wǎng)頁(yè)現(xiàn)已失效。中的4 230個(gè)網(wǎng)站列表。刪除無效網(wǎng)站后，共獲得大約12 800個(gè)候選種子網(wǎng)站*http: //mega.lt.cityu.edu.hk/～czhang22/pupsniffer-eval/Data/All_Seed_Websites_List.txt。

我們開發(fā)了雙語(yǔ)網(wǎng)頁(yè)的質(zhì)量評(píng)估網(wǎng)站*http: //mega.lt.cityu.edu.hk/～czhang22/pupsniffer-eval/，通過隨機(jī)抽樣方式對(duì)雙語(yǔ)網(wǎng)頁(yè)識(shí)別方法進(jìn)行評(píng)估。我們邀請(qǐng)了五人(一位博士和四位碩士生)參加評(píng)估。評(píng)估人員需要判斷候選雙語(yǔ)網(wǎng)頁(yè)對(duì)是否為真實(shí)的雙語(yǔ)網(wǎng)頁(yè)對(duì)。

經(jīng)過實(shí)驗(yàn)，我們共發(fā)現(xiàn)348 058對(duì)候選雙語(yǔ)網(wǎng)頁(yè)。表2給出了不同方法的統(tǒng)計(jì)數(shù)據(jù)和正確率。可以看出，四個(gè)方法的整體正確率為94.72%，基于雙語(yǔ)URL匹配模式局部可信度的雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法的正確率為94.06%，利用弱匹配模式救回算法、深層雙語(yǔ)網(wǎng)頁(yè)檢測(cè)算法以及深層雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)增量算法，能額外多發(fā)現(xiàn)21.82%的高可信度雙語(yǔ)網(wǎng)頁(yè)。

我們也分析了實(shí)驗(yàn)結(jié)果中910個(gè)的虛假雙語(yǔ)URL對(duì)，將它們分為五類，其中: “語(yǔ)言識(shí)別錯(cuò)誤”，是由于Pupsniffer語(yǔ)言識(shí)別模塊存在識(shí)別結(jié)果錯(cuò)誤而造成的；“無效URL”，是指由于網(wǎng)頁(yè)采集時(shí)網(wǎng)站正在維護(hù)或者它們本身就不存在，造成源語(yǔ)言或目標(biāo)語(yǔ)言URL無效；“只有單語(yǔ)”，是指URL對(duì)所對(duì)應(yīng)的候選雙語(yǔ)網(wǎng)頁(yè)實(shí)際上都是同一語(yǔ)種網(wǎng)頁(yè)；“內(nèi)容提取錯(cuò)誤”，是指有些候選網(wǎng)頁(yè)是非純文本文件；“虛假雙語(yǔ)文本”，是指從網(wǎng)頁(yè)內(nèi)容來看候選雙語(yǔ)網(wǎng)頁(yè)不是真實(shí)的雙語(yǔ)網(wǎng)頁(yè)。經(jīng)過統(tǒng)計(jì)發(fā)現(xiàn)，約80%的虛假雙語(yǔ)URL對(duì)是由于語(yǔ)言識(shí)別錯(cuò)誤造成的，因此從理論上來說，如果能夠解決這種類型的錯(cuò)誤，識(shí)別出的雙語(yǔ)網(wǎng)頁(yè)正確率將提高至98.79%。

表2 不同雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法的質(zhì)量評(píng)估

6.2 基于少量先驗(yàn)知識(shí)的雙語(yǔ)網(wǎng)頁(yè)獲取

我們依據(jù)目標(biāo)語(yǔ)言的標(biāo)識(shí)符(如“english”“eng”“en”等)及其對(duì)應(yīng)全局可信度排名前五的雙語(yǔ)匹配模式，利用Google搜索引擎檢索到88 915對(duì)中英文URL*檢索日期為2014年2月。。同樣，我們通過隨機(jī)抽樣來評(píng)估所發(fā)現(xiàn)的雙語(yǔ)網(wǎng)頁(yè)，結(jié)果如表3所示: 4 460個(gè)中英文URL對(duì)中，有4 051對(duì)為真實(shí)的中英文雙語(yǔ)網(wǎng)頁(yè)對(duì)，雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)的正確率為90.83%。雖然該方法相比于[8-9]的結(jié)果較低，但該方法僅考慮少量先驗(yàn)知識(shí)、以較少的系統(tǒng)開銷即可發(fā)現(xiàn)一定規(guī)模的雙語(yǔ)網(wǎng)頁(yè)。

表3 不同雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)方法的結(jié)果比較

對(duì)虛假雙語(yǔ)URL對(duì)的錯(cuò)誤進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)虛假雙語(yǔ)URL對(duì)的錯(cuò)誤主要集中在“只有單語(yǔ)”與“內(nèi)容提取錯(cuò)誤”這兩種類型。

6.3 非雙語(yǔ)網(wǎng)頁(yè)過濾

基于網(wǎng)頁(yè)鏈接與雙語(yǔ)URL匹配模式的雙語(yǔ)網(wǎng)頁(yè)過濾方法，可以對(duì)以上各雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)算法的候選結(jié)果進(jìn)行進(jìn)一步過濾。本節(jié)僅報(bào)告針對(duì)7.2節(jié)中的候選雙語(yǔ)網(wǎng)頁(yè)對(duì)所進(jìn)行過濾的結(jié)果。根據(jù)該節(jié)得到的候選網(wǎng)頁(yè)對(duì)，我們爬取到69 847*有部分網(wǎng)頁(yè)對(duì)未爬取到，原因是其中一個(gè)網(wǎng)頁(yè)失效，或兩個(gè)網(wǎng)頁(yè)均失效，爬蟲爬取時(shí)無反應(yīng)。對(duì)有效的鏈接網(wǎng)址*網(wǎng)頁(yè)抓取日期為2016年9月。。在進(jìn)行高可信度雙語(yǔ)URL模式匹配時(shí)，我們首先排除雙語(yǔ)匹配模式中非中文英文對(duì)的模式，然后選擇了全局可信度排名前30的雙語(yǔ)匹配模式來進(jìn)行雙語(yǔ)候選網(wǎng)頁(yè)對(duì)頁(yè)面鏈接的匹配。

在計(jì)算候選雙語(yǔ)網(wǎng)頁(yè)對(duì)雙語(yǔ)相似度時(shí)，為了降低計(jì)算復(fù)雜度，我們?cè)趯?shí)驗(yàn)中沒有考慮各個(gè)模式的可信度，不同模式可信度均為1。我們將候選雙語(yǔ)網(wǎng)頁(yè)對(duì)的雙語(yǔ)相似度閾值設(shè)置為0，即相似度為0時(shí)將該候選對(duì)濾掉。69 847對(duì)候選對(duì)中一共有2 664對(duì)的雙語(yǔ)相似度為0。這些過濾掉的網(wǎng)頁(yè)中，2 275對(duì)確實(shí)為非雙語(yǔ)候選網(wǎng)頁(yè)對(duì)，過濾的正確率達(dá)85.40%，它們的類型分布如表4所示。該方法僅利用網(wǎng)頁(yè)鏈接和部分高可信度URL匹配模式，即可過濾掉一定規(guī)模的非雙語(yǔ)網(wǎng)頁(yè)，顯然能進(jìn)一步提高候選雙語(yǔ)網(wǎng)頁(yè)對(duì)的準(zhǔn)確率。

表4 非雙語(yǔ)網(wǎng)頁(yè)對(duì)的類型分布

7 結(jié)論與未來工作

本文對(duì)基于URL組成模式的雙語(yǔ)網(wǎng)頁(yè)發(fā)現(xiàn)方法進(jìn)行了比較全面的設(shè)計(jì)和實(shí)驗(yàn): (1)計(jì)算雙語(yǔ)URL匹配模式的可信度；(2)在可信度計(jì)算的基礎(chǔ)上，提出四種不同的雙語(yǔ)網(wǎng)頁(yè)識(shí)別算法；(3)利用搜索引擎的優(yōu)勢(shì)、僅依據(jù)少量的高可信度雙語(yǔ)URL匹配模式，快速識(shí)別雙語(yǔ)網(wǎng)頁(yè)；(4)最后，利用雙語(yǔ)候選網(wǎng)頁(yè)的雙語(yǔ)相似度，進(jìn)一步過濾非雙語(yǔ)網(wǎng)頁(yè)對(duì)。通過實(shí)驗(yàn)，我們驗(yàn)證了所提方法的有效性。

今后的主要研究方向包括: (1)獲取更多候選雙語(yǔ)種子網(wǎng)站: 一方面可以通過提出的增量算法尋找雙語(yǔ)網(wǎng)站和網(wǎng)頁(yè);另一方面我們可以從網(wǎng)上公開目錄得到候選網(wǎng)站列表；(2)進(jìn)一步優(yōu)化雙語(yǔ)URL匹配模式可信度以及網(wǎng)站的雙語(yǔ)可信度計(jì)算方法，比如: 利用候選雙語(yǔ)網(wǎng)頁(yè)的鏈接關(guān)系來計(jì)算每個(gè)頁(yè)面的PageRank值，然后利用PageRank值對(duì)雙語(yǔ)URL匹配模式可信度進(jìn)行加權(quán)；優(yōu)化雙語(yǔ)匹配模式全局可信度的計(jì)算方法；另外，在同一網(wǎng)站中考慮更多的雙語(yǔ)匹配模式作為雙語(yǔ)網(wǎng)站可信度計(jì)算依據(jù)。(3)研究在不需要雙語(yǔ)種子網(wǎng)站或者盡量少的雙語(yǔ)種子網(wǎng)站的情況下，獲取大規(guī)模雙語(yǔ)網(wǎng)頁(yè)的方法。(4)在本文基礎(chǔ)上，進(jìn)一步抽取雙語(yǔ)平行網(wǎng)頁(yè)的正文、生成平行句對(duì)，最后利用標(biāo)準(zhǔn)數(shù)據(jù)集測(cè)試機(jī)器翻譯結(jié)果的BLEU值，從側(cè)面來評(píng)估本文最終生成的平行語(yǔ)料的質(zhì)量。

[1] Brown P F,Pietra V J D.Pietra S A D,etal.The mathematics of statistical machine translation: Parameter estimation[J].Computational linguistics,1993,19(2),263-311.

[2] Davis M W,Dunning T E.ATREC evaluation of query translation methods for multi-lingual text retrieval[C]//Proceedings of the TREC-4,1995: 483-498.

[3] Resnik P.Parallel strands: A preliminary investigation into mining the web for bilingual text[C]//Proceedings of the AMTA 1998: MachineTranslation and the Information Soup,1998: 72-82.

[4] Ma X,Liberman M.Bits: A method for bilingual text search over the web[C]//Proceedings of the Machine Translation Summit VII,1999: 538-542.

[5] ChenJ,NieJ-Y.Parallel web text mining for cross-language IR[C]//Proceedings of the RIAO2000,2000: 62-77.

[6] Chen J,Chau R,Yeh C-H.Discovering parallel text from the WorldWideWeb[C]//Proceedings of the 2nd Workshop on Australasian Information Security,Data Mining and Web Intelligence，and Software Interna-tionalisation,2004(32): 157-161.

[7] Zhang Y,Wu K,Gao J,etal. Automatic acquisition of Chinese-English parallel corpus from the web [C]//Proceedings of the 2006 European Conference on Advances in Information Retrieval. 2006: 420-431.

[8] Kit C，Ng J Y H.An intelligent web agent to mine bilingual parallel pages via automatic discovery of URL pairing patterns[C]//Proceedings of the 2007 IEEE/WIC/ACM International Conferences on Web Intelligence & Intelligent Agent Technology Workshops,2008: 526-529.

[9] Zhang C，Yao X，Kit C.Finding more bilingual webpages with high credibility via link analysis [C]// Proceedings of the Sixth Workshop on Building and Using Comparable Corpora,2013: 138-143.

[10] Ma S,Zhang C.Automatic collection of the parallel corpus with little prior knowledge[C]//Proceedings of the 2014 China National Conference on Computational Linguistics,2014: 95-106.

[11] Shi L，Niu C，Zhou M,etal.A DOM tree alignment model for mining parallel data from the web[C]//Proceedings of the 2006 International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics.2006: 489-496.

[12] 劉奇，劉洋，孫茂松.URL模式與HTML結(jié)構(gòu)相結(jié)合的平行網(wǎng)頁(yè)獲取方法[J].中文信息學(xué)報(bào)，2013,27(3),91-99.

[13] Liu L,Hong Y ,Lu J,Lang J,Ji H ,&Yao J.An iterative link-based method for parallel web page mining. [C]//Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing.2014: 1216-1224.

[14] Brin S，Page L.The anatomy of alarge-scale hyper-textual web search engine[J].Computer networks and ISDN systems,1998,30(1),107-117.