沙力木別克畢山汗，古麗拉阿東別克

(新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆烏魯木齊830046)

0 引言

句子相似度計(jì)算在自然語(yǔ)言處理方面的各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，例如在自動(dòng)問(wèn)答系統(tǒng)中問(wèn)題庫(kù)的檢索．根據(jù)用戶的提問(wèn)在知識(shí)庫(kù)中查找對(duì)應(yīng)的答案是通過(guò)計(jì)算提問(wèn)的句子和知識(shí)庫(kù)中對(duì)應(yīng)的句子之間相似度來(lái)解決的．在信息過(guò)濾技術(shù)中，通過(guò)句子相似度計(jì)算可自動(dòng)過(guò)濾掉用戶可能并不想看到的信息．同樣，在機(jī)器翻譯、自動(dòng)文摘中均用到該技術(shù)獲取必要的信息．

句子相似度計(jì)算也是基于實(shí)例的機(jī)器翻譯方法(Example Based Machine Translation)中的一個(gè)關(guān)鍵技術(shù)，其作用是在實(shí)例庫(kù)中查找跟輸入句子相似的句子，然后用相似句子的對(duì)齊目標(biāo)句子作為翻譯模板進(jìn)行片段對(duì)齊、重組等操作最終完成翻譯．因此，句子相似度計(jì)算結(jié)果的準(zhǔn)確性會(huì)影響到翻譯質(zhì)量．

1 國(guó)內(nèi)外現(xiàn)狀分析

國(guó)外對(duì)于文本相似度計(jì)算的研究起步較早，Gerard Salton于1969年提出的基于向量空間模型(Vector Space Model,VSM)的文本相似度計(jì)算模型是目前最成熟和應(yīng)用最廣泛的文本相似度計(jì)算模型．它最初被引用到文章中相似度的計(jì)算中，后來(lái)被引入到句子相似度的計(jì)算中．其基本思想是將文本分為若干個(gè)特征項(xiàng)，計(jì)算出每個(gè)特征項(xiàng)的權(quán)重，特征項(xiàng)權(quán)重用分量的向量來(lái)表示，對(duì)向量計(jì)算來(lái)表示文檔相似度．在此基礎(chǔ)上，很多改進(jìn)的算法應(yīng)運(yùn)而生．

國(guó)內(nèi)在漢語(yǔ)句子的相似度計(jì)算方面取得了較好的成果，例如張民等設(shè)計(jì)了一種基于詞的計(jì)算相似度方法．而句子相似度計(jì)算中的輸入句子和實(shí)例句子長(zhǎng)度相差較大，其中單詞個(gè)數(shù)也不一致，因此，輸入句子與實(shí)例句子中每個(gè)單詞都可能存在相關(guān)性，這種相關(guān)性位置可加權(quán)處理．

2 哈薩克語(yǔ)句子相似度計(jì)算模型

哈薩克語(yǔ)句子相似度計(jì)算模型由快速檢索模塊和相似度計(jì)算模塊構(gòu)成．在快速檢索模塊中實(shí)現(xiàn)實(shí)例快速匹配，在找到相似實(shí)例句子集合后，作為相似度計(jì)算模塊的輸入．計(jì)算相似度模塊中用到了兩種模型的結(jié)合，即基于詞的句子相似度計(jì)算和基于向量的相似度計(jì)算．

2.1 快速檢索模塊

基于實(shí)例的機(jī)器翻譯中，關(guān)鍵問(wèn)題是如何從海量實(shí)例庫(kù)中篩選出一定數(shù)量的句子作為候選集合，這些集合中包含了與輸入句子最相似的句子，為此設(shè)計(jì)了快速檢索模塊．

為進(jìn)一步提高檢索速度，對(duì)數(shù)據(jù)庫(kù)中的句子建立散列單詞倒排索引．首先對(duì)實(shí)例庫(kù)中實(shí)例的各單詞建立散列表，然后將每個(gè)單詞所出現(xiàn)的多個(gè)實(shí)例編號(hào)id建立一個(gè)單鏈表，其結(jié)構(gòu)如圖1，其中id是單詞出現(xiàn)過(guò)的實(shí)例編號(hào)．

