信息檢索中一種句子相似度的計算方法

劉云芳，楊燕，賈真，尹紅風，楊宇飛

西南交通大學信息科學與技術學院，四川成都 610031

信息檢索是指根據用戶提出的問題從大量文檔資源集合中自動地找到與用戶查詢請求相關的各種信息［1］，即為使用戶的查詢句子或詞語與文檔集信息匹配的一個過程，其實質就是對自然語言進行相關的處理，從而使匹配的效果達到令人相對滿意的程度［2］。信息檢索的主要目的是獲取用戶所需的全面的且精確的信息，這就需要對信息檢索中運用的技術進行相應的改進與完善。信息索引技術主要涉及信息詞語切分和詞語語法分析、進行詞性標注及相關自然語言處理、建立索引項索引、檢索結果處理技術，其中檢索結果處理技術是關鍵技術，其核心是依據計算結果與查詢語句的相關程度來排序。檢索結果排序則應用到了句子相似度計算等技術。關于句子相似度的計算，不同的學者提出了不同的方法。如文獻［3］主要依據分詞以及詞性標注技術對句子表面相似度進行了計算。文獻［4］通過比較兩句相同詞的個數及其位置關系，得到兩句的詞形相似度和詞序相似度，再通過詞形相似度和詞序相似度計算句子的相似度。文獻［5］主要根據編輯距離與依存文法對句子進行相似度計算。文獻［6］則是基于知網的句子相似度計算方法，而文獻［7］中基于本體的句子相似度方法與文獻［6］有異曲同工之效。由于對句子的分析角度不同，可以將句子相似度計算方法分為2種，一種是基于向量空間模型的計算方法，也就是句子表面相似度的計算方法，另一種是基于句法和語義的句子相似度計算方法。由于在信息檢索中用戶使用的查詢語句較短，有時還缺乏必要的語境，因此單純的使用關鍵詞進行匹配并不能令人滿意。為解決這一問題，有學者提出了查詢擴展技術［8］，即在對查詢語句進行擴展的基礎上再進行句子相似度的計算。由于以上方法中對句子主成分的分析較少且不明確，因此文中依據句法依存樹對用戶問句進行了處理，并依此來確定句子中的關鍵字詞以及其對應的權重。同時，文中在句子相似度計算方面提出了一種新的基于二叉樹帶權路徑長度計算的方法。二叉樹的帶權路徑長度計算即是計算每個葉子節點的權值與結點到根結點距離的乘積之和，而在文中中，葉子節點的權值即為句子中關鍵詞的權重。最后計算句子間二叉樹帶權路徑長度的比值，得到句子間的相似度。由于在信息檢索中主要還是對有標題且標題總結性比較強的信息進行檢索，所以文中在對關鍵字詞進行擴展時只考慮了同義詞近義詞擴展。

1 算法原理

1.1 句子分析以及關鍵詞提取

首先對句子進行依存句法分析，依存句法分析是將句子由一個線性序列轉化為結構化的依存樹，即利用依存標注表示出各詞匯之間的關系，同時對每個詞匯做了詞性標注、詞義消歧、命名實體等處理［9］。如句子“劉德華的電影有哪些”經過分詞處理、詞性標注以及句法分析后的結果如表1。

表1 例句處理結果

句子的依存樹結構如圖1所示。

圖1 句子的依存樹結構

國內部分學者研究得出有90%左右的用戶輸入的中文檢索單字為2～6個，其中2個字詞的占58%，4個字詞的約占18%，3個字詞約占14%。因此可以只對中文單句進行分析。

根據語言學知識，對中文單句進行分析可知，除了單個字詞外，幾乎每個句子都包含主語、謂語、賓語這些主要成分，有些還包含了修飾的部分，即定語、狀語、補語等。句子的主要成分毫無疑問對句子的貢獻度是比較大的，而這些成分中的詞不可能包含所有詞性的詞，如連詞等，因此，在保留句子關鍵詞時，選擇了保留部分詞性的詞，保留規則如下:

1)保留詞性標注為 a、b、g、i、j、m、x、r、ws、v 以及以n開頭的詞語，但一般不保留動詞“是、有”等。

2)若句首的詞語的依存關系為HED，且詞性為v的則去除。

由于在句子中，謂語是起到了承上啟下的橋梁作用，而主語和賓語對句子的語義貢獻度較大，因此，選出貢獻度最大的詞語對計算句子相似度有很大的幫助，查找貢獻度最大的詞語的規則如下:

1)若句中含依存關系為SBV的詞，且詞性標注不為r，則為貢獻度最大的詞語。

