劉勁松,張彬,柴文磊,魏建行,劉振鵬

(河北大學(xué)網(wǎng)絡(luò)中心,河北 保定 071002)

校園網(wǎng)園區(qū)搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)

劉勁松,張彬,柴文磊,魏建行,劉振鵬

(河北大學(xué)網(wǎng)絡(luò)中心,河北 保定 071002)

Google、百度等通用搜索引擎不能適用于所有的情況和需要,現(xiàn)有的校園網(wǎng)搜索引擎存在查準(zhǔn)率、查全率不高,升級(jí)維護(hù)困難等局限性.本著整合校園網(wǎng)資源的目的,為方便廣大師生對(duì)校園網(wǎng)信息的獲取和使用,設(shè)計(jì)并實(shí)現(xiàn)了校園網(wǎng)園區(qū)搜索引擎中文檢索系統(tǒng).該系統(tǒng)由搜索引擎機(jī)器人、信息分析器和Web服務(wù)器查詢軟件3部分組成,能夠?qū)@區(qū)網(wǎng)上的中文網(wǎng)頁(yè)進(jìn)行采集、索引.系統(tǒng)實(shí)現(xiàn)了在河北大學(xué)校園網(wǎng)內(nèi)的信息檢索,具有檢索結(jié)果查準(zhǔn)率高、檢索速度快等優(yōu)點(diǎn).

校園網(wǎng);搜索引擎;信息檢索;倒排

從搜索技術(shù)本身及搜索范圍與深度來(lái)看,Google在國(guó)內(nèi)外對(duì)搜索引擎研究是比較著名的.Google在低層次的智能搜索方面已經(jīng)開(kāi)始研究很多年了,實(shí)際的成果就是翻譯方面,但更為重要的是 Google建立起來(lái)的海量搜索歷史記錄.如果把這些海量搜索歷史記錄當(dāng)作詞典,那么與搜索技術(shù)的結(jié)合發(fā)展成為低層次的智能搜索,應(yīng)用范圍將大大擴(kuò)展.

國(guó)內(nèi)比較著名的比如百度,更專注對(duì)中文的處理,并于2009年提出“框計(jì)算”理論.“框計(jì)算”理念的實(shí)現(xiàn),能讓搜索引擎主動(dòng)識(shí)別用戶信息需求,主動(dòng)定位網(wǎng)絡(luò)有用的資源和服務(wù),從而更加精準(zhǔn)便捷.而現(xiàn)階段搜索引擎基本采用的都是“關(guān)鍵詞查詢+選擇性瀏覽”的用戶交互方式[1-2],這種交互方式無(wú)法主動(dòng)識(shí)別用戶需求,只能由用戶選擇自己所需的結(jié)果.為了滿足用戶更深層次的需求,國(guó)內(nèi)的搜索引擎也在不斷完善自己.如何將人類的知識(shí)和智能加入到檢索中,如何使搜索引擎的質(zhì)量產(chǎn)生一個(gè)質(zhì)的飛躍,也是國(guó)內(nèi)搜索引擎努力的方向.目前的框計(jì)算理念,應(yīng)該是基于搜索引擎的下一代互聯(lián)網(wǎng)系統(tǒng)結(jié)構(gòu)框架和設(shè)計(jì)理念.

1 園區(qū)搜索引擎的設(shè)計(jì)

1.1 功能模塊

搜索引擎的信息采集功能模塊：完成校園網(wǎng)內(nèi)網(wǎng)頁(yè)的自動(dòng)采集和現(xiàn)有網(wǎng)頁(yè)的自動(dòng)更新,并提供增量式處理策略.一般地,每個(gè)搜索引擎都派出被稱為“搜索引擎機(jī)器人”[3]的網(wǎng)頁(yè)搜索軟件在各網(wǎng)址中爬行,訪問(wèn)網(wǎng)絡(luò)中公開(kāi)區(qū)域的每一個(gè)站點(diǎn)并記錄其網(wǎng)址,或者將網(wǎng)頁(yè)抓取到本地,創(chuàng)建出一個(gè)詳盡的網(wǎng)絡(luò)目錄.