圖1 倒排索引圖

快速檢索的具體過(guò)程如下：

Step 1:對(duì)輸入的句子進(jìn)行解析，獲得單詞鏈表(圖1)，其中Word是單詞，ID是該單詞出現(xiàn)過(guò)的實(shí)例id集合，id是實(shí)例編號(hào)；

Step 2:統(tǒng)計(jì)(A過(guò)程)，計(jì)算出單詞鏈表中頻繁出現(xiàn)過(guò)的實(shí)例的id集合；

Step 3:返回實(shí)例id集合，作為相似度計(jì)算候選實(shí)例集合．

其中A過(guò)程如下:

例如輸入：

圖2 A過(guò)程

從圖2中可以看到，所有單詞在編號(hào)為681實(shí)例中都出現(xiàn)過(guò)，出現(xiàn)頻率最高，跟輸入句子的關(guān)聯(lián)性比其他實(shí)例強(qiáng)．在A過(guò)程中對(duì)每一個(gè)單詞的ID進(jìn)行統(tǒng)計(jì)，計(jì)算每個(gè)id出現(xiàn)的次數(shù)，并將統(tǒng)計(jì)結(jié)果按降序排列．例如圖2中的每個(gè)id統(tǒng)計(jì)結(jié)果為[(681,3)，(642,1），(971,1)，(722,1)，(723,1)，(724,1)]．最終留下頻率高的id集合，剩下的都過(guò)濾．

2.2 相似度計(jì)算模塊

2.2.1 基于詞的相似度計(jì)算

1)詞形相似度

詞形相似度（詞重疊法，英文名稱Word Overlap Measures）反映兩個(gè)句子形態(tài)上的相似程度，以兩個(gè)句子中所含相同詞的個(gè)數(shù)來(lái)衡量，由以下公式來(lái)表示：

其中l(wèi)en(samewc(x,y))表示輸入句子X(jué)和實(shí)例句子Y中的相似詞一一對(duì)應(yīng)的個(gè)數(shù)，simoverlap表示詞形相似度，length(x)表示句子X(jué)中的詞總個(gè)數(shù),length(y)表示句子Y中詞的總個(gè)數(shù)(包括句子中的標(biāo)點(diǎn)符號(hào))．

詞形相似度計(jì)算過(guò)程如下：

輸入句子：

實(shí)例句子：

通過(guò)計(jì)算公式可以計(jì)算出兩個(gè)句子的相似度

這說(shuō)明C句子比B句子在形態(tài)上更接近A句子．

2)基于逆序數(shù)詞序相似度算法

兩個(gè)句子中出現(xiàn)的單元可能完全相同，但我們不能確定這兩個(gè)句子完全相同．兩個(gè)句子中各個(gè)單元出現(xiàn)的位置不同可能導(dǎo)致兩個(gè)句子表示完全不同的意思，所以必須進(jìn)行詞序上的相似度計(jì)算．

對(duì)于包含n(n∈N)個(gè)不同元素的序列，先規(guī)定各元素之間有一個(gè)標(biāo)準(zhǔn)次序(例如n個(gè)不同的自然數(shù)，規(guī)定由小到大為標(biāo)準(zhǔn)次序)．在這n個(gè)元素的任一排列中，當(dāng)某兩個(gè)元素的先后次序與標(biāo)準(zhǔn)次序不同時(shí)就稱為一個(gè)逆序．一個(gè)排列中所有逆序的總數(shù)叫做這個(gè)排列的逆序數(shù)．

詞序反映兩個(gè)句子中所含相同單元在位置關(guān)系上的相似程度，以兩個(gè)句子中所含相同單元的相鄰順序逆向的個(gè)數(shù)來(lái)衡量．設(shè)x，y表示兩個(gè)句子，ordoccur(x,y)表示在句中都出現(xiàn)且只出現(xiàn)一次的單元集合，pfir(x,y)表示ordoccur(x,y)中的單元在X中的位置序號(hào)構(gòu)成的向量，psec(x,y)表示pfir(x,y)中的分量按對(duì)應(yīng)單元在y中次序排列生成的向量．

