楊 珺，畢忠勤，杜海舟

(上海電力學院計算機科學與技術學院，上海 200090)

全文檢索技術細化了信息檢索的力度，提供了多角度、多側面的信息檢索體驗.當前的檢索模型要求在輸入一組檢索詞組合的情況下，能夠返回與之相關的文檔，常用的檢索模型有布爾模型和向量空間模型.

布爾模型是通過采用AND，OR，NOT等邏輯運算符，將多個檢索關鍵詞組合成一個邏輯表達式，繼而通過布爾運算進行檢索的簡單匹配模型.此模型的缺點主要在于沒有考慮文檔和檢索關鍵詞的相關性問題，沒有區(qū)分檢索關鍵詞的權重問題，導致查詢結果與用戶的意圖差距較大.

向量空間模型使用了一個由關鍵詞構成的文檔向量 Di={d1i，d2i，...，dni}來表示文檔集中的文檔，此模型存在的主要缺陷就是無法解決某一詞的同義詞和近義詞對其的干擾，同時使用n維向量來表示文檔和檢索詞組合，采用內積來計算二者之間的相似度.

針對上述問題，文獻［1］提出將檢索關鍵詞映射為實例、概念或屬性，并設計了6種模板來匹配兩個關鍵詞的簡單組合查詢，當檢索關鍵詞多于兩個時，由于存在組合爆炸的可能性，可以使用啟發(fā)式方法來處理此種問題;文獻［2］嘗試通過本體提供背景知識的方式將關鍵詞組合轉換為描述邏輯連接查詢;文獻［3］針對“標引”提出語義樹模型，針對“相似度計算”提出了3個可計算的窗口模型來近似語義張量;文獻［4］在向量空間模型的基礎上提出了基于本體的檢索模型，將關鍵詞查詢映射為結構查詢，同時還可以對檢索結果進行排序.

本文首先分析了正排索引［5］和倒排索引［6］的適用范圍及缺陷，針對各檢索關鍵詞在整個查詢中的權重和由檢索詞組合順序不同而導致暗含的語義存在差異的問題，在基于倒排索引和向量空間檢索模型的基礎上，給出了與檢索詞排列順序相關的全文檢索方法，以提高檢索質量.

1 基于倒排索引和向量空間檢索模型的全文檢索算法

現(xiàn)有的檢索算法中有兩個重要問題，即索引的建立和相關度的匹配.目前廣泛使用的是基于倒排的索引系統(tǒng)和基于向量空間模型的查詢系統(tǒng).

1.1 正排索引與倒排索引

1.1.1 正排索引

正排索引也稱為“前向索引”，是創(chuàng)建倒排索引的基礎，其字段如下:

(1)localId 表示一個文檔的局部編號;

(2)wordId 表示文檔分詞后的詞的編號，也可稱為“索引詞編號”;

(3)hitList 表示某個索引詞在文檔中出現(xiàn)的位置，即對于正文的偏移量，這是一個變長序列，記錄關鍵詞在文檔中出現(xiàn)的所有位置，為了壓縮存儲的需要，此序列一般采用差分序列的方式存儲;

(4)nHits 表示某個索引詞在文檔中出現(xiàn)的次數(shù)，由于hitList是變長的，因此需要nHits這個字段標記其長度，這樣才能讀出全部的正排索引數(shù)據(jù).

從本質上說，正排索引以文檔編號為視角看待索引詞，也就是通過文檔編號去尋找索引詞.任意給出一個文檔編號，就能夠知道它包含了哪些索引詞、這些索引詞分別出現(xiàn)的次數(shù)，以及索引詞出現(xiàn)的位置.然而全文索引是通過關鍵詞而不是通過文檔編號來檢索的，因此正排索引不能滿足全文檢索的要求.

雖然正排索引不能滿足全文檢索的需要，但是正排索引為創(chuàng)建倒排索引創(chuàng)造了有利條件，它是計算倒排索引不可缺少的一環(huán)，也是我們改進算法的基礎.

1.1.2 倒排索引

倒排索引是描述一個詞項集合元素和一個文檔集合元素對應關系的數(shù)據(jù)結構，記:

式中:di——第 i個文檔，i=1，2，…，n;

tj——第 j個詞項，j=1，2，…，m.

當以“文檔”為出發(fā)點時，我們可以說di中包含哪些tj，或者某一個tj在di中出現(xiàn)了多少次，而“倒排文件”直接給出的是一個tj出現(xiàn)在哪些di中，進而還可以給出它在某一個dj中出現(xiàn)在哪些位置(含多少次).用PL(tj)表示tj出現(xiàn)于其中的文檔記錄的集合，稱為對應于tj的倒排表.

倒排文件分為兩部分:一是由不同詞項組成的索引，稱為詞匯表;二是由每個詞項出現(xiàn)過的文檔集合組成，稱為記錄文件，每個詞項對應部分稱為倒排表，也稱為記錄表，可以通過詞匯表訪問.

