信息檢索實驗報告(共13頁)

1、PAGE PAGE 17信息檢索課程結(jié)業(yè)(ji y)報告姓 名：學(xué) 號：計算機科學(xué)與技術(shù)所學(xué)專業(yè)(zhuny)：信息檢索報告報告(bogo)題目：2014-4-4提交日期：信息檢索與web搜索(su su)應(yīng)用(yngyng)背景及概念信息檢索（Information Retrieval）是指信息按一定的方式組織起來，并根據(jù)信息用戶的需要(xyo)找出有關(guān)的信息的過程和技術(shù)。狹義的信息檢索就是信息檢索過程的后半部分，即從信息集合中找出所需要的信息的過程，也就是我們常說的信息查尋（Information Search 或Information Seek）。信息檢索起源于圖書館的參考咨詢和文摘索引

2、工作，從19世紀下半葉首先開始發(fā)展，至20世紀40年代，索引和檢索成已為圖書館獨立的工具和用戶服務(wù)項目。隨著1946年世界上第一臺電子計算機問世，計算機技術(shù)逐步走進信息檢索領(lǐng)域，并與信息檢索理論緊密結(jié)合起來；脫機批量情報檢索系統(tǒng)、聯(lián)機實時情報檢索系統(tǒng)。信息檢索有廣義和狹義的之分。廣義的信息檢索全稱為“信息存儲與檢索”，是指將信息按一定的方式組織和存儲起來，并根據(jù)用戶的需要找出有關(guān)信息的過程。狹義的信息檢索為“信息存儲與檢索”的后半部分，通常稱為“信息查找”或“信息搜索”，是指從信息集合中找出用戶所需要的有關(guān)信息的過程。狹義的信息檢索包括3個方面的含義：了解用戶的信息需求、信息檢索的技術(shù)或方法、

3、滿足信息用戶的需求。搜索引擎(Search Engine，簡稱SE)是實現(xiàn)如下功能的一個系統(tǒng)：收集、整理和組織信息并為用戶提供查詢服務(wù)。面向WEB的SE是其中最典型的代表。三大特點：事先下載，事先組織，實時檢索。垂直搜索引擎：垂直搜索引擎為2006年后逐步興起的一類搜索引擎。不同于通用的網(wǎng)頁搜索引擎，垂直搜索專注于特定的搜索領(lǐng)域和搜索需求（例如：機票搜索、旅游搜索、生活搜索、小說搜索、視頻搜索等等），在其特定的搜索領(lǐng)域有更好的用戶體驗。相比通用搜索動輒數(shù)千臺檢索服務(wù)器，垂直搜索需要的硬件成本低、用戶需求特定、查詢的方式多樣。Web檢索的歷史：1989年，伯納斯李在日內(nèi)瓦歐洲離子物理研究所（CE

4、RN）開發(fā)計算機遠程控制時首次提出了Web概念，并在1990年圣誕節(jié)前推出了第一個瀏覽器。 接下來的幾年中，他設(shè)計出HTTP、URL和HTML的規(guī)范，使網(wǎng)絡(luò)能夠為普通大眾所應(yīng)用 。Ted Nelson 在1965年提出了超文本的概念.超文本傳輸協(xié)議(HTTP，HyperText Transfer Protocol)是互聯(lián)網(wǎng)上應(yīng)用最為廣泛的一種網(wǎng)絡(luò)傳輸協(xié)議，超文本標注語言（HTML）。1993, 早期的 web robots (spiders) 用于收集 HYPERLINK URL:Wanderer URL: Wanderer、ALIWEB (Archie-Like Index of the W

5、EB)、WWW Worm (indexed URLs and titles for regex search)。1994, Stanford 博士生 David Filo and Jerry Yang 開發(fā)(kif)手工劃分主題層次的雅虎網(wǎng)站。1994年初(ninch)，WebCrawler是互聯(lián)網(wǎng)上第一個支持(zhch)搜索文件全部文字的全文搜索引擎，在它之前，用戶只能通過URL和摘要搜索，摘要一般來自人工評論或程序自動取正文的前100個字。Lycos（Carnegie Mellon University Center for Machine Translation Announces Ly

6、cos ）是搜索引擎史上又一個重要的進步。除了相關(guān)性排序外，Lycos還提供了前綴匹配和字符相近限制，Lycos第一個在搜索結(jié)果中使用了網(wǎng)頁自動摘要，而最大的優(yōu)勢還是它遠勝過其它搜索引擎的數(shù)據(jù)量 。DEC的AltaVista 是一個遲到者，1995年12月才登場亮相. AltaVista是第一個支持自然語言搜索的搜索引擎，AltaVista是第一個實現(xiàn)高級搜索語法的搜索引擎（如AND, OR, NOT等) 。1995年博士生Larry Page開始學(xué)習(xí)搜索引擎設(shè)計，于1997年9月15日注冊了的域名，1997年底，開始提供Demo。1999年2月，Google完成了從Alpha版到Beta版的