2)若句中不含依存關系為SBV的詞，含有依存關系為POB的詞，則依存關系為POB的詞為貢獻度最大的詞語。

3)若依存關系不包含SBV和POB的詞，含有依存關系為VOB且詞性標注是以n開頭的詞，則為貢獻度最大的詞語。

4)若句子中不包含依存關系為SBV、POB以及VOB的詞，且依存關系為HED的詞的詞性不為動詞或疑問代詞，則該詞為貢獻度最大的。如句子“劉德華的電影有哪些”經過處理后保留關鍵詞“劉德華”、“電影”、“哪些”，根據以上規則可知貢獻度最大的關鍵詞為“電影”。

1.2 樹的帶權路徑長度算法

帶權路徑長度(weighted path length of tree，WPL)算法是用在樹結構中的一種算法，該算法包含了結點的權值、結點到樹根之間的路徑長度與結點的帶權路徑長度。

結點的權值:在一些應用中賦予樹中結點的一個有某種意義的實數。

結點到樹根之間的路徑長度:樹根層數為0時，結點所在的層數。

結點的帶權路徑長度:結點到樹根之間的路徑長度與該節點權值的乘積。

WPL:樹中所有葉結點的帶權路徑長度之和。

文中主要用到了最優二叉樹的帶權路徑長度的計算方法。

如一組數(2，4，5，7，8，9)形成的最優二叉樹結構如圖2所示。

圖2 最優二叉樹結構

該二叉樹由下而上葉子結點的權值是由小到大的。圖2中二叉樹的帶權路徑長度計算公式為

2 實現方法

方法流程如圖3。算法實現主要步驟包括句子預處理、關鍵詞權重設置、關鍵詞擴展、二叉樹帶權路徑長度計算以及問句與標題句的相似度計算。

1)句子預處理:該部分包含了分詞處理和句法分析2個部分，主要是對用戶問句中關鍵詞權重的設置做基礎。

2)關鍵詞權重設置:根據問句中關鍵詞的詞性以及在句子中的依存關系，為每個關鍵詞設置權重。

3)關鍵詞擴展:由于有些詞有同義詞和近義詞，為了更準確的與標題句進行相似度的計算，對問句中的關鍵詞進行了相應的同義詞近義詞擴展。

4)二叉樹帶權路徑長度計算:將用戶中的所有關鍵詞對應的權重以最優二叉樹的形式表示出來，并計算該二叉樹的帶權路徑長度。

5)問句與標題句的相似度計算:根據問句的帶權路徑長度和標題句中包含的關鍵詞，對問句與標題句之間的相似度進行計算。

圖3 算法實現步驟

2.1 句子預處理

在對用戶問句進行句法分析之前，要對問句進行分詞以及詞性標注處理，同時也要對標題句進行分詞處理，文中主要運用了西南交通大學思維與智慧研究所的耶寶分詞系統。由于耶寶分詞具有超大規模的語料庫和分詞詞庫，以及較準確的歧義和未登錄詞識別，分詞準確率較高，因此能對句子進行較準確的分詞［10］，為后面句子相似度的計算做了良好的鋪墊。

文中在使用分詞系統以及句法分析系統時也做了一些處理。由于西南交大的分詞系統中應用的是北大的詞性標注，而哈工大的句法分析系統應用的是863詞性標注，所以在用西南交大的分詞系統進行分詞后又將詞性標注轉換成了哈工大句法分析系統中的詞性標注，以保證依存關系的準確性。

2.2 關鍵詞權重的設置

由主觀判斷，認為一個句子中貢獻度最大的詞的權重將占整個句子權重的一半以上，而疑問詞對句子信息的貢獻度極小，可賦予一個很小的權重值，并經過多個單句之間相似度計算的測試，對關鍵詞的權重設置運用了如下一些規則，即句中若含有貢獻度最大的詞，根據經驗值將其權重設置為0.5，若剩下的關鍵詞中含有詞性為r或v的個數為m，設每個詞的權重為x，其余的詞個數為n，設權重為y，則求權重公式為

2.3 同義詞近義詞擴展

文中對用戶問句進行處理后提取句中關鍵詞，并找出每個關鍵詞的同義詞、近義詞，組成不同的向量，關鍵詞與其同義詞對應的權重相同。其中，同義詞、近義詞的擴展主要依據一個已經建立的同義詞、近義詞庫，該庫中的同義詞、近義詞不僅包含了同義詞詞林中的同義詞近義詞對，同時也包含了在大量的百度百科詞條中基于規則抽取出的同義詞對。

2.4 問句的二叉樹帶權路徑長度計算

根據式(2)計算出所有關鍵詞的權重，然后根據權重向量進行問句的二叉樹帶權路徑長度的計算。計算方法如下:

