邸書靈， 劉曉飛， 李 歡

(1.石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北石家莊050043;2.河北聯(lián)合大學(xué)現(xiàn)代教育技術(shù)中心，河北唐山063009)

0 引言

語句相似度計(jì)算是自然語言處理領(lǐng)域中比較重要的研究課題，應(yīng)用廣泛。語句相似度是指兩個(gè)語句相似的程度，即通過一定的算法從信息庫中查找與指定句子相似的句子，得到滿足用戶需求的句子。語句相似度計(jì)算主要應(yīng)用于FAQ系統(tǒng)、信息檢索和翻譯等方面。

目前有很多計(jì)算語句相似度計(jì)算的算法，如詞形詞序綜合法［1-4］、語義依存樹法［5-6］、編輯距離法［1］和基于關(guān)鍵詞的TFIDF法［7］、語義詞典法［8］等，這些方法各有優(yōu)缺點(diǎn)而且仍在不斷發(fā)展完善。

介紹了詞形詞序綜合法的語句相似度計(jì)算算法，它將句子分割成多個(gè)短語，消除了局部的次序變化帶來的影響，該方法還可保證當(dāng)一個(gè)句子的分句或短語整體發(fā)生長距離移動(dòng)后，仍與原句很相似，而眾多短語中關(guān)鍵詞的直接匹配，使得詞形相似度計(jì)算更加準(zhǔn)確。但是該方法對分詞的依賴性很高，往往分詞的質(zhì)量決定了計(jì)算結(jié)果的準(zhǔn)確性，由于目前的分詞算法和系統(tǒng)在歧義處理和未登錄詞識別方面進(jìn)展緩慢，致使分詞具有很大約束性，算法準(zhǔn)度不高，針對基于分詞的詞形詞序綜合法相似度計(jì)算的缺點(diǎn)對該算法進(jìn)行了改進(jìn)。

1 詞形詞序綜合法

詞形詞序綜合法有三部分組成:詞形相似度、詞序相似度和句長相似度。考慮到在兩個(gè)句子比較時(shí)，根據(jù)詞形、詞序和句長各自對整個(gè)相似度計(jì)算的貢獻(xiàn)，詞形相似度起主要作用，句長相似度次要作用，而詞序相似度作用最小。

1.1 詞形相似度

詞形相似度方法是通過計(jì)算兩個(gè)問句的詞形即相同詞的個(gè)數(shù)來比較相似度的［1］。首先將兩個(gè)句子分詞，用s1Arr和s2Arr兩個(gè)數(shù)組分別存放兩句子分詞后的單詞，然后在計(jì)算出兩個(gè)句子共同包含的單詞個(gè)數(shù)sum，若共有單詞出現(xiàn)次數(shù)不相同則取最小出現(xiàn)次數(shù)。Len(s1)表示s1分詞后的詞語數(shù)。詞形相似度計(jì)算公式如下

可以看出詞形相似度數(shù)值范圍為CiSmily(s1，s2)∈［0，1］。

例如:s1:“二維的數(shù)組有哪些存儲(chǔ)方式”，s2:“二維的數(shù)組存儲(chǔ)方式”。分詞后得到:s1Arr={二維，的，數(shù)組，有，哪些，存儲(chǔ)方式}，s2Arr={二維，的，數(shù)組，存儲(chǔ)方式}。CiSmily(s1，s2)=4/6≈0.667。

1.2 計(jì)算句長相似度

兩個(gè)句子長度越接近就越相似。計(jì)算句長相似度采用句子的所有單字的總數(shù)，而非分詞后詞的總數(shù)，這樣避免了，因使用分詞后的詞總數(shù)而忽略有些詞所含單字較多的情況。

句長相似度計(jì)算公式，s1L和s2L分別是句子s1和s2所含單字個(gè)數(shù)

句長相似度的數(shù)值范圍LenSimly(s1，s2)∈［0，1］。

因此，可以計(jì)算出s1:“二維的數(shù)組有哪些存儲(chǔ)方式”，s2:“二維的數(shù)組存儲(chǔ)方式”這這兩個(gè)句子的相似度為LenSimly(s1，s2)=18/21≈0.857。由于兩句長度很接近，故長度相似度較高。

1.3 計(jì)算詞序相似度

共有單詞在兩個(gè)句子中所處位置信息能很好反應(yīng)句子之間的相似程度。首先計(jì)算出s1和s2中都出現(xiàn)且只出現(xiàn)一次的詞的集合onews。然后計(jì)算出onews中各個(gè)詞語依次出現(xiàn)在s2中的位置向量，計(jì)算出逆序數(shù)count。仍然使用同一個(gè)例子，可得onews={二維，的，數(shù)組，存儲(chǔ)方式}。s1中與onews中詞對應(yīng)關(guān)系

二維的數(shù)組有哪些存儲(chǔ)方式

0 1 2 3 4 5

s1的位置向量為{0，1，2，5}。同理可得s2中與onews中詞對應(yīng)關(guān)系

二維的數(shù)組存儲(chǔ)方式

0 1 2 5