在倒排文件中，每個不同的詞會出現(xiàn)在一個詞典中，這個詞典除了包含每個詞外，也包含這個詞對應的倒排表的指針.每一個文檔都有唯一的名字，可為他們賦予連續(xù)的不重復的數(shù)字.

倒排索引是現(xiàn)代大規(guī)模搜索的核心，通過它可以大大提高檢索系統(tǒng)的響應時間和查詢的吞吐量.

1.2 向量空間檢索模型

向量空間模型是近年來在文本檢索、自動文摘、文本分類等領域廣泛使用的一種文本處理模型［7］.特別是在文本檢索領域，該模型對于文檔與查詢的相關度計算有較好的效果.

在向量空間模型中，文檔和查詢均被看作是由索引項構成的向量.其中文檔 Di={d1，j，d2，j，…，dt，i}，i表示文檔集中的第 i個文檔，t表示某個文檔含有 t個詞項.查詢 Q={d1，q，d2，q，…，dt，q}，t表示在查詢q中含有t個詞項.在權重方面使用的計算方法為TF-IDF方法，通過統(tǒng)計特征項的詞頻f值和逆向文本詞頻fid值形成權重計算公式.

文檔Di和查詢Q之間存在的相似程度一般通過計算兩個向量的夾角余弦值來衡量.據(jù)此可采用以上兩個向量的cos值作為相似度:

此相似度值可以看作是文檔和檢索詞之間的相關程度，從而可以優(yōu)先檢索那些與檢索詞相似度較大的文檔.

2 關鍵詞有序檢索方法

我們在基于倒排索引和向量空間檢索模型的全文檢索方法基礎上，加入了檢索預處理算法，即通過定義查詢步進和文檔關鍵詞步進(簡稱文檔步進)，進而給出位置匹配函數(shù)，使之能夠處理當檢索結果與檢索詞組合順序相關時的狀況.

2.1 預處理算法

本文通過實例來給出相關的定義.首先，通過倒排文件來找到同時出現(xiàn)所有檢索關鍵詞的文檔，即使用聯(lián)合索引.假設檢索詞為“小張喜歡小王”，通過分詞可得檢索關鍵詞向量為{“小張”，“喜歡”，“小王”}，索引結果分別為:

I小張={1，5，9，14，20，23，25，30，31，33}

I喜歡={2，6，8，15，20，25，27，31，35}

I小王={3，7，12，14，20，24，25，27，31，36}

聯(lián)合索引的結果為{20，25，31}.

然后，通過正排索引找出相關檢索關鍵詞在文檔中的位置，并做如下定義:

令 pi，pj，pe分別代表檢索關鍵詞 qi，qj，以及最后一個檢索關鍵詞在整個查詢中的位置，則相對查詢步進定義為:

總體查詢步進定義為:

以給出的查詢“小張喜歡小王”為例:“小張”相對于“喜歡”的查詢步進為step小張，喜歡=1-2=-1，而“小王”相對于“喜歡”的查詢步進為step喜歡，小王=3-2=1;而檢索的總體查詢步進為stepall=3-1=2.

類似的，令 ri，rj分別代表檢索關鍵詞 qi，qj在相關文檔中的位置，則相對文檔查詢步進定義為:

設re為最后一個檢索關鍵詞在相對文檔中的位置，因此總體查詢步進定義為:

經(jīng)由上述定義，通過對大量文檔的統(tǒng)計分析發(fā)現(xiàn):文檔和查詢之間的相似度與兩個或多個查詢關鍵詞在文檔中的步進成反比，同時又受到總體查詢步進的影響，總體查詢步進與相似度也成反比.由此我們定義位置匹配函數(shù)為:

只取Res＞0的情況返回結果，如果出現(xiàn)如下情況:

此時:

則Res=100%，我們稱其為完全匹配，也就是說在文檔中檢索到了與檢索關鍵詞組合完全一致的結果.

由于預處理的結果是一個序列，因此可使用二維數(shù)組來返回其結果.數(shù)組的每一行代表一個匹配到的文檔，數(shù)組的第1列存放文檔的編號，也就是正排索引中的localId，數(shù)組的第2列存放此文檔與檢索關鍵詞組合向量的Res值，在實際應用中可根據(jù)具體編程語言的特點來選擇具體的數(shù)據(jù)結構.

以Java為例:返回的值可以是一個ArrayList，存儲所有經(jīng)過預處理的文檔，其中的每個元素具體可以是一個長度為2的一維數(shù)組，數(shù)組的第1個元素是文檔的localId，第2個元素是分詞后的查詢與此文檔的Res值，供后續(xù)階段使用.

2.2 預處理算法的改進

2.2.1 擾動詞的處理

如果查詢文檔中存在查詢關鍵詞的擾動詞，比如說查詢文檔a中有“小張非常喜歡小王”，文檔b中有“小張可能喜歡小王”;那么文檔a中的“非?！焙臀臋nb中的“可能”就是查詢擾動詞，如出現(xiàn)這種情況我們先粗略地采用以下兩種方式處理.

(1)將其作為同樣的地位，此情況下兩個文檔與查詢的語義匹配值相同:

