基于改進(jìn)編輯距離的中文相似句子檢索①

1、基于改進(jìn)編輯距離的中文相似句子檢索 車萬翔 劉挺 秦兵 李生(哈爾濱工業(yè)大學(xué)計算機(jī)學(xué)院信息檢索研究室 哈爾濱 150001摘要 中文相似句子檢索的方法在基于實例的機(jī)器翻譯等中文信息處理領(lǐng)域, 具有非常廣泛 的應(yīng)用背景。 本文提出的基于改進(jìn)編輯距離的中文相似句子檢索方法, 在使用信息檢索技術(shù) 提高檢索效率的同時, 以普通編輯距離算法為基礎(chǔ), 加入了詞匯的語義信息, 使之更加符合 中文句子相似度計算的要求。改進(jìn)編輯距離與單純基于語義辭典計算句子相似度的方法相 比, 具有便于擴(kuò)展, 準(zhǔn)確率高等優(yōu)點。 在基于大規(guī)模雙語句對檢索的英文輔助寫作系統(tǒng)中使 用該算法進(jìn)行中文句子檢索,最后獲得了 81.33%的

2、查準(zhǔn)率和 95.31%的查全率。關(guān)鍵詞:改進(jìn)編輯距離、相似句子檢索、英文輔助寫作0 引言相似句子檢索, 在自然語言處理領(lǐng)域具 有非常廣泛的應(yīng)用背景, 如信息過濾技術(shù)中 的句子模糊匹配, 基于實例機(jī)器翻譯的原語 言檢索, 自動問答技術(shù)中常問問題集的檢索 以及問題與答案的匹配, 基于雙語語料庫的 英文輔助寫作等。因此長期以來,相似句子 檢索問題,一直為人們所熱衷。目前句子相似度計算一般分為三個等 級 1,分別為語法相似度、語義相似度和語 用相似度。計算句子之間的語用相似度,一 直是人們的目標(biāo), 但是其計算具有相當(dāng)?shù)碾y 度, 效果還不盡如人意。 而在一般的應(yīng)用中, 只計算句子的語義相似度就能夠達(dá)到我

3、們 的需要。句子的語義相似,指的是兩個句子 之間結(jié)構(gòu)類似并且詞匯使用同義或者近義 詞代替。例如:“我喜歡吃蘋果”與“我愛 吃香蕉”就是一對語義相似的句子。目前對句子語義相似度計算的研究方 法主要有:基于相同詞匯的方法 1、使用語義詞典的方法 23、使用編輯距離 4的方法,以及基于統(tǒng)計的方法 5等。其中, 基于相同詞匯的方法有很明顯的局限性, 對 于同義詞之間的替換則無能為力。 而使用語 義詞典的方法,可以很好的解決這一問題, 但是單純的使用語義詞典的方法, 并沒有考 慮到句子內(nèi)部的結(jié)構(gòu)和詞語之間的相互作 用關(guān)系,準(zhǔn)確率不高。編輯距離通常被用于句子的快速模糊 匹配領(lǐng)域,但是其規(guī)定的編輯操作不夠靈

4、 活,也沒有考慮詞語的同義替換。最后基于 統(tǒng)計的方法,需要構(gòu)造大量的訓(xùn)練語料,工 作量是十分巨大的, 而且還存在著數(shù)據(jù)稀疏 的問題。我們所提出的改進(jìn)編輯距離的方法, 吸 取了基于語義詞典的方法和編輯距離方法 的優(yōu)點,同時克服了它們的一些不足。與普 通編輯距離算法不同, 改進(jìn)編輯距離方法同 時使用了 HowNet 6和同義詞詞林 7兩種 語義資源,計算詞匯之間的語義距離,同時 賦予不同編輯操作不同的權(quán)重, 在不用經(jīng)過 詞義消歧和句法分析的情況下, 兼顧了詞匯 的順序和語義等信息,最終獲得了 81.33%的查準(zhǔn)率和 95.31%的查全率。本文的第 1部分描述了英文輔助寫作系統(tǒng)框架以及各 個模塊的算