例1的詞序相似度計(jì)算方法為：ordoccur(A,C)={}，它所構(gòu)成的pfir(x,y)={0,2,3,4}，psec(x,y)={0,2,3,4}，rew(x,y)表示psec(x,y)相鄰分量的逆序數(shù)．上例中：0<2，2<3，3<4得到rew(x,y)=0，句子x，y的詞序相似度計(jì)算公式如下

根據(jù)公式2，我們可以計(jì)算出A，C兩個(gè)句子的詞序相似度為

3)句長(zhǎng)相似度

從句子長(zhǎng)度上來(lái)標(biāo)注句子的相似性一定程度上反映句子形態(tài)上的相似性．實(shí)例句和輸入句長(zhǎng)度差會(huì)影響到句子相似度．句長(zhǎng)相似度公式如以下：

輸入句子x和實(shí)例句子y的詞相似度計(jì)算公式similarWStn(x,y)為

其中的α，β，γ是實(shí)驗(yàn)值.

2.2.2 基于向量空間模型的TF_IDF相似度計(jì)算方法

TF_IDF是基于向量空間模型中最廣泛使用的方法之一．若輸入句子與實(shí)例句子中包含的所有詞為w1，w2，···，wn,那么輸入句子和實(shí)例句子可以用n維向量t=表示,實(shí)例句子用q=來(lái)表示，其中ti=ci*log(M/n)，ci是特征項(xiàng)TF值，以特征項(xiàng)在該句子中出現(xiàn)的次數(shù)來(lái)衡量；log(M/n)是該特征項(xiàng)的IDF值，其中M是對(duì)齊實(shí)例庫(kù)中總的句子個(gè)數(shù)，n是特征項(xiàng)出現(xiàn)過(guò)的句子個(gè)數(shù)．從Ti計(jì)算我們可以看出具有較高TF值的特征項(xiàng)，不一定具有高IDF值，對(duì)句子的分辨能力低．例如哈薩克語(yǔ)中出現(xiàn)頻率很高，它在句子中既可以做代詞主語(yǔ)，也可以做介詞，但是對(duì)句子的分辨能力很低，因此該方法綜合考慮了特征項(xiàng)出現(xiàn)的概率和分辨能力．

同樣，我們可以計(jì)算出實(shí)例句子的n維向量q=，得到輸入句子和實(shí)例句子n維向量t和q后，句子相似度可以用向量t和q向量的余弦來(lái)表示

2.2.3 總相似度計(jì)算

計(jì)算基于詞特征和向量特征相似度以后總相似度similarZong計(jì)算公式,

在計(jì)算句子相似度時(shí)，輸入句子和實(shí)例句子中出現(xiàn)同義詞，例如：

兩個(gè)句子所表達(dá)的意思相同．但實(shí)例句子中出現(xiàn)了同義詞，不進(jìn)行同義詞替換直接進(jìn)行相似度計(jì)算會(huì)影響到計(jì)算準(zhǔn)確率．為了避免這種情況的出現(xiàn)，本文中提出了同義詞替換，算法流程如圖3所示．

圖3 算法流程

3 哈薩克語(yǔ)句子相似度計(jì)算模型實(shí)現(xiàn)

本程序包括兩大模塊：倒排索引模塊和計(jì)算相似度模塊．倒排索引模塊先把新的實(shí)例句子分成詞，然后把它添加到倒排索引庫(kù)．

句子相似度計(jì)算界面中，計(jì)算輸入句子和實(shí)例句子相似度按相似度降序返回結(jié)果如圖5．

圖4 倒排索引界面

圖5 句子相似度計(jì)算界面

4 實(shí)驗(yàn)結(jié)果與分析