7、蛻變。Google公司則把1998年9月27日認作自己的生日。Google在Pagerank、動態(tài)摘要、網(wǎng)頁快照、多文檔格式支持、地圖股票詞典尋人等集成搜索、多語言支持、用戶界面等功能上的革新，象Altavista一樣，再一次永遠改變了搜索引擎的定義。主要的進步在于應(yīng)用鏈接分析根據(jù)權(quán)威性對部分結(jié)果排序 。北大天網(wǎng) 是國家“九五”重點科技攻關(guān)項目“中文編碼和分布式中英文信息發(fā)現(xiàn)”的研究成果，由北大計算機系網(wǎng)絡(luò)與分布式系統(tǒng)研究室開發(fā)，于1997年10月29日正式在CERNET上提供服務(wù)。2000年1月，超鏈分析專利發(fā)明人、前Infoseek資深工程師李彥宏與好友徐勇（加州伯克利分校博士）在北京中關(guān)

8、村創(chuàng)立了百度（Baidu）公司2001年8月發(fā)布B搜索引擎Beta版（此前Baidu只為其它門戶網(wǎng)站搜狐新浪Tom等提供搜索引擎）。2001年10月22日正式發(fā)布Baidu搜索引擎。Baidu雖然只提供中文搜索，但目前收錄中文網(wǎng)頁超過9000萬，可能是最大的的中文數(shù)據(jù)庫。Web搜索引擎系統(tǒng)組成：Web數(shù)據(jù)采集系統(tǒng)網(wǎng)頁預(yù)處理系統(tǒng)索引檢索系統(tǒng)檢索結(jié)果排序系統(tǒng)Web檢索所在現(xiàn)階段的挑戰(zhàn)：數(shù)據(jù)的分布性：文檔散落在數(shù)以百萬計的不同服務(wù)器上，沒有預(yù)先定義的拓撲結(jié)構(gòu)相連。不穩(wěn)定的數(shù)據(jù)高比例：許多文檔迅速地添加或刪除 (e.g. dead links).大規(guī)模：網(wǎng)絡(luò)數(shù)據(jù)量的指數(shù)增長，由此引發(fā)了一系列難以處理的

9、規(guī)模問題。無結(jié)構(gòu)(jigu)和冗余信息：每個HTML頁面沒有(mi yu)統(tǒng)一的結(jié)構(gòu), 許多網(wǎng)絡(luò)數(shù)據(jù)是重復(fù)(chngf)的，將近 30% 的重復(fù)網(wǎng)頁.數(shù)據(jù)的質(zhì)量: 許多內(nèi)容沒有經(jīng)過編輯處理，數(shù)據(jù)可能是錯誤的，無效的。錯誤來源有錄入錯誤，語法錯誤，OCR錯誤等。異構(gòu)數(shù)據(jù)：多媒體數(shù)據(jù)(images, video, VRML), 語言,字符集等. Web檢索的基本過程：網(wǎng)頁爬行下來預(yù)處理：網(wǎng)頁去重，正文提取，分詞等建立索引接受用戶請求，檢索詞串的處理，查詢重構(gòu)找到滿足要求的列表根據(jù)連接和文本中的詞進行排序輸出信息采集：信息采集是指為出版的生產(chǎn)在信息資源方面做準備的工作，包括對信息的收集和處理。它是選

10、題策劃的直接基礎(chǔ)和重要依據(jù)。信息采集工作最后一個步驟的延伸，成選題策劃的開端。信息采集系統(tǒng)：信息采集系統(tǒng)以網(wǎng)絡(luò)信息挖掘引擎為基礎(chǔ)構(gòu)建而成,它可以在最短的時間內(nèi),幫您把最新的信息從不同的Internet站點上采集下來,并在進行分類和統(tǒng)一格式后,第一時間之內(nèi)把信息及時發(fā)布到自己的站點上去。從而提高信息及時性和節(jié)省或減少工作量。網(wǎng)絡(luò)爬蟲，是一種自動獲取網(wǎng)頁內(nèi)容的程序，是搜索引擎的重要組成部分，因此 HYPERLINK /view/7147.htm t _blank 搜索引擎優(yōu)化很大程度上就是針對爬蟲而做出的優(yōu)化。倒排索引：倒排索引源于實際應(yīng)用中需要根據(jù)屬性的值來查找記錄。這種索引表中的每一項都包括一