5、法。第 2部分給出了測試結(jié)果。 第 3部分討論該系統(tǒng)的優(yōu)點和缺點。 第 4部 分給出了最后的結(jié)論。1.相似句子檢索863計劃(2002AA147020-11、國家自然科學(xué)基金(60203020資助項目。 男, 1980年生,博士生;研究方向為自然語言處理,信息檢索;聯(lián)系人。相似句子檢索過程如圖 1所示。 核心的相似句子檢索算法由候選句子 粗匹配和句子相似度計算兩部分組成。其 中, 候選句子粗匹配模塊首先到句庫中找到 可能與輸入為相似句的候選句子, 目的是提 高檢索效率。 句子相似度計算模塊將每一個 候選句子與輸入句進(jìn)行仔細(xì)的相似度計算, 并按照相似度的大小排序, 獲得最終的輸出 結(jié)果。1.1候

6、選句子粗匹配候選句子粗匹配由詞擴(kuò)展和快速檢索 兩個子部分構(gòu)成。首先為了獲得較高的召回率, 必須對分 詞以后的各個詞匯進(jìn)行適當(dāng)?shù)耐x詞擴(kuò)展。 在此,對同義詞的定義即不能太寬泛,又不 能太嚴(yán)格。如果太寬泛,將檢索到許多無關(guān) 的句子,降低了系統(tǒng)的準(zhǔn)確率和效率;而如 果太嚴(yán)格,又可能漏掉許多有用的句子,降 低了系統(tǒng)的召回率。在此使用 HowNet 語義辭典作為同義詞 擴(kuò)展的資源。 HowNet 中同義詞的定義為具 有 相 同 的 英 語 譯 文 (W_E 和 語 義 定 義 (DEF 的詞匯。例如“我”和“俺” ,簡 化詞條如下:NO.=085498 W_C=我W_E=IDEF=firstPerson

7、|我 NO.=000701 W_C=俺W_E=IDEF=firstPerson|我可見, “我”和“俺”具有相同的英語 譯 文 (W_E “ I ” 和 語 義 定 義 (DEF “ firstPerson|我” , 是一對同義詞。 在表 1中, 我們給出了使用 HowNet 進(jìn)行詞擴(kuò)展的一些 例子。從中可以看出,使用 HowNet 進(jìn)行詞 的擴(kuò)展,效果是比較理想的。表 1. HowNet進(jìn)行詞擴(kuò)展示例 原詞 擴(kuò)展詞俺 本人 鄙人 我 吾俺們 我方 我們 吾 吾儕 咱 咱們 按 按捺 把持 扼制 管束 收 束 壓 壓制 抑制 制 制約 羈 按鍵 按鈕 電鍵其次,為提高系統(tǒng)的效率,首先對整個 語

8、料庫進(jìn)行初步的篩選, 確定數(shù)量不多但有 可能與用戶的需求相似的候選句, 然后對這 些候選句進(jìn)行精確的語義相似度計算, 得出 最終的結(jié)果。選擇候選句的依據(jù)是, 如果一個句子中 與用戶的需求相同或同義的詞越多, 越有可 能與用戶的需求相匹配,即權(quán)重越大。我們 采用信息檢索中常用的倒排文檔索引 8的 方法進(jìn)行檢索。在此, 并不需要對用戶輸入句子中的詞 進(jìn)行詞義消歧, 而直接對所有擴(kuò)展后的詞進(jìn) 行檢索。這是由于輸入的詞并非孤立,當(dāng)與 其余的詞共同檢索的時候, 能達(dá)到消歧的目 的。以“打”為例,當(dāng)輸入“打毛衣”時, “打”被擴(kuò)展為“打擊” , “編織”等。一個 句子中同時含有“編織”和“毛衣”的可能 性

9、很大,而“打擊”和“毛衣”幾乎不可能 同時出現(xiàn)在一個句子中。 于是, 含有 “編織” 和“毛衣”的句子更容易成為候選句。按照 句子權(quán)重由大到小的順序,我們選擇前 100個句子作為候選句。1.2語義相似度計算本文采用改進(jìn)編輯距離的算法計算句 子之間的語義相似度。 在介紹改進(jìn)編輯距離 的算法之前, 首先介紹兩個句子之間的編輯 距離以及如何進(jìn)行計算。編輯距離指從一個以字為單位的句子 變?yōu)榱硪粋€以字為單位的句子所需要最小 的編輯操作個數(shù)。 編輯操作共有 “插入” 、 “ 刪 除”和“替換”三種。圖 2(a顯示了“愛吃 蘋果”與“喜歡吃香蕉”之間的編輯距離為 4,如四條虛線所顯示。從該計算過程可以看出,

10、 單純使用以字 為單位編輯距離的方法, 計算出的語義距離 和實際情況是有很大的出入的。首先,編輯 距離算法以字為基本計算單位,而在漢語 中,單個的字往往是不具備意義的。例如上 面的“蘋” 、 “果”等字,并不能反映其所合 成詞的意義。其次,詞語之間的替換操作的 代價并非都是相同的。例如, “愛”被“喜 歡”替換,代價不應(yīng)該很大。最后,如果在 被檢索句子或短語中間加入為數(shù)不多的詞, 語義也不會有太大改變。例如“愛吃蘋果” 與“愛吃甜蘋果”就非常相似。 (a編輯距離的 (b改進(jìn)編輯距離 圖 2. 編輯距離與改進(jìn)編輯距離的比較基于以上的觀點, 我們提出了改進(jìn)編輯 距離算法,即以詞匯為基本的計算單位,

11、同 時以 HowNet 和同義詞詞林作為語義距 離的計算資源,并減小插入操作的代價。HowNet 定義的同義詞如前所述。下面 介紹如何使用同義詞詞林進(jìn)行語義距離 計算。在同義詞詞林中,將詞的詞義分為 大、中、小類描述了一個由上到下,由寬泛 概念到具體詞義的語義分類體系, 并將所收 的詞按詞義分門別類組織在其中。于是,每 個漢語詞都按照其語義, 賦予了一個或多個 3位的語義代碼,與此分類體系相對應(yīng)的是 一個詞義的編碼體系,描述如下: <詞義編碼 >:= <大類 ><中類 ><小類 ><大類 >:= <大寫英文字母 > <

12、;中類 >:= <小寫英文字母 > <小類 >:= <數(shù)字 ><數(shù)字 >例如:“蘋果” Bh07, “香蕉” Bh07, “西 紅柿” Bh06,。則 A, B兩詞之間的語 義距離為:, (min , (, b a dist B A Dist b a B=其中, A , B 分別為 A , B 兩詞具有語義的集合,語義 a , b 之間的距離為:4(2 , (n b a dist =其中 n 為它們之間的語義代碼從第 n 類 開始不同,全部相同語義距離為 0?？梢?Dist (蘋果, 香蕉 =0, Dist (蘋果, 西紅柿 =2。 這種代

13、數(shù)操作要較之使用 HowNet 計算語義 相似度方便、快捷的多。在此,也沒有進(jìn)行詞義消歧工作,而使 用兩個詞之間的最短語義距離作為它們之 間的語義距離。 這是因為我們在候選句子粗 匹配時, 檢索到的句子中的詞與用戶輸入句 中的詞具有相似的語義, 起到了詞義消歧的 目的。表 2規(guī)定了詞“ A ”與“ B ”進(jìn)行各種 編輯操作后編輯距離由小到大改變的順序, 其中, “ *”代表 1至 4個詞, “ A ”與“ B ” 為用戶輸入的兩個連續(xù)的詞, X' 為 HowNet 定義的 X 的同義詞, X'' 為同義詞詞林 定義的 X 的近義詞。表 2. 編輯距離改變的次序級別模式據(jù)

14、此, 我們可以定義改進(jìn)編輯距離計算 語義相似度方法中各種編輯操作的代價, 如 表 3所示,其中“ Æ”代表替換操作。 表 3. 改進(jìn)編輯距離編輯操作代價定義編輯操作 操作代價A Æ A 0 插入 A Æ A 0.4A Æ ADist (A, A/10 + 0.5其它根據(jù)以上對編輯距離的重新定義, “愛 吃蘋果”與“喜歡吃香蕉”之間的改進(jìn)編輯 距離計算如圖 2(b所示,其中“愛” Æ“喜歡”代價為 0.5, “蘋果” Æ“香蕉”代價 為 0.7。最后改進(jìn)編輯距離結(jié)果為 1.2,要較 之普通編輯距離計算的距離 4,更符合實際 情況。與計算

15、普通的編輯距離相同, 也使用動 態(tài)規(guī)劃算法計算改進(jìn)編輯距離。 圖 3為計算 兩個句子 S1與 S2改進(jìn)編輯距離的算法。 圖 3. 改進(jìn)編輯距離算法最后, 經(jīng)快速檢索步驟檢索出來的每個 句子都與用戶輸入的句子計算出改進(jìn)編輯 距離,然后按照由小到大的順序進(jìn)行排列, 取出前幾個作為最終的結(jié)果。 本文選擇前 10個結(jié)果。2.測試結(jié)果在現(xiàn)今機(jī)器翻譯效果不令人滿意的情 況下,輔助寫作系統(tǒng)逐漸引起了人們的重 視。我們使用基于相似度的句子檢索技術(shù), 以大規(guī)模的雙語句對語料庫為資源建立的 英文輔助寫作系統(tǒng), 容許用戶輸入中文整句 或者短語, 系統(tǒng)在雙語句對庫中快速的檢索 與之相似的中文句子, 對應(yīng)給出這些句子的

16、 英語翻譯。 具有翻譯準(zhǔn)確, 示例性強(qiáng)等優(yōu)點。 并且隨著收集的雙語語料庫的增加, 覆蓋面 的擴(kuò)大,輔助寫作的效果也會越來越好。目 前,我們收集的雙語句對已達(dá)到 25萬對。 英文輔助寫作系統(tǒng)首先將用戶輸入的 中文整句或者短語分成單獨(dú)的詞匯。在此, 我們采用最大概率分詞算法 9。由于輸入中 一般不會有未登錄詞, 因此采用最大概率分 詞算法即可達(dá)到 95%以上的準(zhǔn)確率, 足以滿 足系統(tǒng)的要求。我 們 采 用 國 際 上 通 用 的 MMR(Mean Reciprocal Rank評分機(jī)制對算法進(jìn)行評價, 即第一個結(jié)果匹配,分?jǐn)?shù)為 1,第二個匹配 分?jǐn)?shù)為 0.5, 第 n 個匹配分?jǐn)?shù)為 1/n, 如果

17、沒 有匹配的句子分?jǐn)?shù)為 0。最終的分?jǐn)?shù)為所有 得分之和。我們隨機(jī)測試了 150個句子或短語, 使 用全部 25萬句對雙語語料庫,最終的平均 分?jǐn)?shù)為:1.254。 其中 122句輸入能夠找到相 匹配的結(jié)果。 在沒有給出相應(yīng)匹配結(jié)果的 28個測試句子中,有 22個是在語料庫中就沒 有相匹配的中文句子, 6個是系統(tǒng)沒有給出 相匹配的正確句子。在表 4中,列出了一些 系統(tǒng)輸入和輸出的最終結(jié)果。表 4. 系統(tǒng)輸入輸出結(jié)果示例用戶需求 系統(tǒng)輸出屬于那種人他是那種隨波逐流的人。 He is the kind of person who swim with the tide.同那種人打交道得隨機(jī)應(yīng)變。 abo

18、ut you when you're dealing with a man like that.擠進(jìn)了大禮堂大家擁進(jìn)了房間。Everyone piled into the room. 人們一起擠進(jìn)了一個小房間。 People were packed together in a small room.同時, 我們又將基于改進(jìn)編輯距離的中 文相似句子檢索方法與單純基于語義辭典 的方法進(jìn)行比較。比較結(jié)果如表 5所示。其 中,查準(zhǔn)率 P 和查全率 R 的定義如下所示:測試句子數(shù)含有相匹配的句子數(shù)=P子數(shù) 語料庫中有相匹配的句含有相匹配的句子數(shù) =R可以看到, 改進(jìn)編輯距離的方法比基于 語義詞典

19、的方法在輔助寫作系統(tǒng)中, 取得了 更好的效果。 基于語義詞典的方法除了進(jìn)行 語義距離的計算過程中使用單純的語義詞典進(jìn)行語義距離的計算外, 其余步驟與改進(jìn) 編輯距離的方法完全相同。另外, 我們建立的英文輔助寫作在線演 示系統(tǒng) , 目前已經(jīng)收集了超過 5000個真實 有效的翻譯查詢。經(jīng)過分析可知,其中主要 的查詢?yōu)槎陶Z和短句, 抽樣檢查系統(tǒng)的查準(zhǔn) 率在 80%以上。表 6. 改進(jìn)編輯距離的方法與基于語義詞典 的方法比較結(jié)果方法 改進(jìn)編輯距離基于語義詞 典的方法測試句子數(shù)含有正確匹配句子數(shù)系統(tǒng)沒有給出正確匹配的句子數(shù)語料庫中沒有相匹配的句子數(shù)查準(zhǔn)率 P查全率 R3.討論以上測試結(jié)果說明, 在英文輔助

20、寫作系 統(tǒng)中, 使用改進(jìn)的編輯距離進(jìn)行中文相似句 子檢索取得了較為理想的效果, 查準(zhǔn)率達(dá)到 了 81.33%。對匹配不正確的例子進(jìn)行分析可知, 該 方法目前的問題是如果用戶需求的句子較 長,就很難找到與之完全匹配的句子,例如 輸入 “順利到達(dá)職場生涯的頂峰” 與輸出 “他 當(dāng)選為總統(tǒng)是他職業(yè)生涯的頂峰” ,雖然匹 配了后半部分,但是前面的“順利到達(dá)”并 沒有體現(xiàn)出來, 這就需要對句子進(jìn)行恰當(dāng)?shù)?分割,然后分別查詢。通過使用改進(jìn)編輯距離的方法與基于 語義的方法相比較可知, 改進(jìn)編輯距離的方 法考慮了較多的詞匯順序以及距離的信息, 例如對于輸入句子S input =“匆匆忙忙交給她”改進(jìn)編輯距離方法首選結(jié)果為:S edit =“她急忙把孩子交給她妹妹照管”而基于語義方法首選結(jié)果為:S sem =“她就 匆匆忙忙 挑了一件店里最貴重的衣服,把它 交給 售貨員,此人為 她 盡快包好”雖然 S sem 與 S input 中所有的詞都匹配,可是并非最好的結(jié)果,反而是