1)若問句中只有1個或2個詞，則設其二叉樹的帶權路徑長度qw=1。

2)若問句中的詞如圖4所示含有2個以上關鍵詞，則可將其左邊的向量轉化成最優二叉樹，然后計算二叉樹的帶權路徑長度qw。

2.5 問句與標題句之間的相似度計算

對檢索內容的標題進行處理，處理方法如下:

1)若標題中不含有問句中的關鍵詞或關鍵詞的同義詞近義詞，則其二叉樹的帶權路徑長度aw=0。

2)若標題中只含1個詞或只含2個詞且均為問句中的關鍵詞或關鍵詞的同義詞，則其帶權路徑長度aw=qw。

3)若標題中含有2個以上問句中的關鍵詞或關鍵詞的同義詞近義詞，去除句中停用詞后總的詞的個數為i，與問句中關鍵詞或關鍵詞的同義詞近義詞相同的詞數為j，則標題中詞的權重設置方法如下:

a)與問句中關鍵詞或關鍵詞的同義詞相同的詞的權重為

weightq(m)為與問句中關鍵詞或關鍵詞的同義詞相同的詞在問句中的權重。

b)與問句中關鍵詞或關鍵詞的同義詞不相同的詞的權重如下:

根據式(1)可計算出此標題句對應的二叉樹帶權路徑長度aw

最后把標題句的權重視為其與問句之間的句子相似度Sim(a)。

3 實驗分析

3.1 實驗步驟

實驗主要步驟如下:

1)運用分詞系統以及句法分析系統對問句進行分析;

2)對問句中的關鍵詞進行擴展，并設置權重，計算句子的二叉樹帶權路徑長度;

3)對標題句進行去停用詞以及提取關鍵詞處理;

4)對標題中的詞設置權重，并計算對應的二叉樹帶權路徑，然后得到句子對應的權重，即與問句之間的相似度。

3.2 實驗數據集

從哈工大信息檢索研究室問答系統問題集中抽取104個問句，并對這104句中的關鍵詞進行同義詞近義詞擴展，每個問句擴展出一個或以上相同相似的句子，然后在保證每個句子都有相似句子的情況下保留530個問句形成新的問題集。

由于百度是最大的中文搜索引擎，因此文中選擇在百度搜索引擎中為這530個句子搜索出相應的答案，由于搜索結果的量較大，且統計用戶翻閱答案的量是有限的，因此文中只選取了每個問題對應的搜索結果的前200個，又由于百度搜索存在競價排名，所以會在搜索結果中的最前面出現廣告干擾，文中將予以去除。同時所得搜素結果將包含標題句、網頁鏈接以及對應網頁的主要內容。其中主要內容的抽取文中首先利用正則表達式將網頁中主要部分即＜body＞＜/body＞中的內容抽取出來，然后對已抽取內容進行分詞以及詞性標注處理，只保留詞性標注不為 vyou、vshi且不以 w、u、c、p、d 以及 r開頭的詞，由于除了主要內容可能會含有英文單詞外，網頁源碼中也存在很多英文單詞，因此在處理詞性標注以x開頭的詞時，根據網頁結構，只保留了其前面詞性標注以及后面的詞性標注不同時為w或x的詞，一般中文網頁中大量的英文介紹內容很少，因此這種方法對主要內容的抽取影響不大，但網頁噪聲如廣告等會對網頁主要內容產生一些影響，文中不對該方面做深入研究。然后經過網頁去重處理，最后形成含502173個搜索結果的信息檢索結果集。

當用戶提出問題時，首先運用關鍵詞匹配以及tfidf算法對檢索結果集進行檢索和排序，然后再用文中算法對已檢索結果進行二次排序。

文中采取平均查全率(mean of average recall，MAR)，查準率(mean of average precision，MAP)以及前30個返回的網頁的查準率(precision of return results of top 30，PRRT30)作為檢索結果的評測標準。

3.3 實驗結果及分析

可先用如下實驗結果來說明文中的句子相似度計算方法的效果。用戶問句為“兒童電影有哪些”。文中根據搜索引擎給出的搜索結果設置了幾個標題句，并利用不同方法對標題句與問句的相似度進行了計算與分析，計算結果如表2所示。

表2 相似度對比

方法1是一種基于詞語共現統計的方法，利用了北大計算語言所提出的一種句子相似度計算公式:2c/(m+n)，式中:m、n分別為2個句子的詞的個數，c是2個句子中相同詞的個數［11］。

方法2是一種基于知網的句子相似度計算方法，利用了文獻［6］中句子的表層相似度與語義偏移量相似度相結合的方法，其中用到的詞語間相似度利用了文獻［12］的詞語間語義相似度的計算方法。