11、個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。倒排文件（倒排索引），索引對象是文檔或者 HYPERLINK /view/5182467.htm t _blank 文檔集合中的單詞等，用來存儲這些單詞在一個文檔或者一組文檔中的存儲位置，是對文檔或者文檔集合的一種最常用的索引機制。建立倒排索引目的：對文檔或文檔集合建立索引，以加快檢索速度倒排文檔（或倒排索引）是一種最常用的索引機制倒排文檔的索引對象是文檔或文檔集合中

12、的單詞等。例如，有些書往往在最后提供的索引（單詞頁碼列表對），就可以看成是一種倒排索引倒排索引的組成：倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄表（posting list）詞匯表是文本或文本集合中所包含的所有不同單詞的集合。對于詞匯表中的每一個單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號構(gòu)成一個列表，所有這些列表的集合就稱為記錄表。相關(guān)(xinggun)工具ltp-Java版分詞(fn c)工具1.1文件(wnjin)_irlas.dll, _wsd.dll : 分詞工具所需要的動態(tài)鏈接庫，放在java工程的根目錄下。nlptools.jar : jar文件。resou

13、rce : 分詞所需要的資源，需放在放在java工程的根目錄下。1.2 使用方法下面將列出在實驗過程中可能使用到的類：edu.hit.irlab.nlp.splitsentences.SplitSentences將中文文本按照有分割意義的標點符號(如句號)分開，以句子的序列方式返回。輸入為中文文本，輸出為中文句子的序列。例如：SplitSentences sentenceSplit = new SplitSentences();List sentences = sentenceSplit.getSentences(text);sentences是對text分句之后的句子集合。edu.hit.i

14、rlab.nlp.irlas.IRLAS分詞以及詞性標注，使用方法如下：irlas = new IRLAS();irlas.loadResource();/調(diào)用分詞方法前必須先加載資源Vector words = new Vector();/用來存儲分詞結(jié)果Vector posTags = new Vector();/用來存儲詞性標注結(jié)果，標點符號的詞性是“wp”。irlas.wordSegment(sentence, words, posTags);/調(diào)用分詞以及詞性標注方法使用該文件可以將文件里的文本自動變成一個一個關(guān)鍵詞，并且統(tǒng)計出此關(guān)鍵詞出自哪個文檔，建立哈希表進行存儲，再存儲在txt

15、文件中。DownloadURL類edu.hit.irlab.util.web.DownloadURL類封裝在nlptools中，包含一些常見的web操作，如下載網(wǎng)頁(wn y)、判斷編碼格式等。請?zhí)貏e注意：Google的檢索結(jié)果在本程序發(fā)送的FF的head的情況(qngkung)下，沒有編碼信息。 所以在爬Google的檢索結(jié)果的時候請務(wù)必手動指定使用UTF-8編碼。表格(biog) SEQ 表格 * ARABIC 1 DownloadURL類的方法介紹構(gòu)造方法摘要 HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l DownloadURL()

16、DownloadURL()方法摘要staticjava.lang.String HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l decodeContent(java.lang.String, java.lang.String) decodeContent(java.lang.StringbyteCode, java.lang.Stringencoding)根據(jù)字節(jié)碼和相應(yīng)的編碼，將內(nèi)容轉(zhuǎn)換成對應(yīng)的原始文字staticjava.lang.String HYPERLINK F:.eduhitirlabutilwebDownloadURL.html

17、 l downURL(java.lang.String, java.lang.String) downURL(java.lang.Stringurladdr, java.lang.Stringtype)給定URL以及網(wǎng)頁，爬取網(wǎng)頁內(nèi)容，如果網(wǎng)頁有指定編碼，則本程序會自動判斷編碼。若網(wǎng)頁沒有指定編碼，則默認為GB18030編碼（兼容GBK，GB2312）type：模擬瀏覽器抓取網(wǎng)頁，瀏覽器類型；IE8.0 or FF3.0staticjava.lang.String HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l downURL(java.la

18、ng.String, java.lang.String, java.lang.String) downURL(java.lang.Stringurladdr, java.lang.Stringencoding, java.lang.Stringtype)給定URL以及網(wǎng)頁的編碼，爬取網(wǎng)頁內(nèi)容type：模擬瀏覽器抓取網(wǎng)頁，瀏覽器類型; IE8.0 or FF3.0staticjava.lang.String HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l encodeContent(java.lang.String, java.lang.Str

19、ing) encodeContent(java.lang.Stringcontent, java.lang.Stringencoding)給定內(nèi)容和編碼，將內(nèi)容轉(zhuǎn)換成編碼對應(yīng)的字節(jié)碼staticvoid HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l main(java.lang.String) main(java.lang.Stringargs)下面(xi mian)是一個下載“”網(wǎng)頁(wn y)的例子(l zi)：/模擬IE8，以gb2312的編碼格式下載“”的內(nèi)容。String content = HYPERLINK F:.eduhit

