蘇金波 葉紅

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

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

中圖分類號：TP393文獻標識碼：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，桌面上搜索自己感興趣的資料。這些工具一般是利用倒排文件，將用戶可能用到的關鍵字和相關文檔關聯(lián)起來，通過這些關鍵字用戶可以很快找到對應的文檔。但是這種索引機制并不考慮數(shù)據(jù)本身的結構和語義，所以在桌面搜索[1]中，搜索結果往往包含大量用戶不關心的文檔，或是一些該被找到的文檔卻被遺漏。本文討論了一種擴展的倒排索引機制，該機制基于規(guī)則對原始文檔進行規(guī)范化，能夠把數(shù)據(jù)的結構和語義[2]也考慮在內。通過它可以獲得更好的搜索結果。

1問題舉例

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

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

圖2邀請函原文檔

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

圖3被邀請者XML文檔

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

圖4邀請函實例

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

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

2擴展算法

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

圖5擴展索引機制的結構圖

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

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

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

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

2.1規(guī)范化

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

1）構造標記表（d, R）(d：原始文檔，R：規(guī)則)

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

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

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

表1圖2對應的標記表

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

掃描標記表，如果是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ī)范化過程可以由程序自動完成。具體見文獻[7-9]。

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

2.2索引創(chuàng)建

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

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

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

表2擴展的倒排文件

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

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

3結束語

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

參考文獻:

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

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

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

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

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

[6]數(shù)據(jù)結構[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文檔中的應用研究[J].電腦知識與技術, 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]郭太飛,何潔月.歸納學習XPATH Web信息提取規(guī)則[J].計算機技術與發(fā)展, 2007,17(3).

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