s2的位置向量為{0，1，2，5}，由于0＜1，1＜2，2＜5不存在逆序，可得逆序數(shù)count=0。詞序相似度計(jì)算公式

容易得出詞序相似度的數(shù)值也在Record(s1，s2)∈［0，1］之間。

因此，s1和s2兩個(gè)句子的詞序相似度為:Record(s1，s2)=1。即onews中的詞語在兩個(gè)句子中的順序完全相同。若Record(s1，s2)=0，說明順序完全相反。

1.4 語句相似度

語句相似度

式中，λ1，λ2，λ3均為常數(shù)，且λ1+λ2+λ3=1，則Sim(s1，s2)∈［0，1］。

根據(jù)詞形、句長和詞序在相似度計(jì)算中所起作用的大小，給三個(gè)常數(shù)賦值，可設(shè)λ1遠(yuǎn)大于另外兩個(gè)常數(shù)，λ1=0.8，λ2=0.15，λ3=0.05。

最終得到s1:“二維的數(shù)組有哪些存儲(chǔ)方式”，s2:“二維的數(shù)組存儲(chǔ)方式”兩個(gè)句子相似度Sim(s1，s2)=0.8*0.667+0.15*0.857+0.05*1≈0.712。

2 存在的問題及改進(jìn)

詞形詞序綜合法因其容易理解及易于實(shí)現(xiàn)，而且其計(jì)算結(jié)果能達(dá)到人們的一半要求，在實(shí)際應(yīng)用中有一定的優(yōu)勢。

但是上述相似度計(jì)算方法仍有局限性。該相似度計(jì)算方法，對分詞的依賴性很強(qiáng)，例如:要比較的是“哈夫曼”和“哈夫曼樹”，假如詞庫中(你也可以使用其他非基于詞典詞庫的分詞方法)有“哈夫曼樹”但是無“哈夫曼”時(shí)，第一句就會(huì)分成{哈，夫，曼}，而第二句分詞后是{哈夫曼樹}，按照上述算法，這兩句的詞形相似度為0，總的相似度僅為0.129。這顯然不符合實(shí)際。因此，需要對以上方法進(jìn)行改進(jìn)。

改進(jìn)的方法是，增加計(jì)算兩個(gè)句子不分詞的詞形相似度計(jì)算，來平衡分詞后對相似度計(jì)算的影響。即，在式(1)中的sum為兩個(gè)句子共同包含的單字個(gè)數(shù)，若共有單字出現(xiàn)次數(shù)不相同則取最小出現(xiàn)次數(shù)。Len(s1)表示s1中的單字個(gè)數(shù)。其計(jì)算公式不變，單字詞形相似度

式(4)中的語句相似度也要更改為

式中，λ1=0.4，λ2=0.15，λ3=0.05，λ4=0.4，λ1+λ2+λ3+λ4=1。使得基于分詞和單字的詞形相似度計(jì)算所占比重相同。經(jīng)過改進(jìn)后，“哈夫曼樹”和“哈夫曼”的NoCiSmily(s1，s2)=0.75，總相似度為0.429，有了較大提升。

那么，為什么不使用單字的詞形相似度計(jì)算取代基于分詞的詞形相似度計(jì)算呢?因?yàn)閱巫衷~形相似度計(jì)算也有局限。例如:“多維數(shù)組”和“多個(gè)二維數(shù)組”，因?yàn)樵~庫中有“多維數(shù)組”，所以基于單字的相似度NoCiSmily(s1，s2)≈0.667，Sim(s1，s2)≈0.653(詞序和詞長相似度計(jì)算不變)說明這兩句話相似度很高，但是很顯然我們要查“多維數(shù)組”，“多個(gè)二維數(shù)組”就離我們想要的相去較遠(yuǎn)，因此就要降低它們的相似程度，而使用上述改進(jìn)的方法CiSmily(s1，s2)=0，Sim(s1，s2)≈0.387。有效的降低了使用單字詞形相似度計(jì)算造成的較低的查準(zhǔn)率。而且從這也可以看出，這樣符合語義的要求。

改進(jìn)后的相似度計(jì)算得到的結(jié)果更準(zhǔn)確也更合理。設(shè)置一個(gè)閾值作為問句相似的一個(gè)條件，當(dāng)兩個(gè)問句的相似度高于這個(gè)閥值時(shí)，就認(rèn)為這兩個(gè)問句相似。由于改進(jìn)的方法是取了兩種詞形詞序相似度的折中，因此總的相似度將會(huì)趨于降低，但這并不會(huì)影響結(jié)果的準(zhǔn)確性，只需根據(jù)實(shí)際情況適當(dāng)設(shè)置閥值即可得到準(zhǔn)確結(jié)果。而且將此方法應(yīng)用于上面兩種情況下準(zhǔn)確性會(huì)大大提高。很適合在某一領(lǐng)域的自動(dòng)問答系統(tǒng)中使用。

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