方法3是文中句子相似度計算方法，即對句子進行了分詞，詞性標注以及句法分析處理后，對句中的關鍵詞進行抽取以及加權處理，然后基于帶權路徑長度計算方法計算句子間的相似度。

文中是對搜索結果進行二次排序，為獲取更準確的信息，只對問句中的關鍵詞做了同義詞以及近義詞擴展處理。

對表2進行分析可知，方法1中從標題句6到標題句9與問句1的相似度均為0，這顯然是不合理的，因為從標題句6到標題句8中均含有問句中貢獻度最大的詞“電影”的同義詞，而標題句9則含有“兒童”的同義詞，方法3即文中方法用了關鍵詞的同義詞近義詞擴展的方法，使以上含同義詞近義詞的句子之間的相似度計算結果更合理。標題句2在語義上與問題句1的相似度更大，因為并沒有其他的限定詞語，而標題句3中就含有限定詞“經典”，所以標題句2與問句1的相似度應大于標題句3與問句1的相似度，而方法2中卻是相反的，同時在方法2中標題句9與問句1之間的語義相似度和標題句10與問句1之間的語義相似度太大，而實際上標題句10與問句之間幾乎沒有聯系，因此方法2是不符合實際的，文中方法則利用詞性標注以及句法分析對句子進行分析處理，并采用二叉樹帶全路徑長度計算方法對句子相似度進行計算使以上句子之間的語義相似度更符合人們的直觀感受，如標題句10與問句1之間的相似度就比較合理。由以上分析可以看出，文中提出的計算方法更符合實際，具有一定的實用性。

基于已處理的數據集對文中方法進行評測，評測結果如表3所示。在未對問句進行擴展時，檢索結果的查全率、查準率以及前30個檢索結果的查準率較低，而對問句進行擴展后，都有所提高，最后再用文中方法對檢索結果進行二次排序，在查全率不變的情況下檢索結果的查準率有所提高。這說明文中方法在保證信息檢索結果的查全率的情況下，能有效地提高信息檢索結果的查準率，是可行的。

表3 評測結果對比

4 結束語

句子相似度的計算在自然語言處理領域中起到了不可或缺的作用，在文本聚類、機器問答等領域也占有重要地位。文中在對問句進行分詞以及句法分析處理的基礎上，利用了二叉樹的帶權路徑長度的計算方法來計算問句與檢索內容的標題句間的相似度，對檢索結果進行了二次排序。由實驗結果可知，文中提出的句子相似度計算方法比較符合人們的主觀判斷，能夠很好地被運用到信息檢索中檢索結果的二次排序中去。在對句子處理方面文中運用到了句法分析系統，而句法分析系統分析句子結果的準確性和處理句子的速度都存在一些問題，因此文中在問句的處理上還存在一定的局限性。在下一步的工作中準備用其他的方法對問句中貢獻度大的詞進行提取。

［1］李立.中文信息檢索系統研究［D］.武漢:華中師范大學，2008:15-28.

［2］王品，黃廣源.信息檢索中的句子相似度計算［J］.計算機工程，2011，37(12):38-40.

［3］周法國，楊炳儒.句子相似度計算新方法及在問答系統中的應用［J］.計算機工程與應用，2008，44(1):165-167.

［4］呂學強，任飛亮，黃志丹，等.句子相似模型和最相似句子查找算法［J］.東北大學學報:自然科學版，2003，24(6):531-534.

［5］劉寶艷，林鴻飛，趙晶.基于改進編輯距離和依存文法的漢語句子相似度計算［J］.計算機應用與軟件，2008，25(7):33-34.

［6］程傳朋，吳志剛.一種基于知網的句子相似度計算方法［J］.計算機工程與科學，2012，34(2):172-175.

［7］劉宏哲.一種基于本體的句子相似度計算［J］.計算機科學，2013，40(1):251-256.

［8］LISA BALLEDTEROS，BRUCE CROFT W.Statistical methods for cross-language information retrieval［M］.Boston:Kluwer Academic Publisers，1998:23-40.

［9］CHE W X，LI Z H，LIU T.A Chinese language technology platform［C］//Proc of the Coling 2010，Beijing.2010:13-16.

［10］西南交通大學中文分詞系統［CP/OL］.［2013－12－25］.http://www.yebol.com.cn.

［11］王榮波，池哲儒，常寶寶，等.基于詞串力度及權值的漢語句子相似度衡量［J］.計算機工程，2005，31(13):142-144.

［12］夏天.漢語詞語語義相似度計算研究［J］.計算機工程，2007，33(6):191-193.