此情況只是考慮了詞的匹配順序，可以保證檢索的效率，但是擾動詞的具體含義也可能會對檢索帶來一定的影響.

(2)根據(jù)擾動詞含義類型，將擾動詞分為正向含義加強類型和逆向含義加強類型，并分別賦予正向增強權值和逆向增強權值(亦即正向減弱權值)，這兩個值互為相對數(shù).例如將“非?！笨醋魇钦蚝x加強類型詞，把“可能”看作是逆向含義加強類型詞，在獲取肯定查詢時分別賦予權值α和-α，(0＜＜1)，由此可得，對于“小張非常喜歡小王”:

對于“小張可能喜歡小王”:

在此情況下需要一個本體庫或語料庫，例如howNet等的支持，而且如何確定含義的增強權值或減弱權值也需要考慮.

對于更加復雜的情況，例如:“小張可能非常喜歡小王”，我們可通過本體庫或語料庫的支持，根據(jù)其具體含義，遞歸地擴充檢索匹配公式進行計算.

2.2.2 文檔中匹配到的多個檢索詞的處理

檢索詞在文檔中出現(xiàn)的位置不可能只有一處，而且正排索引中記錄了各個關鍵詞(索引詞)在文檔中的位置，因此可以利用正排索引來查找與關鍵詞順序相關且關鍵詞間步進最小的檢索詞的位置進行預處理.

2.3 檢索方法的總體描述

檢索算法主要是在傳統(tǒng)搜索引擎算法的基礎上增加了預處理的步驟:

(1)對查詢關鍵詞分詞，使用邏輯表達式來表示查詢，例如“小張喜歡小王”可以表示為“小張”AND“喜歡”AND“小王”;

(2)采用布爾模型的方法得到結果文檔列表;

(3)使用關鍵詞有序預處理算法對上一步驟中得到的文檔進行篩選，取Res值大于某一閾值的文檔;

(4)將預處理過的文檔向量化，并計算與向量化查詢之間的向量相似度，再計算此向量相似度與對應文檔Res值的乘積作為文檔與查詢之間的相似度;

(5)按照最終相似度排序輸出檢索結果.

3 實例驗證

仍以“小張喜歡小王”為例，假設通過索引從文檔集中匹配到的文檔中分別包含如下內容:

(1)小張非常喜歡小王;

(2)小王喜歡小張;

(3)小張和小王都喜歡戶外運動.

如果采用傳統(tǒng)的方法，這3個文檔均可被檢索出，但因次序的順序組合不相符導致得出的結果不理想.采用關鍵詞有序檢索方法需經(jīng)過如下預處理:

(1)對于包含“小張非常喜歡小王”的文檔，dstep小張，喜歡=2，dstep喜歡，小王=1，qstepall=3，利用式(6)可得Res=50%;

(2)對于包含“小王喜歡小張”的文檔，dstep小張，喜歡=-1，dstep喜歡，小王=-1，qstepall=2，利用式(6)可得Res=-100%;

(3)對于包含“小張和小王都喜歡戶外運動”的文檔，dstep小張，喜歡=-4，dstep喜歡，小王=-2，qstepall=4，利用式(6)可得 Res=-37.5%.

可以設置閾值為零，經(jīng)過預處理，包含“小王喜歡小張”和“小張和小王都喜歡戶外運動”的文檔被過濾掉，不進入檢索階段.

由此可見，通過給出的預處理算法可以優(yōu)化過濾與檢索期望相差較大的文檔，最終可以提高檢索結果的質量.

4 結語

本文提出了一種與檢索關鍵詞組合順序相關的全文檢索方法:考慮各檢索關鍵詞在整個查詢中的權重，以及由檢索詞組合順序不同而導致暗含的語義存在差異的問題，按照一定的規(guī)則對索引結果進行處理，約簡掉不相關的文檔，從而提高了檢索結果的質量.今后我們將使用本體或語料庫來支撐預處理算法，以期取得更好的結果.

［1］ LEI Yuang，UREN Victoria，MOTTA Enrico.SemSearch:a search engine for the semantic web［C］∥15th International Conference，EKAW，2006:222-237.

［2］ TRAN Thanh，CIMIANO Philipp，RUDOLPH Sebastian，et al.Ontology-based interpretation of keywords for semantic search［C］∥6th International Semantic Web Conference 2nd Asian Semantic Web Conference，2007:523-536.

［3］ 趙軍，金千里，徐波.面向文本檢索的語義計算［J］.計算機學報，2005(12):2 068-2 078.

［4］ VALLET David，F(xiàn)ERNONDEZ Miriam，CASTELLS Pablo.An ontology-based information retrieval model［C］∥2nd European Semantic Web Conference，2005:455-471.

［5］ 梁斌.走進搜索引擎［M］.北京:電子工業(yè)出版社，2007:132-140.

［6］ 李曉明，閆宏飛，王繼民.搜索引擎——原理、技術與系統(tǒng)［M］.北京:科學出版社，2005:214-217.

［7］ 宗成慶.統(tǒng)計自然語言理解［M］.北京:清華大學出版社，2008:92-97.