蘇金波 葉紅

摘要：Google，百度，MSN和其他一些工具提供了強大的Internet，桌面搜索功能，為用戶查找信息提供了便捷，但這些搜索工具并不關(guān)心數(shù)據(jù)本身的結(jié)構(gòu)和語義，搜索結(jié)果常有用戶不關(guān)心的垃圾數(shù)據(jù)，而一些有用的數(shù)據(jù)卻不能列出。該文探討了一種基于規(guī)則，將數(shù)據(jù)的結(jié)構(gòu)和語義考慮在內(nèi)的桌面搜索索引方法。該方法首先對原始數(shù)據(jù)進(jìn)行規(guī)范化，然后根據(jù)一系列的規(guī)則對規(guī)范化數(shù)據(jù)創(chuàng)建索引文件，通過該方法可獲得更好的搜索結(jié)果，而且該方法可通過擴展應(yīng)用到其他領(lǐng)域。

關(guān)鍵詞：規(guī)則；謂詞；桌面搜索；索引

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)07-1521-03

A Rule-based Method of Index in Desktop Search

SU Jin-bo, YE Hong

(Department of Computer Sci., Anhui Univ., Hefei 230039, China)

Abstract: Google, Baidu, Msn and other products provide users powerful way of searching for information on the Internet, desktop. But these facilities dont care the structure and semantics of data, the search results often include what users dont want,some data which users care can not be listed. This paper discusses a new method of index in desktop searching, it fully exploits the structure and semantics of data, this method firstly normalize the raw data,create index files based on some rules. With it, better search results can gained, and the method can be applied to other domain with some extension.

Key words: rule; predicate; desktop search; index

一些諸如Google，百度，MSN等搜索工具可以方便用戶在Internet，桌面上搜索自己感興趣的資料。這些工具一般是利用倒排文件，將用戶可能用到的關(guān)鍵字和相關(guān)文檔關(guān)聯(lián)起來，通過這些關(guān)鍵字用戶可以很快找到對應(yīng)的文檔。但是這種索引機制并不考慮數(shù)據(jù)本身的結(jié)構(gòu)和語義，所以在桌面搜索[1]中，搜索結(jié)果往往包含大量用戶不關(guān)心的文檔，或是一些該被找到的文檔卻被遺漏。本文討論了一種擴展的倒排索引機制，該機制基于規(guī)則對原始文檔進(jìn)行規(guī)范化，能夠把數(shù)據(jù)的結(jié)構(gòu)和語義[2]也考慮在內(nèi)。通過它可以獲得更好的搜索結(jié)果。

1問題舉例

以圖1會議室預(yù)定系統(tǒng)為例，當(dāng)邀請者創(chuàng)建一個預(yù)定，把被邀請者加入、填寫會議時間和地點后，系統(tǒng)自動生成一個邀請函并通過Email發(fā)送到被邀請者的郵箱中，假設(shè)邀請函以圖2的XML[3]文檔表示。本文討論的皆以XML表示，非XML表示的文檔都可以通過接口轉(zhuǎn)換成XML文檔。

圖1會議室預(yù)定系統(tǒng)

圖2邀請函原文檔

其中<被邀請者/>記錄在另一個XML文檔：

圖3被邀請者XML文檔

如果用不考慮數(shù)據(jù)的結(jié)構(gòu)和語義的傳統(tǒng)搜索算法[4]，用戶輸入“張三”進(jìn)行搜索，那么圖2所示的文檔不會被列出，因為它并沒包含“張三”這個關(guān)鍵字，但用戶卻希望能看到圖4所示的搜索結(jié)果（因為“張三”是被邀請者之一）。類似的，如果用戶輸入“402”關(guān)鍵字，圖2文檔就會被找出，因為包含了“402”這個關(guān)鍵字，但這個結(jié)果并不是用戶關(guān)心的（因為會議是在401室開的，而不是在402）。

圖4邀請函實例

圖4是圖2文檔的一個實例，其中的<被邀請者/>被“替換”成實際的值：“張三，李四”；會議室402也從文檔中刪去。類似的對原始文檔實例化的例子還可以舉出很多，比如“限定”條件（在某些條件下成立，某些條件下該被刪除）。