信息內(nèi)容功能分析模塊：對(duì)信息采集系統(tǒng)所采集的信息所有文本內(nèi)容以及經(jīng)過(guò)算法處理后的摘要等有用信息存入數(shù)據(jù)庫(kù)以便于檢索,同時(shí)數(shù)據(jù)庫(kù)的內(nèi)容必須經(jīng)常更新、重建,以保持與信息世界的同步發(fā)展.和英文的Internet搜索索引相比,中文的信息分析具有自身的特點(diǎn)對(duì)中文搜索引擎建立索引構(gòu)成了一定的障礙.

信息檢索/發(fā)布/推送模塊：提供多種功能的面向用戶的檢索、發(fā)布、推送服務(wù).這一部分功能模塊的性能主要表現(xiàn)在準(zhǔn)確率、召回率和響應(yīng)時(shí)間上,也是評(píng)價(jià)搜索引擎的主要性能標(biāo)準(zhǔn).

1.2 園區(qū)搜索引擎數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用4個(gè)表(表1-4)：Cache,URLindex,Dict和 Page,分別存儲(chǔ)抓取回來(lái)的頁(yè)面的全部信息、需要抓取的頁(yè)面地址、字典和分開(kāi)后的htm l標(biāo)記和頁(yè)面文字.

表1 存儲(chǔ)抓取回來(lái)的頁(yè)面的全部信息Tab.1 Grab the back pages stored all information

表2 存儲(chǔ)需要抓取的頁(yè)面地址Tab.2 To grab the pages stored address

表3 Dict 功能:存儲(chǔ)字典Tab.3 Stored in the dictionary

表4 存儲(chǔ)分開(kāi)后的htm l標(biāo)記和頁(yè)面文字Tab.4 Htm l tags separated stored and page text

1.3 信息內(nèi)容分析器

1.3.1 倒排文檔的設(shè)計(jì)

通過(guò)對(duì)源信息文件進(jìn)行文本分析生成倒排文件的方式建立檢索項(xiàng)相關(guān)信息.倒排文檔的建立應(yīng)當(dāng)有助于進(jìn)行快速、有效地進(jìn)行檢索,同時(shí)應(yīng)該考慮到在數(shù)據(jù)庫(kù)中的索引數(shù)據(jù)表的規(guī)模,應(yīng)當(dāng)在盡可能小的空間里存儲(chǔ)大容量的信息[4].

字檢索是在建立索引時(shí)以字為檢索項(xiàng),但用戶在進(jìn)行查詢時(shí),均是輸入關(guān)鍵詞,因此在查詢時(shí),就需要把詞拆分為單個(gè)漢字,從數(shù)據(jù)庫(kù)中檢索到相關(guān)記錄后,再進(jìn)行相反的配詞運(yùn)算,才能檢索到用戶需要的有效記錄.在這種條件下,筆者決定在建立倒排文檔時(shí)記錄漢字在文件中的絕對(duì)位置信息,即該漢字距離文件首的字節(jié)數(shù),其倒排文檔格式如表5所示.

表5 倒排文檔格式Tab.5 Inverted file format

在返回查詢結(jié)果時(shí),相關(guān)信息源的信息,如URL、標(biāo)題、摘要等等,也將返回給用戶,因此,還需要建立一份頁(yè)面信息的倒排文檔以記錄所需要的主頁(yè)信息,其結(jié)構(gòu)設(shè)計(jì)如表6所示.

表6 頁(yè)面信息的倒排文檔Tab.6 Inverted file information page

其中Doc i就是字倒排文檔中所記錄的文章標(biāo)識(shí)符,對(duì)于不同的URL其數(shù)值取值也是唯一的.Title是htm l文檔中的標(biāo)題信息,對(duì)于規(guī)范的主頁(yè)文檔都是能夠具有該項(xiàng)關(guān)鍵信息的.Time元素是在更新數(shù)據(jù)庫(kù)時(shí)是否對(duì)已存在的記錄進(jìn)行更新操作的判斷標(biāo)準(zhǔn),如果獲取的主頁(yè)信息比數(shù)據(jù)庫(kù)中的信息新,則對(duì)數(shù)據(jù)庫(kù)中相應(yīng)的記錄進(jìn)行操作,否則仍保留原來(lái)的數(shù)據(jù).