20、irlabutilwebDownloadURL.html l DownloadURL() DownloadURL. HYPERLINK F:.eduhitirlabutilwebDownloadURL.html l downURL(java.lang.String, java.lang.String, java.lang.String) downURL(“”, “gb2312”, IE8.0); 正文提取算法：將網(wǎng)頁源代碼中的HTML格式信息刪除，每行僅保留文本內(nèi)容，即文本行。接下來，正文內(nèi)容塊的抽取可以被看成一個優(yōu)化問題，即計算行和，用于最大化低于行和高于行的非文本字符數(shù)，以及在行和行之間的

21、行文本字符數(shù)，相應(yīng)的就是最大化對應(yīng)的目標函數(shù)，如公式所示。 其中，是原始網(wǎng)頁源代碼中行的總字符數(shù)，是剔除HTML標簽后行的的文本字符數(shù)，為網(wǎng)頁源代碼總行數(shù)，編號從0到。算法不需要針對特定網(wǎng)頁書寫正則表達式，不需要解析HTML以建立DOM結(jié)構(gòu)，不被病態(tài)的HTML標簽所累，可以高效、準確地定位網(wǎng)頁正文內(nèi)容塊。實驗相關(guān)流程基本流程和模塊大致如下圖所示：2. 爬取網(wǎng)頁的基本流程(lichng)如下圖所示：3. 倒排索引的建立流程(lichng)如下圖所示：4. 搜索(su su)過程流程如下圖所示：實驗結(jié)果(ji gu)及分析：爬取網(wǎng)頁的結(jié)果如下：初始網(wǎng)址：第一次爬取得到的網(wǎng)址保存到本地文件test0

22、.txt中：然后循環(huán)讀取第一次爬取到的網(wǎng)址繼續(xù)(jx)爬取網(wǎng)址得到第二次爬取到的網(wǎng)址，保存在本地文件test1.txt中：考慮到時間(shjin)和大小等因素，實驗只爬取了兩層網(wǎng)址即停止。提取(tq)正文：由于保存網(wǎng)址時使用哈希表存取，再寫入本地文件，哈希表中使用網(wǎng)址作為key值，所以不會出現(xiàn)重復(fù)網(wǎng)址，即實現(xiàn)了網(wǎng)址去重，所以提取正文時只需循環(huán)讀取本地文件中保存的網(wǎng)址，用上面提到的正文提取方法提取正文即可，提取到的正文按順序?qū)懭氡镜匚募Aurlc中，文件中第一行為網(wǎng)頁的網(wǎng)址，后面為網(wǎng)頁正文,如下圖所示：本實驗共提取了683篇正文：建立(jinl)倒排索引：利用分詞工具將提取到的正文分詞，即使用(

23、shyng)分詞工具將urlc文件夾中的文件內(nèi)容分詞，然后建立倒排索引，將建立好的倒排索引保存到本地文件irtable中：文件中第一項為關(guān)鍵詞，后面為關(guān)鍵詞出現(xiàn)的文檔序號，由于文檔中第一行為網(wǎng)址(wn zh)，所以根據(jù)文檔序號即可以得到改關(guān)鍵詞出現(xiàn)在哪一個網(wǎng)頁中。如果該關(guān)鍵詞在正文中多次出現(xiàn)，那么改文檔號也會在改關(guān)鍵詞key對應(yīng)的value中多次出現(xiàn)，這樣在搜索過程中即可根據(jù)該詞在文檔中出現(xiàn)的頻率對輸出結(jié)果排序，出現(xiàn)頻率高的網(wǎng)頁會在前面顯示，出現(xiàn)頻率低的網(wǎng)頁會在后面顯示。搜索：例如我們搜索“我在南海的回憶”，首先根據(jù)停用詞表會去除“在”、“的”這些對搜索沒有意義的詞匯：經(jīng)過去除停用詞之后分詞結(jié)

24、果為：然后根據(jù)倒排索引搜索，并根據(jù)出現(xiàn)頻率排序，得到的結(jié)果如下：這3個詞在第264篇文檔中共(zhn n)出現(xiàn)了13次，網(wǎng)址(wn zh)為 HYPERLINK / /，在第284篇文檔中出現(xiàn)(chxin)了12次，網(wǎng)址為 HYPERLINK /china/20120327/123486.shtml ， 所以第264的網(wǎng)址排在了第284 /china/20120327/123486.shtml ， 所以第264的網(wǎng)址排在了第284的前面。這里需要注意的是，第264篇文檔并以一定就是urlc文件夾中名為con264.txt這篇文檔，從網(wǎng)址我們可以看出：網(wǎng)址并非 HYPERLINK / /。因為在讀取文件時，其讀取順序跟文件在文件夾中的排列順序并不是完全一致的。結(jié)論：實驗爬取網(wǎng)頁使用的廣度優(yōu)先爬取，