這個例子說明如果不考慮數(shù)據(jù)的結(jié)構(gòu)和語義，在桌面搜索中，一部分用戶想要的結(jié)果就會被漏掉，或者一些不需要的結(jié)果就會被搜出。為了提高桌面搜索結(jié)果的準(zhǔn)確性，本文接下來討論了一種擴展的索引機制。

2擴展算法

傳統(tǒng)的索引是基于原始數(shù)據(jù)創(chuàng)建倒排文件[5][6]的，為了能將數(shù)據(jù)的語法語義也考慮在內(nèi)，我們對傳統(tǒng)索引方法進(jìn)行擴展，首先基于一系列的規(guī)則，對原始文檔進(jìn)行變換，生成包含數(shù)據(jù)的結(jié)構(gòu)和語義信息的規(guī)范化文檔。然后基于規(guī)范化的文檔再生成倒排文件。整個擴展索引機制的結(jié)構(gòu)圖如圖5所示。

圖5擴展索引機制的結(jié)構(gòu)圖

規(guī)則是規(guī)范化的基礎(chǔ)，用以說明原始文檔該如何被規(guī)范化，規(guī)則以XSLT[7-8]和XQuery[9]表達(dá)式構(gòu)成。由于應(yīng)用程序的開發(fā)者和使用者最清楚原始數(shù)據(jù)的結(jié)構(gòu)和語義，規(guī)則的定義可由他們編寫完成。圖6是前面例子用到的兩個規(guī)則。在實際應(yīng)用中還可以對規(guī)則庫進(jìn)行修改和添加。

圖6“替換”規(guī)則

圖7“選擇”規(guī)則

match屬性用XPath[10-12]指出原始XML文檔哪些部分需要被應(yīng)用規(guī)則，action屬性指出規(guī)則的策略。不同的規(guī)則可以有不同的屬性，圖6中的value屬性指出被替換的值。下面對規(guī)范化和擴展索引的創(chuàng)建算法進(jìn)行描述。

2.1規(guī)范化

所謂的規(guī)范化就是根據(jù)規(guī)則，在原始數(shù)據(jù)的基礎(chǔ)上把所有可能的實例全部生成出來，如前面例子中由圖2生成圖4的過程。規(guī)范化過程分以下兩步：

1）構(gòu)造標(biāo)記表（d, R）(d：原始文檔，R：規(guī)則)

目的是用來標(biāo)記原始文檔中哪些元素必須被打上“select”和謂詞（predicate）標(biāo)記，其中predicate謂詞屬性是用來說明元素所受到的約束。

①對于匹配規(guī)則r∈R的每個節(jié)點n∈d，向表T中加入一條記錄t，使得t.Rule←r，t.Pattern←r.Pattern，t.NodeId←n。

②根據(jù)規(guī)則中的value屬性對節(jié)點n進(jìn)行求值，并設(shè)置t.KeyValue和t.Operator。前面的例子的標(biāo)記表如表1所示。

表1圖2對應(yīng)的標(biāo)記表

2）規(guī)范化原始文檔

掃描標(biāo)記表，如果是replace類型的規(guī)則，在t.NodeId指向的節(jié)點外加一個select節(jié)點，該節(jié)點的predicate屬性為t.Rule t.Operator t.KeyValue；如果是alternative規(guī)則，將滿足條件的option節(jié)點用t.KeyValue代替，其余的option節(jié)點全部刪除，規(guī)范化的文檔如圖9所示。對于其他規(guī)則，可以根據(jù)語義添加select和謂詞（predicate）屬性。

因為規(guī)則是以XSLT和XQuery表示，所以規(guī)范化過程可以由程序自動完成。具體見文獻(xiàn)[7-9]。

圖9規(guī)范化后的文檔

2.2索引創(chuàng)建

和傳統(tǒng)搜索索引創(chuàng)建方法類似，只是不再基于原始文檔，而是基于規(guī)范化后的文檔創(chuàng)建倒排文件，創(chuàng)建步驟如下:

