山東師范大學(xué)碩士學(xué)位論文 網(wǎng)絡(luò)多媒體教育資源主題搜索算法研究 摘要 網(wǎng)絡(luò)多媒體教育資源是指存在于i n t e m e t 中的多媒體教學(xué)資源。隨著網(wǎng)絡(luò)與多媒體 技術(shù)的發(fā)展，w e b 中的多媒體教學(xué)資源，尤其是音頻、視頻和動畫，也日益豐富，成 為教育領(lǐng)域的重要組成部分。如何快速、準確地找到特定主題的多媒體教學(xué)資源，使 其在信息化教育中充分發(fā)揮作用，是教育技術(shù)工作者亟待解決的問題，也使得傳統(tǒng)的 搜索引擎面臨著巨大的挑戰(zhàn)，各類多媒體搜索引擎也隨之應(yīng)運而生并受到廣泛的關(guān)注。 主題搜索器的搜索算法，是搜索引擎的核心，它決定了搜索引擎的搜索效率和質(zhì)量。 本文從主題網(wǎng)頁和包含多媒體的網(wǎng)頁在w e b 中分布的特點出發(fā)，圍繞提高多媒體主題 搜索效率的問題，提出一種基于u r l 鏈接規(guī)則的多媒體主題搜索算法。 本文首先介紹了在h t m l 文檔中，與多媒體資源有關(guān)的文本信息和h t m l 標簽， 深入分析了主題頁面和包含多媒體資源的網(wǎng)頁在w e b 上的分布特征。在分析和比較現(xiàn) 有的主題搜索算法的優(yōu)缺點的基礎(chǔ)上，歸納了提高搜索效率的幾個關(guān)鍵因素。 本文對主題搜索領(lǐng)域中傳統(tǒng)的主題搜索算法進行了詳細的分析，在深入分析主題 頁面在w 曲上的分布特征與主題相關(guān)性判別算法的基礎(chǔ)上，對p a g e r a n k 、s h a r k s e a r c h 兩種典型的主題搜索算法進行相關(guān)參數(shù)的改進，同時將網(wǎng)頁內(nèi)容相似度和網(wǎng)頁鏈接相 似度加入到算法的計算過程中，并將改進后的t o p i c p a g e r a n k 算法、s h a r k s e a r c h 算法 應(yīng)用于多媒體主題搜索領(lǐng)域。 針對傳統(tǒng)的主題搜索算法不能簡單的應(yīng)用于多媒體主題搜索領(lǐng)域的問題，本文基 于包含多媒體的網(wǎng)頁往往呈現(xiàn)出“資源相鄰性 的特點，提出了一種基于u r l 鏈接規(guī) 則的多媒體主題搜索算法，即從種子網(wǎng)站列表中自動學(xué)習(xí)出代表“多媒體資源區(qū)域 u r l 正則表達式，并用這些正則表達式來指導(dǎo)主題搜索器對網(wǎng)頁的抓取。在詳細介紹 u r l 數(shù)據(jù)結(jié)構(gòu)、u r l 距離的度量以及u r l 正則表達式的學(xué)習(xí)和指導(dǎo)過程的基礎(chǔ)上，對 p a g e r a n k 算法進行改進，實現(xiàn)基于u r l 鏈接規(guī)則算法在鏈接方面的相似度計算。 為了驗證基于u r l 鏈接規(guī)則多媒體主題搜索算法的高效性，本文采用統(tǒng)一的系統(tǒng) 體系結(jié)構(gòu)和軟、硬件平臺，對t o p i c p a g e r a n k 算法、改進的s h a r k s e a r c h 算法和基于 u r l 鏈接規(guī)則的算法輸入相同的種子頁面集、限定同一搜索深度進行實驗測試。文章 從查全率和查準率兩個角度，對三種算法進行比較。實驗結(jié)果表明本文的工作是相當(dāng) 有效的，尤其是提出的基于u r l 鏈接規(guī)則的多媒體主題搜索算法，具有相當(dāng)?shù)膭?chuàng)新性 和實際應(yīng)用價值。 【關(guān)鍵字】w e b 多媒體；主題搜索器；主題搜索算法 【分類號】 g 4 3 4 i i 山東師范大學(xué)碩上學(xué)位論文 r e s e a r c ho nn e t w o r km u l t i m e d i ae d u c a t i o n a lr e s o u r c e s t o p i cs e a r c ha l g o r i t h m a bs t r a c t n e t w o r km u l t i m e d i ae d u c a t i o nr e s o u r c e sr e f e rt ot h em u l t i m e d i at e a c h i n gr e s o u r c e s o nt h ei n t e r n e t a st h e d e v e l o p m e n t o fn e t w o r ka n dm u l t i m e d i at e c h n o l o g y , w e b m u l t i m e d i at e a c h i n gr e s o u r c e s ，e s p e c i a l l ya u d i o ，v i d e oa sw e l la sa n i m a t i o n ，a r ea l s o i n c r e a s i n g l yr i c ha n db e c o m ea l li m p o r t a n tp a r ti nt h ef i e l do fe d u c a t i o n h o wt oq u i c k l y a n da c c u r a t e l yf i n dt h es p e c i f i ct o p i cm u l t i m e d i at e a c h i n gr e s o u r c e s ，a n de n a b l et h e mt o p l a yt h er o l ei ne d u c a t i o n a li n f o r m a t i o n i z a t i o ns u f f i c i e n t l y ，i st h eu r g e n tp r o b l e mf o r e d u c a t i o n a lt e c h n o l o g yw o r k e r s ，a n da l s oag r e a tc h a l l e n g et ot h et r a d i t i o n a ls e a r c h e n g i n e s av a r i e t yo fm u l t i m e d i as e a r c he n g i n e se m e r g e da st h et i m e sr e q u i r e da n dg o t w i d e s p r e a dc o n c e r n t h ea l g o r i t h mi st h ec o r eo ft h et o p i cs e a r c he n g i n ea n dd e t e r m i n e s t h es e a r c he f f i c i e n c ya n dq u a l i t y a c c o r d i n gt ot h e c h a r a c t e r i s t i c so ft h ed i s t r i b u t i o no f t o p i cp a g ea n dm u l t i m e d i ap a g eo nt h ew e b ，t h ep a p e rp r e s e n t sam u l t i m e d i at o p i cs e a r c h a l g o r i t h mb a s e do nu r l l i n kr u l e st h a tf o c u s e so nt h ep r o b l e mo fi m p r o v i n gt o p i cs e a r c h e f f i c i e n c y t h ep a p e rf i r s t l yi n t r o d u c et h et e x ti n f o r m a t i o na n dh t m l t a g sr e l a t e dt om u l t i m e d i a r e s o u r c e si nh t m ld o c u m e n t s ，t h e nm a k ea n d e e pa n a l y s i so ft h e d i s t r i b u t i o n c h a r a c t e r i s t i c so ft h et o p i cp a g ea n dm u l t i m e d i ap a g ei nt h ew e b b a s e do nt h ea n a l y s i sa n d c o m p a r i s o no f t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ee x i s t i n gt o p i cs e a r c ha l g o r i t h m s ，t h e k e yf a c t o r so fi m p r o v i n gs e a r c he f f i c i e n c ya r ep r e s e n t e d t h et r a d i t i o n a lt o p i cs e a r c ha l g o r i t h m si nt h et o p i cs e a r c hf i e l dg e td e t a i l e da n a l y s i s b a s e do nt h ed e e pa n a l y s i so ft h ed i s t r i b u t i o nc h a r a c t e r i s t i c so ft o p i cp a g ei nt h ew e ba n d t h et o p i cr e l e v a n c ed i s c r i m i n a t i o na l g o r i t h m ，t h er e l a t e dp a r a m e t e r so ft h et w ot y p i c a lt o p i c s e a r c ha l g o r i t h m sp a g e r a n ka n ds h a r k - s e a r c ha r ei m p r o v e d m e a n w h i l e ，t h ew e bc o n t e n t s i m i l a r i t ya n dt h ew e b l i n k ss i m i l a r i t ya r ea d d e dt ot h ec a l c u l a t i o np r o c e s so ft h ea l g o r i t h m t h e n ，t h ei m p r o v e dt o p i c - p a g e r a n ka n ds h a r k s e a r c ha l g o r i t h m sa r ea p p l i e di n m u l t i m e d i at o p i cs e a r c hf i e l d 1 1 1 s i n c et r a d i t i o n a lt o p i cs e a r c ha l g o r i t h m sc a n tb ea p p l i e di nm u l t i m e d i at o p i cs e a r c h f i e l d ，t h ep a p e rp r e s e n t sam u l t i m e d i at o p i cs e a r c ha l g o r i t h mb a s e do nu r l l i n kr u l e su n d e r c o n s i d e r a t i o nw i t ht h e “r e s o u r c ea d j a c e n c y o ft h em u l t i m e d i aw e b t h en e wa l g o r i t h mc a n l e a r na u t o m a t i c a l l yt h eu r lr e g u l a re x p r e s s i o no nb e h a l fo ft h e m u l t i m e d i ar e s o u r c ea r e a f r o mt h es e e dw e bl i s t ，a n dt h e nu s et h e s er e g u l a re x p r e s s i o n st oi n s t r u c tt h et o p i cs e a r c h e n g i n et oc a p t u r ep a g e s i nt h el i g h to ft h ed e t a i l e di n t r o d u c t i o no nu r l d a t as t r u c t u r e ，u r l d i s t a n c e sm e a s u r e m e n t ，a n dt h es t u d yo fu r l r e g u l a re x p r e s s i o n ，t h ep a g e r a n ka l g o r i t h m i si m p r o v e d ，e v e n t u a l l yt h el i n ks i m i l a r i t yi sc a l c u l a t e db a s e do nt h eu r ll i n kr u l e s a l g o r i t h m t ov a l i d a t et h eh i g he f f i c i e n c yo fm u l t i m e d i at o p i cs e a r c ha l g o r i t h mt h a tb a s e do n u r ll i n kr u l e s ，t h i sp a p e ra d o p t sau n i f i e ds y s t e ms t r u c t u r ea n ds o f t w a r ea n dh a r d w a r e p l a t f o r m s ；i n p u t st h es a m es e e dp a g e sa n dl i m i t s t h es a m es e a r c hd e p t ht oc o n d u c t e x p e r i m e n t sf o rt h et o p i c - p a g e r a n k ，i m p r o v e ds h a r k s e a r c ha n du r l - b a s e da l g o r i t h m s f r o mt h et w oa s p e c t so fr e c a l la n dp r e c i s i o nr a t i o ，t h et h r e ea l g o r i t h m sa r ec o m p a r e d t h e e x p e r i m e n t a lr e s u l t ss h o wt h a to u rw o r ki sq u i t ee f f e c t i v e ，e s p e c i a l l yt h eu r l b a s e d m u l t i m e d i at o p i cs e a r c ha l g o r i t h mw h i c hh a sc o n s i d e r a b l ei n n o v a t i o na n dp r a c t i c a l a p p l i c a t i o nv a l u e 【k e yw o r d s l w e bm u l t i m e d i a ；t o p i cs e a r c h e r ；t o p i cs e a r c ha l g o r i t h m 【c a t e g o r y l g 4 3 4 i v 獨創(chuàng)聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究成果。 據(jù)我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫 過的研究成果，也不包含為獲得( 注：如沒有其他需要特別聲明的，本 欄可空) 或其他教育機構(gòu)的學(xué)位或證書使用過的材料。與我一同工作的同志對本研究所做 的任何貢獻均已在論文中作了明確的說明并表示謝意。 學(xué)位論文作者簽名：楊移廠 導(dǎo)師肄錫鋤形移 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解堂撞有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國 家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)堂撞可 以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等 復(fù)制手段保存、匯編學(xué)位論文。( 保密的學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文作者簽名： 簽字日期：2 0 0 9 年月 乃2 ，廠 導(dǎo)師簽字： 釤豫彩智 簽字日期：2 0 0 9 年彰月i o n 楊 日 山東師范大學(xué)碩士學(xué)位論文 第一章緒論帚一旱三：百下匕 1 1 引言 多媒體是綜合性的信息資源，是文本( t e x t ) 、圖形( g r a p h i c ) 、聲音( s o u n d ) 、 動畫( a n i m a t i o n ) 、視頻( v i d e o ) 等媒體元素的統(tǒng)稱【l 】。隨著計算機技術(shù)的發(fā)展和i n t e r n e t 應(yīng)用的普及，基礎(chǔ)教育教學(xué)資源的信息化建設(shè)也得到了蓬勃的發(fā)展。隨著各種類型教 學(xué)資源專業(yè)網(wǎng)站的不斷涌現(xiàn)，w e b 已經(jīng)成為人們獲取教學(xué)資源的主要途徑。根據(jù)c n n i c 發(fā)布的第1 9 次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告，截至2 0 0 6 年底，中國網(wǎng)站的網(wǎng)頁數(shù) 量為4 4 7 億【2 1 ，其中文本和圖像仍然是網(wǎng)頁最主要的內(nèi)容形式，分別占據(jù)7 0 2 和2 9 5 的比例；視頻網(wǎng)頁占網(wǎng)頁總數(shù)的0 3 9 6 。而按照多媒體格式分類：s w 潞式的網(wǎng)頁占網(wǎng)頁 總數(shù)的1 ，m p 3 格式的網(wǎng)頁占網(wǎng)頁總數(shù)的0 1 。同時根據(jù)c n n i c 2 0 0 8 年8 月發(fā)布的報告 顯示：目前中國網(wǎng)站數(shù)量已達1 9 1 9 萬個，年增長率達至t j 4 6 3 ，而且繼續(xù)保持快速增長 的勢頭。 美國教育傳播技術(shù)協(xié)會( a e c t ) t 3 1 9 0 年代以后發(fā)布了2 個不同的定義：a e c t 9 4 定 義認為：“教育技術(shù)是為了促進學(xué)習(xí)，對有關(guān)的過程和資源進行設(shè)計、開發(fā)、利用、管 理和評價的理論與實踐 【4 ，5 1 。2 0 0 4 年，a e c t 又發(fā)布了對教育技術(shù)的新界定，對于該界 定，彭邵東教授將其翻譯為：“教育技術(shù)是通過創(chuàng)造、使用、管理適當(dāng)?shù)募夹g(shù)過程和資 源，促進學(xué)習(xí)和改善績效的研究與符合道德規(guī)范的實踐 1 6 】。從以上教育技術(shù)的定義中 不難看出，對教育相關(guān)資源的利用和管理是教育技術(shù)的一個重要研究范疇，而多媒體 資源是教育資源的重要組成部分。對于學(xué)習(xí)環(huán)境的構(gòu)建和學(xué)習(xí)者的學(xué)習(xí)具有非常重要 的作用。 但隨著網(wǎng)站的增多，教學(xué)資源數(shù)量呈幾何級數(shù)的增長，要想從w e b 上獲取一條想要 的多媒體資源的難度越來越大。目前網(wǎng)站教學(xué)資源都是以半結(jié)構(gòu)化( s e m i s t r u c t u r e d ) f 7 ，8 1 的數(shù)據(jù)形式存在，大多數(shù)網(wǎng)頁是通過h t m l 9 1 語言來展現(xiàn)的，而h t m l 語言的一個顯 著特點是結(jié)構(gòu)隱含、不規(guī)則或不完整。結(jié)果使得這種網(wǎng)站上的多媒體資源處于雜亂無 序的狀態(tài)，數(shù)據(jù)集成性非常差、應(yīng)用程序無法直接解析、獲取并利用w e b 多媒體資源困 難，從而給教育教學(xué)資源信息化建設(shè)造成了極大的困難。 i n t e m e t 具有海量、異構(gòu)、動態(tài)變化等特性，使得用戶試圖通過瀏覽網(wǎng)頁來發(fā)現(xiàn)所 需要的多媒體資源已經(jīng)變得越來越困難。如何能夠?qū)崿F(xiàn)從互聯(lián)網(wǎng)自動的或者人盡量少 山東師范大學(xué)碩士學(xué)位論文 的參與下搜索到w 曲中的多媒體資源，并對搜索到的多媒體資源進行自動分類，然后對 它們進行特征提取以確定多媒體資源的主題內(nèi)容，這些工作都具有重要的現(xiàn)實意義。 基于此，論文立題研究網(wǎng)絡(luò)多媒體教育資源主題搜索算法，根據(jù)包含多媒體的網(wǎng) 頁在i n t e m e t 上分布的特征，通過一定的算法在盡可能少的耗費計算機資源的情況下快 速地搜索到多媒體網(wǎng)頁，從多媒體所在的網(wǎng)頁中提取出多媒體相關(guān)文本，再從相關(guān)文 本中提取出用于描述、標引w 曲多媒體的語義信息，從而確定多媒體的主題。將此方法 應(yīng)用到基礎(chǔ)教育資源中，這對于學(xué)習(xí)環(huán)境的構(gòu)建、教育資源信息化的建設(shè)具有重要的 意義。 1 2 網(wǎng)絡(luò)多媒體資源搜索的研究現(xiàn)狀 目前，因特網(wǎng)上圖形、圖像、視頻、音頻、動畫等多媒體信息日益豐富，各種基 于網(wǎng)絡(luò)的多媒體搜索引擎隨之應(yīng)運而生。根據(jù)它們的工作原理和方式的不同，主要分 為兩種類型：基于文本描述的多媒體搜索引擎和基于內(nèi)容的多媒體搜索引擎。 基于文本描述的多媒體搜索引擎，這種方法主要是對含有多媒體資源的網(wǎng)站和網(wǎng) 頁進行分析，對多媒體信息的物理特征和內(nèi)容特征進行著錄和標引，把它們轉(zhuǎn)換成文 本信息或者添加文本說明，對這些文本信息建立數(shù)據(jù)庫，索引時主要在此數(shù)據(jù)庫中進 行關(guān)鍵詞的匹配?？梢酝ㄟ^文件擴展名來確定多媒體的類型，如：圖像文件常用g i f 和j p g 作為擴展名，聲音文件常用m i d 、w a y 、m p 3 等作為擴展名，視頻文件常用a v i 、m o v 、 m p e g 、r i l l 、r m v b 作為擴展名。在多媒體搜索引擎中還可以利用超文本標識符來確定 多媒體資源的類型，如： 和 兩個超文本標識符可以用來檢測是否存在 可顯示的圖像文件。嵌套在網(wǎng)頁中的多媒體信息，在網(wǎng)頁中往往帶有與內(nèi)容相關(guān)的標 題或文本描述，這些信息在多媒體搜索過程中起著表征多媒體內(nèi)容的作用。 目前，網(wǎng)上的大部分多媒體搜索引擎都屬于此類。視頻搜索引擎比較著名的有： 優(yōu)酷、六間房、百度視頻、g o o g l e 視頻、土豆網(wǎng)等；音頻搜索引擎比較著名的有：百度 m p 3 、愛聽音樂、搜狗音樂、雅虎音樂等；動畫搜索引擎比較著名的有：閃吧、小破 孩、閃客帝國、t o m f l a s h 動畫等。 基于內(nèi)容的多媒體搜索引擎【1 0 】一般包括兩部分，數(shù)據(jù)庫生成系統(tǒng)和查詢子系統(tǒng)。 具體而言，就是多媒體信息標引系統(tǒng)和檢索系統(tǒng)。標引系統(tǒng)的任務(wù)是完成對多媒體的 預(yù)處理和提取特征，然后建立起多媒體信息數(shù)據(jù)庫系統(tǒng)，該數(shù)據(jù)庫系統(tǒng)包括信息庫、 特征庫和知識庫。檢索系統(tǒng)則負責(zé)對用戶提交的多媒體信息進行特征提取，然后檢索 2 山東師范大學(xué)碩士學(xué)位論文 多媒體特征庫，并將用戶要求最相似的信息輸出出來。它和基于文本描述的搜索引擎 最重要的區(qū)別是：基于內(nèi)容的多媒體搜索引擎對多媒體的內(nèi)容特征描述進行查詢，這 些多媒體信息內(nèi)容特征的描述主要包括：圖像的顏色、紋理、形狀等；聲音的音頻、 響度、頻度和音色等；視頻的視頻特征、運動特征等。 基于內(nèi)容的多媒體搜索引擎目前還不多見，常見的主要有以下幾種： ( 1 ) q b i c l j ( q u e r yb yi m a g ec o n t e n t ) 。q b i c ( h t t p ：w w w q b i c a l m a d e n c o r n ) 是2 0 世紀9 0 年代i b m 公司研制的，它是標準的基于內(nèi)容特征的檢索系統(tǒng)。q b i c 提供的 檢索途徑有：利用系統(tǒng)提供的標準范圍，用戶自己輸入圖像、簡圖或者影像片段。 ( 2 ) 上海交通大學(xué)的音樂數(shù)據(jù)庫檢索系統(tǒng)【1 2 1 ，是為數(shù)不多的基于內(nèi)容的聲音檢索 系統(tǒng)。它不但提供了基于文本描述的聲音檢索系統(tǒng)的演奏者、作曲者、曲名、主題類 別外，而且還提供了樂句和全曲作為檢索途徑。樂句作為樂曲的主題詞，以簡譜作為 表現(xiàn)形式。檢索時，將輸入的字符序列和音樂數(shù)據(jù)庫的字符序列相匹配。在樂句檢索 中，可以只輸入樂句簡譜的音高部分，而不用輸入時值。在檢索中，也可以采用前截 或后截詞檢索，用 表示，如“* 2 3 2 3 5 6 2 * 表示前后截詞。由于音樂的演奏形式 會經(jīng)常發(fā)生變化，如果檢索者對旋律的記憶不很準確，這時就需要模糊檢索功能，這 是相當(dāng)重要的。 ( 3 ) 哥倫比亞大學(xué)研究的v i d e o q 是一種全自動面向?qū)ο蠡趦?nèi)容的視頻檢索系統(tǒng) 【1 3 】。它對基于關(guān)鍵字或主題瀏覽的傳統(tǒng)檢索方式進行了拓展，同時提出了全新的基于 視覺特征和時空關(guān)系的查詢技術(shù)。此系統(tǒng)能自動切分并跟蹤視頻中任意形狀的對象， 并且提供包括顏色、紋理、形狀和運動在內(nèi)的豐富視覺特征庫。目前，v i d e o q 視頻庫 有超過3 0 0 0 段的視頻，每段都被壓縮成3 層結(jié)構(gòu)保持，可通過w w w 互聯(lián)網(wǎng)交互查詢和 瀏覽。 1 3 多媒體主題搜索相關(guān)技術(shù)介紹 1 3 1 主題搜索引擎 主題搜索引擎【1 4 】以查詢和檢索某一專業(yè)領(lǐng)域或?qū)W科領(lǐng)域的因特網(wǎng)信息資源為目 的，在互聯(lián)網(wǎng)上智能的搜索符合特定查詢主題的i n t e m e t 信息資源。主題搜索引擎和通 用搜索引擎在工作原理上是一樣的，主題搜索器是其核心組成部分。不同的是，在主 題搜索引擎中主題搜索器在進行網(wǎng)絡(luò)信息采集時采用主題式搜索策略，按照管理員預(yù) 先設(shè)定的主題去采集網(wǎng)上的相關(guān)信息，這樣可以減少被采集的信息數(shù)量，提高索引數(shù) 3 山東師范大學(xué)碩士學(xué)位論文 據(jù)庫中的信息質(zhì)量。 主題搜索引擎一般由搜索器、索引器、檢索器和用戶接口四個基本部分組成。其 基本結(jié)構(gòu)如圖1 1 。 圖1 - 1 主題搜索引擎的基本結(jié)構(gòu) 1 主題搜索器 主題搜索器是一種網(wǎng)絡(luò)資源發(fā)現(xiàn)與收集程序，通常從一個“種子集 ( 如用戶查詢、 種子鏈接或種子頁面) 出發(fā)，通過h t t p 等協(xié)議請求并下載網(wǎng)絡(luò)資源，分析資源并提取 鏈接，然后再以循環(huán)迭代的方式訪問網(wǎng)絡(luò)【1 5 ，1 6 】。主要負責(zé)h t m l 頁面的解析、爬行頁面 的選擇和主題搜索算法的計算等工作。 主題搜索算法是主題搜索器的核心，它也是區(qū)別于通用搜索引擎的關(guān)鍵部分，決 定了一個主題搜索引擎搜索的效率和返回結(jié)果的準確度。目前，在該領(lǐng)域很多專家、 學(xué)者從理論和實踐上做了很多研究工作，提出了許多主題搜索算法，包括：以 s h a r k s e a r c h 17 】和b e s t f i s h 1 8 】為代表的基于內(nèi)容評價的搜索策略；以p a g e r a n k t l 9 】和 h i t s 2 川為代表的基于鏈接結(jié)構(gòu)評價的搜索策略。文獻【2 1 】為了增強主題搜索的自適應(yīng) 能力，將鞏固學(xué)習(xí)策略在預(yù)測遠期回報的優(yōu)勢加入到搜索的學(xué)習(xí)過程中，用來預(yù)測待 搜索鏈接未來回報價值。文獻【2 2 在鞏固學(xué)習(xí)的基礎(chǔ)上，通過構(gòu)建典型的“w 曲語境圖” 策略來估計目標頁面的距離，加強了主題搜索器的自適應(yīng)和增量反饋能力。 2 索引器 索引器的作用是對主題搜索器采集來的網(wǎng)頁進行處理，抽取出網(wǎng)頁的索引項，然 4 山東師范大學(xué)碩士學(xué)位論文 后編制索引入庫以備用戶檢索。網(wǎng)頁處理的內(nèi)容主要包括以下幾個部分：文檔特征提 取、網(wǎng)頁篩選、標引、相關(guān)度分析、歸類和最后的入庫、生成文檔庫的索引表。索引 表一般使用某種形式的倒排序表( i n v e r s i o nl i s t ) 2 3 】，即由索引項查找相應(yīng)的文檔。索 引表也可能要記錄索引項在文檔中出現(xiàn)的位置，以便檢索器計算出索引項之間的相鄰 或接近關(guān)系( p r o x i m i t y ) 。索引器可以使用集中索引算法或分布式索引算法進行索引， 索引算法對索引器的性能有很大影響。 3 檢索器 檢索器是根據(jù)用戶的查詢內(nèi)容在索引庫中快速檢索出所需的資源，并對用戶的查 詢主題與索引庫中的相關(guān)資源進行相關(guān)度的評價，然后根據(jù)相關(guān)度的高低，通過用戶 接口返回給用戶。其中檢索算法、信息查詢和組織方式都會在很大程度上影響檢索器 的性能。 4 用戶接口 用戶接口的作用是輸入用戶查詢內(nèi)容、顯示查詢結(jié)果和提供用戶交互反饋機制。 主要目的是方便用戶使用搜索引擎，能夠高效率、多方式地從搜索引擎中得到有效、 及時的信息。 1 3 2 多媒體資源的文件格式 主題搜索器在進行網(wǎng)頁信息的采集過程中，通過分析嵌入到網(wǎng)頁中的多媒體文件 格式來判斷多媒體的類型，然后獲取多媒體資源的鏈接路徑，并將其存入到多媒體數(shù) 據(jù)庫中。目前i n t e r n e t 上存在的網(wǎng)頁大多以文本和圖像形式存在，所以在搜索多媒體 資源的時候圖像暫時沒有考慮。本論文搜集的多媒體主要包括三類：音頻、視頻、動 畫。它們的格式如下： 音頻：m p 3 、f l a c 、w a v 、w m a 、m i d i 、m 、f l u 。其中以m p 3 、w a y 、m i d i 、w m a 、這 四種格式為主。 視頻：a v i 、m p e g 、r m v b 、w m v 、m o v 、a s f , m p e 、m p g 、v o b 、d a t 、m l v 、m 2 v 、 d i v x 。其中以a v i 、m p e g 、w m v 、r m v b 、a s f , m o v i e _ 六種格式為主。 動畫：s w f o 1 3 3 主題選擇 在進行主題搜索的時候，首先要弄明白一個問題什么是主題。針對不同主題 的搜索系統(tǒng)，必須進行有效的主題選擇，這樣才能搜索到我們真正需要的主題頁面。 5 山東師范大學(xué)碩士學(xué)位論文 一個主題就是一個“含義 ，也可以叫做一個“概念 ，它可以是一個詞，也可以是一 個短語，甚至是一個段落或者一篇文章。這個“概念的范圍可大可小，大的時候非 常廣泛，但同時意義也非常模糊；小的時候非常狹義，但這時它的意義卻非常具體。 因此系統(tǒng)在設(shè)計時需要考慮到主題變化的方便性。 搜索引擎返回結(jié)果的用戶滿意度在很大程度上決定于關(guān)鍵詞的選擇，現(xiàn)實中的主 題范圍太廣泛，有些主題沒有實際用途上的意義( “假如，并且 等) ；而有些主題卻 又不能引起人們搜索的興趣( “走 等) 。為此，在設(shè)計系統(tǒng)時有必要對主題進行統(tǒng)一 的分類，這有利于主題搜索系統(tǒng)從合適的主題范圍和主題角度進行搜索。目前很多搜 索系統(tǒng)主題的選擇采用y a h o o 主題分類目錄，也有選擇其它分類目錄的，但所選擇的分 類目錄必須是分類比較合理，同時具有一定的權(quán)威性。本論文主要研究教育領(lǐng)域的多 媒體資源搜索，對教育主題的選擇將在5 1 1 節(jié)中進行詳細介紹。 1 4 本文的主要工作和組織結(jié)構(gòu) 主題搜索算法是目前主題搜索領(lǐng)域研究的熱點，同樣也是難點，但在多媒體主題 搜索領(lǐng)域相關(guān)的研究還很少，簡單地將主題搜索算法運用于多媒體資源的主題搜索過 程中，并不能取得良好的效果。本文首先分析了多媒體資源在網(wǎng)頁中分布的特點，在 此基礎(chǔ)上對傳統(tǒng)的主題搜索算法進行相關(guān)參數(shù)的改進，使之應(yīng)用于網(wǎng)絡(luò)多媒體資源主 題搜索領(lǐng)域中。同時，提出一種基于u r l 鏈接規(guī)則的多媒體主題搜索算法，通過實驗 結(jié)果驗證基于u r l 鏈接規(guī)則的多媒體主題搜索算法，更能有效地提高多媒體資源主題 搜索的查準率和查全率。 1 4 1 本文的工作 本論文以網(wǎng)絡(luò)上包含教育多媒體資源的網(wǎng)頁為研究對象，在已有主題搜索器的基 礎(chǔ)上，重點研究多媒體主題搜索算法，用于提高網(wǎng)絡(luò)多媒體資源的主題搜索效率。主 要工作包括以下幾個方面： 1 深入分析包含多媒體資源的主題頁面在w e b 上的分布特征，通過采用通用搜索算 法對種子網(wǎng)站進行搜索實驗的結(jié)果分析，提出包含多媒體資源的網(wǎng)頁在w e b 存在著“資 源相鄰性”的特點。 2 對傳統(tǒng)的主題搜索算法進行分析，同時針對包含多媒體資源的網(wǎng)頁在w e b 中分布 的特點，對t o p i c p a g e r a n k 算法、s h a r k s e a r c h 算法進行相關(guān)參數(shù)的改進，使它們應(yīng) 用于多媒體資源的主題搜索領(lǐng)域，并詳細介紹了這兩種算法的改進過程。 6 山東師范大學(xué)碩士學(xué)位論文 3 根據(jù)包含多媒體資源的網(wǎng)頁在w e b 中呈現(xiàn)出“資源相鄰性 的特點，提出一種基 于u r l 鏈接規(guī)則的多媒體資源主題搜索算法，并詳細介紹了算法的實現(xiàn)細節(jié)和過程。 4 在同一軟、硬件平臺上，在已有的主題搜索器系統(tǒng)上，對t o p i c p a g e r a n k 算法、 改進s h a r k - s e a r c h 算法、基于u r l 鏈接規(guī)則算法進行測試，通過實驗結(jié)果證明基于u r l 鏈接規(guī)則的多媒體主題搜索算法，在多媒體資源主題搜索領(lǐng)域具有較高的查準率和查 全率。 1 4 2 本文的組織結(jié)構(gòu) 本文共分六章： 第一章緒論。主要介紹了多媒體資源主題搜索的現(xiàn)狀和相關(guān)技術(shù)，同時也對多媒 體資源的文件格式、多媒體資源主題的確定做了簡單的介紹。 第二章網(wǎng)絡(luò)多媒體w e b 頁面主題信息提取。本章首先介紹了h t m l 文檔中與多媒體 資源有關(guān)的文本信息，然后詳細介紹了h t m l 文檔中能夠表征多媒體資源信息的相關(guān)標 簽，最后對主題頁面在w e b 中分布的特征進行了簡單的闡述。 第三章主題搜索算法研究。本章對目前主流的幾種主題搜索算法進行了詳細的介 紹，結(jié)合多媒體資源在w e b 中分布的特點，選擇p a g e r a n k 算法和s h a r k - s e a r c h 算法進行 相關(guān)參數(shù)的改進，并詳細介紹了算法改進的過程。 第四章基于u r l 鏈接規(guī)則的多媒體主題搜索算法。本章詳細介紹了h t m l 解析器的 實現(xiàn)過程和文本信息處理、超鏈接分析和處理的關(guān)鍵技術(shù)，為多媒體主題搜索算法的 設(shè)計打下了基礎(chǔ)。通過實驗驗證了包含多媒體網(wǎng)頁的“資源相鄰性 特點，詳細介紹 了u r l 數(shù)據(jù)結(jié)構(gòu)、u r l 距離的度量以及u r l 正則表達式的學(xué)習(xí)和指導(dǎo)過程，對p a g e r a n k 算法進行改進，提出一種基于u r l 鏈接規(guī)則的多媒體主題搜索算法。 第五章實驗系統(tǒng)與測試分析。本章我們給出了系統(tǒng)的實現(xiàn)平臺以及三種算法的測 試結(jié)果，從查準率和查全率兩個方面對三種算法進行比較，并對實驗結(jié)果進行分析。 7 山東師范大學(xué)碩士學(xué)位論文 第二章網(wǎng)絡(luò)多媒體w e b 頁面主題信息提取 目前大部分網(wǎng)頁采用半結(jié)構(gòu)化的h t m l ( h y p e r t e x tm a r k - u pl a n g u a g e ) i 吾言編寫， 主題搜索器搜索頁面時遇到的首要問題就是解析這些h t m l 頁面，并且提取出h t m l 頁 面中包含的結(jié)構(gòu)信息和內(nèi)容信息。一般的，篇h t m l 文檔主要由文本、標簽、注釋這 三部分組成。文本是指我們在h t m l 文檔中看到的詞句，除了腳本語言和注釋，h t m l 文檔中的所有數(shù)據(jù)，只要不是標簽的組成部分，我們都可以將其認為是文本。文本是 格式化的，并且由嵌套它的標簽控制，如： 基礎(chǔ)教育資源網(wǎng) 。處于不同 標簽內(nèi)的文本傳遞的信息也是不同的，利用標簽在網(wǎng)頁中的重要程度，我們可以確定 此文本對網(wǎng)頁主題的貢獻率。 2 1h t m l 簡介 h t m l 是超文本標記語言的縮寫，由t i m eb e r b e r s l e e 在1 9 0 0 年提出，它是用于書 寫超文本文檔的語言規(guī)范，目前它已經(jīng)成為w e b 上的一種通用的描述語言。h t m l 用描 述性的標簽( 或稱為標記) 來指明文檔的不同內(nèi)容，把h t m l 文檔劃分成不同的邏輯結(jié) 構(gòu)，如段落、標題和表格等。h t m l 標簽有兩個作用：一是定義文檔結(jié)構(gòu)，便于瀏覽器 顯示該文檔；二是提供各種鏈接，把w e b 搜索器的搜索程序引導(dǎo)到該文檔的關(guān)鍵區(qū)域。 在其數(shù)年的演變過程中，h t m l 基于需求不斷地更新，1 9 9 7 年w 3 c 推出了h t m l 4 0 作 為推薦規(guī)范。 2 1 1h t m l 解析器 在主題搜索器中，h t m l 解析器的主要功能是從h t m l 源文件中分析出h t m l 文檔 中的鏈接結(jié)構(gòu)，提取出其中包含的鏈接地址，使主題搜索器能夠按照鏈接地址繼續(xù)向 前搜索，h t m l 4 0 1 規(guī)范中可以看到h t m l 文檔主要有如下四種鏈接結(jié)構(gòu)： ( a n c h o r ) t a g s 、i m g ( i m a g e ) t a g s 、 a n d t a g s 齊f l a n d t a g s 。這四種鏈接 結(jié)構(gòu)都有很多屬性與之相聯(lián)系，具體屬性描述略。 h t m l 解析的過程是將h t m l 文檔的流式數(shù)據(jù)結(jié)構(gòu)化的過程。根據(jù)h t m l 的語法定 義，依次對輸入的h t m l 文檔詞法和語法進行分析，其中詞法分析是為了從字符流中識 別出有意義的符號，這些符號是h t m l 語法的最小單位，包括標簽、無標簽文本單詞、 注釋以及處理指令等。同時，h t m l 解析器依據(jù)h t m l 語法確定這些符號之間的關(guān)系， 8 山東師范大學(xué)碩士學(xué)位論文 如標簽與標簽之間的層次包含關(guān)系等。最后，h t m l 解析器將解析的結(jié)果以語法書的形 式輸出。 目前有公司和個人開發(fā)的h t m l 解析器非常多，如w 3 c 提供的c t i d y 軟件以及i b m 開發(fā)的x e r c e s 等。然而，不同用途的主題搜索器對于h t m l 解析器在性能和功能上有不 同的特殊要求。首先，w e b 文檔書寫的不規(guī)范造成了許多w e b 文檔不合法，為保證解析 過程的順暢進行，必須特別考慮h t m l 解析器的容錯性。其次，為了適應(yīng)w e b 搜索器處 理的需要，需要提供專用的訪問接口( 如訪問頁面鏈接的接口) 。 2 1 2h t m l 文檔中多媒體相關(guān)文本信息 h t m l 文檔中包含很多信息，本文在對h t m l 頁面進行解析時，只提取有助于揭 示頁面主題和多媒體主題的部分信息，包括：( 1 ) 元信息；( 2 ) 網(wǎng)頁標題；( 3 ) 鏈接 內(nèi)容信息，包括u r l 地址信息和鏈接錨文本信息；( 4 ) 鏈接結(jié)構(gòu)信息，包括父鏈接的 信息和兄弟鏈接的信息；( 5 ) 在第三類、第四類信息基礎(chǔ)上得到的信息，包括網(wǎng)頁的 物理層、邏輯層、網(wǎng)頁的鏈接數(shù)量、網(wǎng)頁是否包含多媒體、某網(wǎng)頁鏈接兄弟鏈接的數(shù) 量、某網(wǎng)頁鏈接包含多媒體的兄弟鏈接的數(shù)量、網(wǎng)頁鏈接的錨文本路徑信息，網(wǎng)頁鏈 接的u r l 路徑信息以及結(jié)合中英文分詞詞典和主題詞典產(chǎn)生的u r l 翻譯后的中文文本 信息等；( 6 ) 其他與主題內(nèi)容無關(guān)的，但在設(shè)計搜索算法時需要用到的信息，包括頁 面的訪問時間、頁面的錯誤信息等。以下對這幾類信息進行簡單的介紹。 1 元信息 元信息即通常所說的m e t a 標簽所包含的信息。本文只提取其中的k e y w o r d s ( 關(guān)鍵 字) 和d e s c r i p t i o n ( 簡介) 這兩種信息。k e y w o r d s 為搜索引擎提供關(guān)鍵字列表，在h t m l 文檔中的用法為 ；d e s c r i p t i o n 用來告訴搜索引擎網(wǎng)站的主要內(nèi)容，在h t m l 文檔中的用法為 。此類信息對網(wǎng)頁主題有重要的指示 作用。 2 網(wǎng)頁標題 網(wǎng)頁標題是網(wǎng)頁源代碼中 和 標記之間的文字，也就是出現(xiàn)在瀏覽器 界面的最左上方的文本內(nèi)容。網(wǎng)頁標題中的內(nèi)容一般與網(wǎng)頁的主題關(guān)系非常密切，起 著概括全篇的作用。有人做過相關(guān)統(tǒng)計，如果標題中出現(xiàn)與某個主題相關(guān)的關(guān)鍵詞， 那么其主要內(nèi)容與該主題也相關(guān)的網(wǎng)頁數(shù)量占全部網(wǎng)頁數(shù)量的9 7 8 。因此在判斷網(wǎng)頁 9 山東師范大學(xué)碩士學(xué)位論文 內(nèi)容與查詢主題相關(guān)度時，可以對出現(xiàn)在標題中的關(guān)鍵詞賦較高的權(quán)值。 3 鏈接內(nèi)容信息 鏈接內(nèi)容信息包括網(wǎng)頁u r l 地址信息和網(wǎng)頁錨文本信息。一般的網(wǎng)頁制作者，都 習(xí)慣于在自己制作的頁面所對應(yīng)的u r l 中，加入與該頁面主題相關(guān)的信息來反映頁面 的主題，比如某個u r l 地址為h t t p ：l w w w c b e 2 1 c o m s u b j e c v p h y s i c s ，那么該頁面就很可 能與“物理學(xué)科”這個主題有關(guān)。錨文本即超鏈接文本( a n c h o r ) ，它也對該鏈接所指 向的頁面也起到了概括描述作用，這種概括在一定程度上可能會比該頁面的作者所作 的概括更為可觀、準確。比如 物理 f l a s h 課件砒 ，錨文本所鏈接的網(wǎng)頁主題就很可能是關(guān)于“高一化學(xué)f l a s h 課件 方面 的。 4 鏈接結(jié)構(gòu)信息 在分析鏈接結(jié)構(gòu)對網(wǎng)頁主題貢獻率的時候，我們提取父鏈接和兄弟鏈接兩部分信 息。如果網(wǎng)頁p 包含兩個鏈接r 和q ，我們稱鏈接p 是鏈接r 和v 的父鏈接，鏈接r 和v 是 鏈接p 的子鏈接，鏈接r 和鏈接v 互稱為兄弟鏈接。根據(jù)主題頁面的主題關(guān)聯(lián)特征，可以 得出下面的結(jié)論： ( 1 ) 如果父鏈接指向的頁面內(nèi)容與主題相關(guān)度較高，那么父鏈接所包含的子鏈接 與主題的相關(guān)度可能也較高； ( 2 ) 如果兄弟鏈接指向的頁面內(nèi)容大部分與主題的相關(guān)度較高，那么鏈接的其他 兄弟鏈接指向的頁面也可能與主題相關(guān)。 因此把鏈接的父鏈接和兄弟鏈接所包含的信息提取出來，作為判斷鏈接主題相關(guān) 度的一個影響因素。 2 1 3 表征多媒體信息的相關(guān)標簽介紹 w e b 中