1.3.2 倒排文檔生成算法

由于網(wǎng)絡(luò)機(jī)器人在下載主頁(yè)的時(shí)候已經(jīng)對(duì)源文件進(jìn)行了相關(guān)的處理,所以頁(yè)面文檔信息的倒排文檔生成算法只需要對(duì)經(jīng)過(guò)預(yù)處理[5-8],按照約定格式存儲(chǔ)的文檔進(jìn)行必要操作即可.這種面向?qū)ο蟮木幊谭椒O大地增強(qiáng)了程序的健壯性,同時(shí)使功能擴(kuò)充也非常容易.

字信息倒排文檔生成算法處理就較為復(fù)雜.漢字編碼是雙字節(jié)編碼,即每1個(gè)漢字占用2個(gè)字節(jié)的存儲(chǔ)單位,并且每1個(gè)字節(jié)按照8位二進(jìn)制編碼,其最高位必定為1,同時(shí)在漢字編碼表中第1個(gè)漢字“啊”的16位編碼是“B0A 1”,此前的符號(hào)都是漢字標(biāo)點(diǎn)符號(hào),其后的編碼才代表了漢字.在程序中設(shè)置了2個(gè)指向字符型的指針,始終指向前后相鄰的2個(gè)字節(jié).如果2個(gè)指針?biāo)赶虻膶?duì)象中,有任何1個(gè)字節(jié)的編碼最高位是0,則說(shuō)明這2個(gè)字節(jié)既不是漢字也不是中文符號(hào),此時(shí)前面的指針向后移動(dòng)2位,重新進(jìn)行測(cè)定.如果2個(gè)字節(jié)最高位編碼都為1,再進(jìn)一步與“B0A 1”比較,判斷是否為漢字,如果是則記錄其位置信息,并將2個(gè)指針同時(shí)后移2位,如果不是,則說(shuō)明是中文標(biāo)點(diǎn)符號(hào),只需要對(duì)指針進(jìn)行移動(dòng)操作就可以了.

在記錄漢字位置信息的過(guò)程中,每1條記錄代表了1個(gè)漢字,為了適合工程的需要,從CObject類中派生了1個(gè)新類CCh Index專門記錄漢字的信息,用該類生成的1個(gè)對(duì)象就記錄了1個(gè)漢字的位置信息.該類中包括1個(gè)雙字節(jié)長(zhǎng)度的CString數(shù)據(jù)成員ChWord,另一個(gè)數(shù)據(jù)成員是一個(gè)CPoint數(shù)組WordPosA rray,記錄了漢字的所有位置信息,并且在需要的時(shí)候隨時(shí)可以改變長(zhǎng)度.

2 查詢檢索算法

由于提供的搜索服務(wù)能夠進(jìn)行布爾邏輯查詢,所以首先應(yīng)當(dāng)獲取用戶輸入的所有字符,根據(jù)不同的邏輯方式的分隔符(如邏輯“與”操作是以空格為分隔符)把用戶的輸入子串分成多個(gè)子串[9],對(duì)每一個(gè)子串進(jìn)行查詢,然后對(duì)各個(gè)子串的查詢結(jié)果進(jìn)行邏輯處理,并將最終的結(jié)果生成一個(gè)htm l文件,返回給客戶端;否則,對(duì)各種異常進(jìn)行處理,生成錯(cuò)誤信息htm l文件,返回給客戶端.最后,退出檢索程序,等待下一次查詢,如圖1所示.

圖1 查詢程序總體流程Fig.1 Query overall process

對(duì)于基于字所建立的索引進(jìn)行查詢,最重要的處理過(guò)程就是配詞算法[5-6],如圖2.把每一個(gè)查詢關(guān)鍵詞子串分解為單個(gè)的漢字,從數(shù)據(jù)庫(kù)表格中查到相關(guān)的記錄后,再把字還原成詞,找到符合用戶要求的記錄,返回其中對(duì)用戶有用或感興趣的元素.

圖2 子串檢索配詞算法Fig.2 Clauses retrieval algorithm with words