1）如果關(guān)鍵字不在select元素內(nèi)，則把該關(guān)鍵字加到倒排文件中，且predicate設(shè)置為true（表明該關(guān)鍵字在任何條件下永真）.

2）如果關(guān)鍵字在select元素內(nèi)，則加在倒排文件中的predicate屬性值根據(jù)規(guī)則的約束來定，比如在圖2例子基礎(chǔ)上再加上一個約束條件：如果時間是上午（time<=12.00）用401會議室，如果是下午（time>12.00）用402會議室，那么倒排文件表如表2所示。

表2擴展的倒排文件

其中添加了Score這一列用來記錄該關(guān)鍵字出現(xiàn)的次數(shù)，也可以是其他一些信息，搜索結(jié)果可以根據(jù)score進(jìn)行排序。

搜索過程和傳統(tǒng)的搜索方法一樣，以給定的關(guān)鍵字，通過掃描倒排文件,如果找到相關(guān)記錄，根據(jù)predicate條件判斷是否為真，如果為真便可以找到規(guī)范化的文檔。因為這些規(guī)范化的文檔就是所有原始文檔可能生成的所有實例，所以通過這樣的索引機制可以給用戶提供更準(zhǔn)確的搜索結(jié)果。對于詳細(xì)的搜索過程，不是本文重點，可參考相關(guān)文獻(xiàn)[5-6]。

3結(jié)束語

傳統(tǒng)的桌面搜索方法不考慮文檔所包含的結(jié)構(gòu)和語義，搜索結(jié)果常帶有垃圾文檔，或是用戶關(guān)心的文檔卻未找到，本文對傳統(tǒng)桌面搜索索引進(jìn)行擴展，添加一系列規(guī)則，用以對原始文檔進(jìn)行規(guī)范化，基于這樣規(guī)范化的文檔構(gòu)建起來的倒排文件，包含原始文檔的結(jié)構(gòu)和語義，可以為用戶提供更好的搜索結(jié)果。這種索引機制還可以通過擴展應(yīng)用到其他領(lǐng)域。

參考文獻(xiàn):

[1]向凱全,王盼卿,陳軍廣,等.裝備領(lǐng)域中語義桌面上的個人主觀本體研究[J].計算機技術(shù)與發(fā)展,2011,21(8).

[2]鄧輝文.離散數(shù)學(xué)[M].北京:清華大學(xué)出版社,2010.

[3] W3C.Extensible Style sheet Language (XSL)[EB/OL].[2001-10-15].http://www.w3.org.

[4] Cormen T H.算法導(dǎo)論[M].北京:機械工業(yè)出版社,2006.

[5]王能斌.數(shù)據(jù)庫系統(tǒng)教程[M].北京:電子工業(yè)出版社,2002.

[6]數(shù)據(jù)結(jié)構(gòu)[EB/OL].http://www.xjife.edu.cn/teacher/wjj/DataStructure/web/wenjian/wenjian10.6.1.htm, 2002.

[7] XSLT 2.0 and XQuery 1.0 Serialization[EB/OL].Second Edition. [2010-12-14].http://www.w3.org/TR/2010/REC-xslt-xquery-serialization-20101214/.

[8]洪新華,夏群兵.XSLT在XML文檔中的應(yīng)用研究[J].電腦知識與技術(shù), 2009(5).

[9] Word Wide Web Consortium. XQuery 1.0 and XPath 2.0 Formal Semantics [EB/OL]. http://www.w3c.org/TR/query-semantics/, 2002.

[10] XML Path Language (XPath) 2.0[EB/OL].[2010-12-14].Second Edition.http://www.w3.org/TR/2010/REC-xpath20-20101214/.

[11]郭太飛,何潔月.歸納學(xué)習(xí)XPATH Web信息提取規(guī)則[J].計算機技術(shù)與發(fā)展, 2007,17(3).

[12] Deitel H M.Java Web Services for Experienced Programmers [M].北京:機械工業(yè)出版社,2003.