哈薩克語(yǔ)句子相似度計(jì)算尚處于初期階段，用以評(píng)價(jià)哈薩克語(yǔ)句子相似度的標(biāo)準(zhǔn)很少．目前對(duì)齊實(shí)例庫(kù)中有1 000個(gè)句子和3 500多個(gè)已經(jīng)倒排索引好的詞，相似度計(jì)算實(shí)驗(yàn)結(jié)果如表1，表2，表3．

表1 基于向量空間模型不進(jìn)行同義詞替換相似度計(jì)算

表2 基于向量空間模型和基于詞相結(jié)合的相似度計(jì)算(替換同義詞之前)

表3 基于向量空間模型和基于詞相結(jié)合的相似度計(jì)算(替換同義詞之后)

從三次實(shí)驗(yàn)結(jié)果來(lái)看，基于向量空間模型和基于詞相結(jié)合的計(jì)算相似度計(jì)算方法比基于向量空間模型和相結(jié)合的不進(jìn)行同義詞替換方法，在哈薩克語(yǔ)句子相似度中的正確率有所提高．

5 總結(jié)

散列的倒排索引能夠有效地實(shí)現(xiàn)快速查找．為了從雙語(yǔ)對(duì)齊實(shí)例庫(kù)中快速地查找候選句子集合作為下一步工作的輸入，計(jì)算輸入句子與實(shí)例句子的詞相似度和向量余弦值，然后結(jié)合兩種方法整合句子的相似度．為了避免同義詞產(chǎn)生的歧義，計(jì)算過(guò)程中使用了同義詞替換，同義詞替換可以提高相似度計(jì)算的正確率．由于現(xiàn)在對(duì)齊實(shí)例庫(kù)規(guī)模不大，句子相似度計(jì)算結(jié)果還差強(qiáng)人意，下一步工作將繼續(xù)擴(kuò)大對(duì)齊實(shí)例庫(kù)，繼續(xù)提高搜索速度，更多的引入哈薩克語(yǔ)語(yǔ)法、語(yǔ)義知識(shí)，提高正確率，從而提高翻譯質(zhì)量．

參考文獻(xiàn)：

[1]阿力木塞買提·阿布力哈孜.基礎(chǔ)哈薩克語(yǔ)[M].烏魯木齊:新疆大學(xué)出版社,2009,3.

[2]田生偉,吐?tīng)柛ひ啦祭?禹龍.一種維吾爾語(yǔ)句相似度算法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(26):144-146.

[3]南鉉國(guó),崔榮一.基于多層次融合的語(yǔ)句相似度計(jì)算模型[J].延邊大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,33(3):191-194.

[4]卡哈爾江·阿比的熱西提,吐?tīng)柛ひ啦祭?一種改進(jìn)的維吾爾語(yǔ)句子相似度計(jì)算方法[J].中文信息學(xué)報(bào),2011,25(4):50-53

[5]達(dá)吾勒·阿布都哈依爾，海拉提·克孜爾別克,等.基于規(guī)則的哈薩克語(yǔ)詞干提取算法的研究[J]．新疆大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,28(2):238-241.

[6]南鉉國(guó),崔榮一.基于多層次融合的語(yǔ)句相似度計(jì)算模型[J].延邊大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,33(3):191-194

[7]周法國(guó),楊炳儒.句子相似度計(jì)算新方法及在問(wèn)答系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2008.44(1):165-167

[8]江阿古麗·哈依達(dá)爾，卡哈爾江·阿比的熱西提，阿里木江·亞森，等.一種哈薩克語(yǔ)句子相似度計(jì)算方法的研究[J].新疆大學(xué)學(xué)報(bào)，2012,29(4):473-477.

[9]王長(zhǎng)勝，劉群.基于實(shí)例的漢英機(jī)器翻譯系統(tǒng)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2002,38(8)：126-127.

[10]吉?jiǎng)佘?基于Levenshtein Distance算法的句子相似度計(jì)算[J].電腦知識(shí)與技術(shù),2009,5(9):143-144