3 系統(tǒng)實(shí)現(xiàn)及性能測(cè)試

3.1 系統(tǒng)實(shí)現(xiàn)

本系統(tǒng)采用多線程及Socket編程技術(shù),基于上述方案,成功地實(shí)現(xiàn)了對(duì)中文網(wǎng)頁(yè)的搜索功能,建立了一個(gè)小規(guī)模的中文搜索引擎網(wǎng)站,實(shí)現(xiàn)了在河北大學(xué)校園網(wǎng)的園區(qū)搜索.例如用戶輸入“河北大學(xué)”,檢索程序?qū)⒃撛~分解為4個(gè)漢字.經(jīng)過(guò)查詢數(shù)據(jù)庫(kù)中Word Info表,發(fā)現(xiàn)“北”字的記錄最少,便以它為配詞基本點(diǎn).提取“北”的第1個(gè)位置信息,如(1,54),表示“北”字在第1篇文章第54個(gè)字節(jié).接著,如果在第1篇文章中有“河北大學(xué)”記錄,那么,“河”的記錄中應(yīng)當(dāng)含有(1,52)的位置信息,“大”的記錄中應(yīng)有(1,56),“學(xué)”的記錄中應(yīng)含有(1,58)的位置信息.分別對(duì)其他3個(gè)字的記錄進(jìn)行搜索,發(fā)現(xiàn)全部能夠匹配,則說(shuō)明在第1篇文章內(nèi)存在“河北大學(xué)”的關(guān)鍵詞,所以可以查詢Page Info表,把與第1篇文章相關(guān)的信息返回給用戶.這樣反復(fù)循環(huán),直到把“北”字的所有位置信息均查詢一遍,就完成了對(duì)“河北大學(xué)”關(guān)鍵詞的查詢.

3.2 性能測(cè)試

對(duì)于系統(tǒng)的運(yùn)行效率,測(cè)試采用的衡量尺度是單次查詢的執(zhí)行時(shí)間.利用Apache JM eter,可以簡(jiǎn)單模擬對(duì)查詢服務(wù)的訪問(wèn)[10],表7列出了不同數(shù)量的文檔集合對(duì)系統(tǒng)處理時(shí)間的影響.

表7 查詢執(zhí)行時(shí)間Tab.7 Inquires the execution Time

測(cè)試結(jié)果表明在其他參數(shù)不變的情況下,系統(tǒng)的執(zhí)行時(shí)間與文檔數(shù)量成正比,對(duì)于小規(guī)模的文檔集合,檢索速度快.系統(tǒng)使用SQL Server數(shù)據(jù)庫(kù)管理器和DLL作為網(wǎng)關(guān)程序,響應(yīng)速度快,配詞算法性能優(yōu)越,一般查詢?cè)? s左右均能返回查詢結(jié)果,在中低壓力的情況下,系統(tǒng)可以提供穩(wěn)定的搜索服務(wù).

評(píng)價(jià)信息檢索性能的主要指標(biāo)為查準(zhǔn)率和查全率.查準(zhǔn)率是指檢索到的相關(guān)文檔與檢索到的全部文檔的比率,查全率是指檢索到的相關(guān)文檔與所有滿足條件的文檔數(shù)目的比例.在測(cè)試中,從資料中獲取有關(guān)Web文檔1 200篇,采用計(jì)算機(jī)中的常用詞組1 500個(gè),建立索引特征項(xiàng)庫(kù),并利用不同的相似度閥值分別進(jìn)行測(cè)試,得到的傳統(tǒng)搜索引擎和本系統(tǒng)的查全率和查準(zhǔn)率,如表8所示.

表8 傳統(tǒng)搜索與本系統(tǒng)的性能比較Tab.8 Traditional search performance comparison with this system

表8的測(cè)試結(jié)果表明,檢索結(jié)果查準(zhǔn)率高.系統(tǒng)采用二值型布爾式檢索模型,返回結(jié)果中一定含有待查詢字符串,不會(huì)出現(xiàn)誤差,這一點(diǎn)性能要遠(yuǎn)優(yōu)于詞檢索模型.

4 結(jié)語(yǔ)