本次實(shí)驗(yàn)從《數(shù)據(jù)結(jié)構(gòu)》課程常用問句集中選取16個(gè)不同類別，每類有3～4句相似的句子組成，共計(jì)50句，并作為樣本句，另外依據(jù)這些樣本句人工構(gòu)造出50個(gè)與樣本句相似的句子作為測試集。對測試集中的每句話，分別設(shè)計(jì)與之相似的語句分別使用改進(jìn)前和改進(jìn)后兩種方法計(jì)算所有句子與其的相似度，并將相似度最大的句子和人工判斷出的正確句子做比較，若相同則認(rèn)為結(jié)果正確。實(shí)驗(yàn)結(jié)果如表1。

表1 實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可知，改進(jìn)的方法的效率明顯較高，得益于綜合了兩種詞形相似度計(jì)算方法，兼顧了基于分詞和基于單字算法的優(yōu)點(diǎn)，因此一般說來改進(jìn)前可以得到正確結(jié)果的，改進(jìn)后也可以得到正確結(jié)果。但是，考慮到用戶在輸入時(shí)對于一些由多個(gè)詞復(fù)合而成的詞語，并不一定能完整輸入整個(gè)詞，可能只是輸入這個(gè)詞語的部分或部分的組合或內(nèi)部詞語詞序顛倒，將使得改進(jìn)前的算法的準(zhǔn)確率急劇下降，如:“時(shí)間和空間復(fù)雜度”和“時(shí)空復(fù)雜度”，按照改進(jìn)前的算法(詞庫中有“空間復(fù)雜度”無“時(shí)空復(fù)雜度”)相似度為Sim(s1，s2)≈0.115，這顯然不對，改進(jìn)后Sim(s1，s2)≈0.365，相對于改進(jìn)前已經(jīng)有明顯的提升，而這也是改進(jìn)后算法的優(yōu)勢之一。另外，由于改進(jìn)前基于分詞的缺陷，即:過度依賴于分詞，有時(shí)會(huì)出現(xiàn)難以接受的結(jié)果，如:用s1:“動(dòng)態(tài)查找表的表示方法”來搜索與之最相似的句子s2:“動(dòng)態(tài)和靜態(tài)查找表有哪些表示方法”，兩者相似度(詞庫中有“靜態(tài)查找表”和“動(dòng)態(tài)查找表”)為Sim(s1，s2)≈0.399;但是s1與s3:“有哪些存儲(chǔ)圖的方法”的相似度為Sim(s1，s2)≈0.459，這樣的結(jié)果顯然錯(cuò)誤，在這點(diǎn)上改進(jìn)后的算法明顯優(yōu)于改進(jìn)前，改進(jìn)后s1與s2的相似度Sim(s1，s2)≈0.524，s1與s3的相似度Sim(s1，s2)≈0.445，顯然改進(jìn)后更合理?；谝陨系姆治觯膶?shí)驗(yàn)中得出，若按相似度由高到低排序輸出前N(N≥2)個(gè)句子，改進(jìn)后的結(jié)果更準(zhǔn)確。

本次實(shí)驗(yàn)沒有去除停用詞，若去除停用詞將會(huì)使算法的準(zhǔn)度和性能進(jìn)一步提高。

4 結(jié)語

基于詞形詞序的相似度計(jì)算改進(jìn)算法分為四個(gè)部分，將四部分?jǐn)?shù)值匯總就可得到兩個(gè)句子的最終相似度。相對來說，詞形詞序綜合算法易于理解和實(shí)現(xiàn)，更重要的是計(jì)算結(jié)果也可靠。由于詞形相似度計(jì)算在整個(gè)相似度計(jì)算中所占比重較大，因此本文對基于分詞的相似度計(jì)算進(jìn)行了優(yōu)化，增加了單字詞形相似度計(jì)算來降低過分依賴分詞帶來的不合理計(jì)算。另外，可以根據(jù)實(shí)際情況，靈活改變相似度計(jì)算中四個(gè)參數(shù)的值，來控制各部分在總的相似度中所占的比重。

［1］董自濤，包佃清，馬小虎.智能問答系統(tǒng)中問句相似度計(jì)算方法［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2010，32(1):31-34.

［2］王常亮，滕至陽.語句相似度計(jì)算在FAQ中的應(yīng)用［J］.計(jì)算機(jī)時(shí)代，2006(2):24-25.

［3］楊思春.一種改進(jìn)的句子相似度計(jì)算模型［J］.電子科技大學(xué)學(xué)報(bào)，2006，35(6):956-959.

［4］李玉紅，柴林燕，張琪.結(jié)合分詞技術(shù)與語句相似度的主觀題自動(dòng)判分算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(11):2663-2666.

［5］車萬翔，劉挺，秦兵，等.基于改進(jìn)編輯距離的中文相似句子檢索［J］.高技術(shù)通訊，2004(7):15-19.

［6］李彬，劉挺，秦兵，等.基于語義依存的漢語句子相似度計(jì)算［J］.計(jì)算機(jī)應(yīng)用研，2002(12):15-17.

［7］秦兵，劉挺，王洋，等.基于常問問題集的中文問答系統(tǒng)研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2003，35(10):1179-1182.

［8］李素建.基于語義計(jì)算的語句相關(guān)度研究［J］.計(jì)算機(jī)工程與應(yīng)用，2002(7):75-76.