蘇金波 葉紅

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

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

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)起來(lái)，通過(guò)這些關(guān)鍵字用戶可以很快找到對(duì)應(yīng)的文檔。但是這種索引機(jī)制并不考慮數(shù)據(jù)本身的結(jié)構(gòu)和語(yǔ)義，所以在桌面搜索[1]中，搜索結(jié)果往往包含大量用戶不關(guān)心的文檔，或是一些該被找到的文檔卻被遺漏。本文討論了一種擴(kuò)展的倒排索引機(jī)制，該機(jī)制基于規(guī)則對(duì)原始文檔進(jìn)行規(guī)范化，能夠把數(shù)據(jù)的結(jié)構(gòu)和語(yǔ)義[2]也考慮在內(nèi)。通過(guò)它可以獲得更好的搜索結(jié)果。

1問(wèn)題舉例

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

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

圖2邀請(qǐng)函原文檔

其中<被邀請(qǐng)者/>記錄在另一個(gè)XML文檔：

圖3被邀請(qǐng)者XML文檔

如果用不考慮數(shù)據(jù)的結(jié)構(gòu)和語(yǔ)義的傳統(tǒng)搜索算法[4]，用戶輸入“張三”進(jìn)行搜索，那么圖2所示的文檔不會(huì)被列出，因?yàn)樗]包含“張三”這個(gè)關(guān)鍵字，但用戶卻希望能看到圖4所示的搜索結(jié)果（因?yàn)椤皬埲笔潜谎?qǐng)者之一）。類似的，如果用戶輸入“402”關(guān)鍵字，圖2文檔就會(huì)被找出，因?yàn)榘恕?02”這個(gè)關(guān)鍵字，但這個(gè)結(jié)果并不是用戶關(guān)心的（因?yàn)闀?huì)議是在401室開的，而不是在402）。

圖4邀請(qǐng)函實(shí)例

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

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

2擴(kuò)展算法

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

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

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

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

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

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

2.1規(guī)范化

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

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

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

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

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

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

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

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

因?yàn)橐?guī)則是以XSLT和XQuery表示，所以規(guī)范化過(guò)程可以由程序自動(dòng)完成。具體見文獻(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ī)則的約束來(lái)定，比如在圖2例子基礎(chǔ)上再加上一個(gè)約束條件：如果時(shí)間是上午（time<=12.00）用401會(huì)議室，如果是下午（time>12.00）用402會(huì)議室，那么倒排文件表如表2所示。

表2擴(kuò)展的倒排文件

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

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn):

[1]向凱全,王盼卿,陳軍廣,等.裝備領(lǐng)域中語(yǔ)義桌面上的個(gè)人主觀本體研究[J].計(jì)算機(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].北京:機(jī)械工業(yè)出版社,2006.

[5]王能斌.數(shù)據(jù)庫(kù)系統(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í)與技術(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].計(jì)算機(jī)技術(shù)與發(fā)展, 2007,17(3).

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