隨著搜索引擎技術(shù)的不斷商業(yè)化,信息檢索技術(shù)已經(jīng)進(jìn)入了發(fā)展的黃金時(shí)期,而Internet在中國(guó)的發(fā)展也是日新月異,大量涌現(xiàn)的中文信息需要性能優(yōu)良的中文搜索引擎.而把搜索引擎技術(shù)和自然語(yǔ)言處理技術(shù)結(jié)合起來(lái),提高中文搜索引擎的檢索效果不僅是Internet信息檢索技術(shù)發(fā)展的趨勢(shì),同樣使用了這種技術(shù)的搜索引擎也必然具有巨大的市場(chǎng)和廣闊的發(fā)展前景.

[1]馬費(fèi)成,望俊成,吳克文,等.國(guó)外搜索引擎檢索效能研究述評(píng)[J].中國(guó)圖書(shū)館學(xué)報(bào),2009(4)：73-80.

[2]張軍華,韓全會(huì).中文五大綜合搜索引擎主要性能測(cè)評(píng)[J].情報(bào)科學(xué),2008,26(10)：1540-1542.

[3]姚全珠,彭程,宋志理,等.基于關(guān)聯(lián)規(guī)則的搜索引擎方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(9)：134-136.

[4]陳華,李仁發(fā),劉鈺峰,等.個(gè)性化搜索引擎推薦算法研究[J].計(jì)算機(jī)應(yīng)用研究,2010(1)：48-50.

[5]聶靖,李強(qiáng),龐力,等.移動(dòng)元搜索引擎中網(wǎng)頁(yè)內(nèi)容提取算法研究[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),2010,26(10)：54-58.

[6]AHM ET U YAR.Investigation of the accuracy of search engine hit counts[J].Journalof Information Science,2009,35(4)：321-325.

[7]CHRISTOPHER N.Op timize your web site fo r search engines[J].PCWORLD,2009,27(3)：527-533.

[8]薛曄偉,沈鈞毅,張?jiān)?一種編輯距離算法及其在網(wǎng)頁(yè)搜索中的應(yīng)用[J].西安交通大學(xué)學(xué)報(bào),2008,42(12)：1450-1454.

[9]李紅梅,丁振國(guó),周水生,等.搜索引擎中的聚類瀏覽技術(shù)[J].中文信息學(xué)報(bào),2008,22(3)：56-63.

[10]劉奕群,岑榮偉,張敏,等.基于用戶行為分析的搜索引擎自動(dòng)性能評(píng)價(jià)[J].軟件學(xué)報(bào),2008,19(11)：3023-3032.

Design and Emplement of Search Engine on the Campus Network Park

LIU Jin-song,ZHANGBin,CHAIWen-lei,WEIJian-hang,LIU Zhen-peng
(Network Center,Hebei University,Baoding 071002,China)

Google and baidu universal search engines and soon can't be app lied to meet the needs of all the situation,the existing campus network search engines exist p recision and recall are not high,it is difficult to upgrademaintenance.In line w ith the purpose of netwo rk resources integration,fo r the convenience of teachers and students of campus network info rmation acquisition and use,we design and imp lement the campus network park search engine Chinese retrieval system.This system consistsof search engine robots,info rmation analyzer and web server inquires the softw are of three parts,fo r the Chinese w eb page in park online collection and index.System realizes the campus in Hebei University in information retrieval,and the retrieval results w ith high p recision,retrieval speed,etc.

campus netwo rk;search engines;info rmation retrieval;inverted

TP 391

A

1000-1565(2011)04-0439-06

2011-01-20

國(guó)家自然科學(xué)基金專項(xiàng)基金資助項(xiàng)目(J0921020)

劉勁松(1978-),男,河北保定人,河北大學(xué)實(shí)驗(yàn)師,主要從事網(wǎng)絡(luò)信息化方向研究.

E-mail：ljs@hbu.cn

為一自然數(shù)Doci,該標(biāo)識(shí)符是區(qū)別不同文檔的唯一依據(jù);Posi則表明該漢字在文檔i中的絕對(duì)位置.這樣每一對(duì)數(shù)值構(gòu)成了一個(gè)漢字的唯一坐標(biāo)信息.

孟素蘭)