關(guān)鍵詞有序排列的全文檢索算法

楊 珺，畢忠勤，杜海舟

(上海電力學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200090)

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

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

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

針對(duì)上述問(wèn)題，文獻(xiàn)［1］提出將檢索關(guān)鍵詞映射為實(shí)例、概念或?qū)傩?，并設(shè)計(jì)了6種模板來(lái)匹配兩個(gè)關(guān)鍵詞的簡(jiǎn)單組合查詢，當(dāng)檢索關(guān)鍵詞多于兩個(gè)時(shí)，由于存在組合爆炸的可能性，可以使用啟發(fā)式方法來(lái)處理此種問(wèn)題;文獻(xiàn)［2］嘗試通過(guò)本體提供背景知識(shí)的方式將關(guān)鍵詞組合轉(zhuǎn)換為描述邏輯連接查詢;文獻(xiàn)［3］針對(duì)“標(biāo)引”提出語(yǔ)義樹(shù)模型，針對(duì)“相似度計(jì)算”提出了3個(gè)可計(jì)算的窗口模型來(lái)近似語(yǔ)義張量;文獻(xiàn)［4］在向量空間模型的基礎(chǔ)上提出了基于本體的檢索模型，將關(guān)鍵詞查詢映射為結(jié)構(gòu)查詢，同時(shí)還可以對(duì)檢索結(jié)果進(jìn)行排序.

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

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

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

1.1 正排索引與倒排索引

1.1.1 正排索引

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

(1)localId 表示一個(gè)文檔的局部編號(hào);

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

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

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

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

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

1.1.2 倒排索引

倒排索引是描述一個(gè)詞項(xiàng)集合元素和一個(gè)文檔集合元素對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)，記:

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

tj——第 j個(gè)詞項(xiàng)，j=1，2，…，m.

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

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

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

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

1.2 向量空間檢索模型

向量空間模型是近年來(lái)在文本檢索、自動(dòng)文摘、文本分類等領(lǐng)域廣泛使用的一種文本處理模型［7］.特別是在文本檢索領(lǐng)域，該模型對(duì)于文檔與查詢的相關(guān)度計(jì)算有較好的效果.

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

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

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

2 關(guān)鍵詞有序檢索方法

我們?cè)诨诘古潘饕拖蛄靠臻g檢索模型的全文檢索方法基礎(chǔ)上，加入了檢索預(yù)處理算法，即通過(guò)定義查詢步進(jìn)和文檔關(guān)鍵詞步進(jìn)(簡(jiǎn)稱文檔步進(jìn))，進(jìn)而給出位置匹配函數(shù)，使之能夠處理當(dāng)檢索結(jié)果與檢索詞組合順序相關(guān)時(shí)的狀況.

2.1 預(yù)處理算法

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

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)合索引的結(jié)果為{20，25，31}.

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

令 pi，pj，pe分別代表檢索關(guān)鍵詞 qi，qj，以及最后一個(gè)檢索關(guān)鍵詞在整個(gè)查詢中的位置，則相對(duì)查詢步進(jìn)定義為:

總體查詢步進(jìn)定義為:

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

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

設(shè)re為最后一個(gè)檢索關(guān)鍵詞在相對(duì)文檔中的位置，因此總體查詢步進(jìn)定義為:

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

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

此時(shí):

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

由于預(yù)處理的結(jié)果是一個(gè)序列，因此可使用二維數(shù)組來(lái)返回其結(jié)果.數(shù)組的每一行代表一個(gè)匹配到的文檔，數(shù)組的第1列存放文檔的編號(hào)，也就是正排索引中的localId，數(shù)組的第2列存放此文檔與檢索關(guān)鍵詞組合向量的Res值，在實(shí)際應(yīng)用中可根據(jù)具體編程語(yǔ)言的特點(diǎn)來(lái)選擇具體的數(shù)據(jù)結(jié)構(gòu).

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

2.2 預(yù)處理算法的改進(jìn)

2.2.1 擾動(dòng)詞的處理

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

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

此情況只是考慮了詞的匹配順序，可以保證檢索的效率，但是擾動(dòng)詞的具體含義也可能會(huì)對(duì)檢索帶來(lái)一定的影響.

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

對(duì)于“小張可能喜歡小王”:

在此情況下需要一個(gè)本體庫(kù)或語(yǔ)料庫(kù)，例如howNet等的支持，而且如何確定含義的增強(qiáng)權(quán)值或減弱權(quán)值也需要考慮.

對(duì)于更加復(fù)雜的情況，例如:“小張可能非常喜歡小王”，我們可通過(guò)本體庫(kù)或語(yǔ)料庫(kù)的支持，根據(jù)其具體含義，遞歸地?cái)U(kuò)充檢索匹配公式進(jìn)行計(jì)算.

2.2.2 文檔中匹配到的多個(gè)檢索詞的處理

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

2.3 檢索方法的總體描述

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

(1)對(duì)查詢關(guān)鍵詞分詞，使用邏輯表達(dá)式來(lái)表示查詢，例如“小張喜歡小王”可以表示為“小張”AND“喜歡”AND“小王”;

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

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

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

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

3 實(shí)例驗(yàn)證

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

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

(2)小王喜歡小張;

(3)小張和小王都喜歡戶外運(yùn)動(dòng).

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

［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］ 趙軍，金千里，徐波.面向文本檢索的語(yǔ)義計(jì)算［J］.計(jì)算機(jī)學(xué)報(bào)，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］ 梁斌.走進(jìn)搜索引擎［M］.北京:電子工業(yè)出版社，2007:132-140.

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

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