信息檢索實(shí)驗(yàn)報(bào)告

1、信息檢索課程結(jié)業(yè)報(bào)告姓 名：學(xué) 號：計(jì)算機(jī)科學(xué)與技術(shù)所學(xué)專業(yè)：信息檢索報(bào)告報(bào)告題目：2014-4-4提交日期：信息檢索與web搜索應(yīng)用背景及概念信息檢索（Information Retrieval）是指信息按一定的方式組織起來，并根據(jù)信息用戶的需要找出有關(guān)的信息的過程和技術(shù)。狹義的信息檢索就是信息檢索過程的后半部分，即從信息集合中找出所需要的信息的過程，也就是我們常說的信息查尋（Information Search 或Information Seek）。信息檢索起源于圖書館的參考咨詢和文摘索引工作，從19世紀(jì)下半葉首先開始發(fā)展，至20世紀(jì)40年代，索引和檢索成已為圖書館獨(dú)立的工具和用戶服務(wù)項(xiàng)目

2、。隨著1946年世界上第一臺電子計(jì)算機(jī)問世，計(jì)算機(jī)技術(shù)逐步走進(jìn)信息檢索領(lǐng)域，并與信息檢索理論緊密結(jié)合起來；脫機(jī)批量情報(bào)檢索系統(tǒng)、聯(lián)機(jī)實(shí)時(shí)情報(bào)檢索系統(tǒng)。信息檢索有廣義和狹義的之分。廣義的信息檢索全稱為“信息存儲與檢索”，是指將信息按一定的方式組織和存儲起來，并根據(jù)用戶的需要找出有關(guān)信息的過程。狹義的信息檢索為“信息存儲與檢索”的后半部分，通常稱為“信息查找”或“信息搜索”，是指從信息集合中找出用戶所需要的有關(guān)信息的過程。狹義的信息檢索包括3個方面的含義：了解用戶的信息需求、信息檢索的技術(shù)或方法、滿足信息用戶的需求。搜索引擎(Search Engine，簡稱SE)是實(shí)現(xiàn)如下功能的一個系統(tǒng)：收集、整

3、理和組織信息并為用戶提供查詢服務(wù)。面向WEB的SE是其中最典型的代表。三大特點(diǎn)：事先下載，事先組織，實(shí)時(shí)檢索。垂直搜索引擎：垂直搜索引擎為2006年后逐步興起的一類搜索引擎。不同于通用的網(wǎng)頁搜索引擎，垂直搜索專注于特定的搜索領(lǐng)域和搜索需求（例如：機(jī)票搜索、旅游搜索、生活搜索、小說搜索、視頻搜索等等），在其特定的搜索領(lǐng)域有更好的用戶體驗(yàn)。相比通用搜索動輒數(shù)千臺檢索服務(wù)器，垂直搜索需要的硬件成本低、用戶需求特定、查詢的方式多樣。Web檢索的歷史：1989年，伯納斯·李在日內(nèi)瓦歐洲離子物理研究所（CERN）開發(fā)計(jì)算機(jī)遠(yuǎn)程控制時(shí)首次提出了Web概念，并在1990年圣誕節(jié)前推出了第一個瀏覽器。

4、 接下來的幾年中，他設(shè)計(jì)出HTTP、URL和HTML的規(guī)范，使網(wǎng)絡(luò)能夠?yàn)槠胀ù蟊娝鶓?yīng)用 。Ted Nelson 在1965年提出了超文本的概念.超文本傳輸協(xié)議(HTTP，HyperText Transfer Protocol)是互聯(lián)網(wǎng)上應(yīng)用最為廣泛的一種網(wǎng)絡(luò)傳輸協(xié)議，超文本標(biāo)注語言（HTML）。1993, 早期的 web robots (spiders) 用于收集 URL: Wanderer、ALIWEB (Archie-Like Index of the WEB)、WWW Worm (indexed URLs and titles for regex search)。1994, Stanfo

5、rd 博士生 David Filo and Jerry Yang 開發(fā)手工劃分主題層次的雅虎網(wǎng)站。1994年初，WebCrawler是互聯(lián)網(wǎng)上第一個支持搜索文件全部文字的全文搜索引擎，在它之前，用戶只能通過URL和摘要搜索，摘要一般來自人工評論或程序自動取正文的前100個字。Lycos（Carnegie Mellon University Center for Machine Translation Announces Lycos ）是搜索引擎史上又一個重要的進(jìn)步。除了相關(guān)性排序外，Lycos還提供了前綴匹配和字符相近限制，Lycos第一個在搜索結(jié)果中使用了網(wǎng)頁自動摘要，而最大的優(yōu)勢還是它遠(yuǎn)勝

6、過其它搜索引擎的數(shù)據(jù)量 。DEC的AltaVista 是一個遲到者，1995年12月才登場亮相. AltaVista是第一個支持自然語言搜索的搜索引擎，AltaVista是第一個實(shí)現(xiàn)高級搜索語法的搜索引擎（如AND, OR, NOT等) 。1995年博士生Larry Page開始學(xué)習(xí)搜索引擎設(shè)計(jì)，于1997年9月15日注冊了的域名，1997年底，開始提供Demo。1999年2月，Google完成了從Alpha版到Beta版的蛻變。Google公司則把1998年9月27日認(rèn)作自己的生日。Google在Pagerank、動態(tài)摘要、網(wǎng)頁快照、多文檔格式支持、地圖股票詞典尋人等集成搜索、多語言支持、用

7、戶界面等功能上的革新，象Altavista一樣，再一次永遠(yuǎn)改變了搜索引擎的定義。主要的進(jìn)步在于應(yīng)用鏈接分析根據(jù)權(quán)威性對部分結(jié)果排序 。北大天網(wǎng) 是國家“九五”重點(diǎn)科技攻關(guān)項(xiàng)目“中文編碼和分布式中英文信息發(fā)現(xiàn)”的研究成果，由北大計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)研究室開發(fā)，于1997年10月29日正式在CERNET上提供服務(wù)。 2000年1月，超鏈分析專利發(fā)明人、前Infoseek資深工程師李彥宏與好友徐勇（加州伯克利分校博士）在北京中關(guān)村創(chuàng)立了百度（Baidu）公司2001年8月發(fā)布B搜索引擎Beta版（此前Baidu只為其它門戶網(wǎng)站搜狐新浪Tom等提供搜索引擎）。2001年10月22日正式發(fā)

8、布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ù)以百萬計(jì)的不同服務(wù)器上，沒有預(yù)先定義的拓?fù)浣Y(jié)構(gòu)相連。不穩(wěn)定的數(shù)據(jù)高比例：許多文檔迅速地添加或刪除 (e.g. dead links).大規(guī)模：網(wǎng)絡(luò)數(shù)據(jù)量的指數(shù)增長，由此引發(fā)了一系列難以處理的規(guī)模問題。無結(jié)構(gòu)和冗余信息：每個HTML頁面沒有統(tǒng)一的結(jié)構(gòu), 許多網(wǎng)絡(luò)數(shù)據(jù)是重復(fù)的，將近 30% 的重復(fù)網(wǎng)頁.數(shù)據(jù)的質(zhì)量: 許多內(nèi)容沒有經(jīng)過編輯處理，數(shù)據(jù)可能是

9、錯誤的，無效的。錯誤來源有錄入錯誤，語法錯誤，OCR錯誤等。異構(gòu)數(shù)據(jù)：多媒體數(shù)據(jù)(images, video, VRML), 語言,字符集等. Web檢索的基本過程：網(wǎng)頁爬行下來預(yù)處理：網(wǎng)頁去重，正文提取，分詞等建立索引接受用戶請求，檢索詞串的處理，查詢重構(gòu)找到滿足要求的列表根據(jù)連接和文本中的詞進(jìn)行排序輸出信息采集：信息采集是指為出版的生產(chǎn)在信息資源方面做準(zhǔn)備的工作，包括對信息的收集和處理。它是選題策劃的直接基礎(chǔ)和重要依據(jù)。信息采集工作最后一個步驟的延伸，成選題策劃的開端。信息采集系統(tǒng)：信息采集系統(tǒng)以網(wǎng)絡(luò)信息挖掘引擎為基礎(chǔ)構(gòu)建而成,它可以在最短的時(shí)間內(nèi),幫您把最新的信息從不同的Internet

10、站點(diǎn)上采集下來,并在進(jìn)行分類和統(tǒng)一格式后,第一時(shí)間之內(nèi)把信息及時(shí)發(fā)布到自己的站點(diǎn)上去。從而提高信息及時(shí)性和節(jié)省或減少工作量。網(wǎng)絡(luò)爬蟲，是一種自動獲取網(wǎng)頁內(nèi)容的程序，是搜索引擎的重要組成部分，因此搜索引擎優(yōu)化很大程度上就是針對爬蟲而做出的優(yōu)化。倒排索引：倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來查找記錄。這種索引表中的每一項(xiàng)都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。倒排文件（倒排索引），索引對象是文檔或者

11、文檔集合中的單詞等，用來存儲這些單詞在一個文檔或者一組文檔中的存儲位置，是對文檔或者文檔集合的一種最常用的索引機(jī)制。建立倒排索引目的：對文檔或文檔集合建立索引，以加快檢索速度倒排文檔（或倒排索引）是一種最常用的索引機(jī)制倒排文檔的索引對象是文檔或文檔集合中的單詞等。例如，有些書往往在最后提供的索引（單詞頁碼列表對），就可以看成是一種倒排索引倒排索引的組成：倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄表（posting list）詞匯表是文本或文本集合中所包含的所有不同單詞的集合。對于詞匯表中的每一個單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號構(gòu)成一個列表，所有這些列表的集合就

12、稱為記錄表。相關(guān)工具1 ltp-Java版分詞工具1.1文件_irlas.dll, _wsd.dll : 分詞工具所需要的動態(tài)鏈接庫，放在java工程的根目錄下。nlptools.jar : jar文件。resource : 分詞所需要的資源，需放在放在java工程的根目錄下。1.2 使用方法下面將列出在實(shí)驗(yàn)過程中可能使用到的類：1) edu.hit.irlab.nlp.splitsentences.SplitSentences將中文文本按照有分割意義的標(biāo)點(diǎn)符號(如句號)分開，以句子的序列方式返回。輸入為中文文本，輸出為中文句子的序列。例如：SplitSentences sentenceSpl

13、it = new SplitSentences();List<String> sentences = sentenceSplit.getSentences(text);sentences是對text分句之后的句子集合。2) edu.hit.irlab.nlp.irlas.IRLAS分詞以及詞性標(biāo)注，使用方法如下：irlas = new IRLAS();irlas.loadResource();/調(diào)用分詞方法前必須先加載資源Vector<String> words = new Vector<String>();/用來存儲分詞結(jié)果Vector<String

14、> posTags = new Vector<String>();/用來存儲詞性標(biāo)注結(jié)果，標(biāo)點(diǎn)符號的詞性是“wp”。irlas.wordSegment(sentence, words, posTags);/調(diào)用分詞以及詞性標(biāo)注方法使用該文件可以將文件里的文本自動變成一個一個關(guān)鍵詞，并且統(tǒng)計(jì)出此關(guān)鍵詞出自哪個文檔，建立哈希表進(jìn)行存儲，再存儲在txt文件中。2 DownloadURL類edu.hit.irlab.util.web.DownloadURL類封裝在nlptools中，包含一些常見的web操作，如下載網(wǎng)頁、判斷編碼格式等。請?zhí)貏e注意：Google的檢索結(jié)果在本程序發(fā)送的

15、FF的head的情況下，沒有編碼信息。 所以在爬Google的檢索結(jié)果的時(shí)候請務(wù)必手動指定使用UTF-8編碼。表格 1 DownloadURL類的方法介紹構(gòu)造方法摘要DownloadURL() 方法摘要static java.lang.StringdecodeContent(java.lang.String byteCode, java.lang.String encoding)  根據(jù)字節(jié)碼和相應(yīng)的編碼，將內(nèi)容轉(zhuǎn)換成對應(yīng)的原始文字static java.lang.StringdownURL(java.lang.String

16、 urladdr, java.lang.String type) 給定URL以及網(wǎng)頁，爬取網(wǎng)頁內(nèi)容，如果網(wǎng)頁有指定編碼，則本程序會自動判斷編碼。若網(wǎng)頁沒有指定編碼，則默認(rèn)為GB18030編碼（兼容GBK，GB2312）type：模擬瀏覽器抓取網(wǎng)頁，瀏覽器類型；IE8.0 or FF3.0static java.lang.StringdownURL(java.lang.String urladdr, java.lang.String encoding, java.lang.String type) 給定URL以及網(wǎng)頁

17、的編碼，爬取網(wǎng)頁內(nèi)容type：模擬瀏覽器抓取網(wǎng)頁，瀏覽器類型; IE8.0 or FF3.0static java.lang.StringencodeContent(java.lang.String content, java.lang.String encoding) 給定內(nèi)容和編碼，將內(nèi)容轉(zhuǎn)換成編碼對應(yīng)的字節(jié)碼static voidmain(java.lang.String args)            下面

18、是一個下載“”網(wǎng)頁的例子：/模擬IE8，以gb2312的編碼格式下載“”的內(nèi)容。String content = DownloadURL.downURL(“”, “gb2312”, "IE8.0")  正文提取算法：將網(wǎng)頁源代碼中的HTML格式信息刪除，每行僅保留文本內(nèi)容，即文本行。接下來，正文內(nèi)容塊的抽取可以被看成一個優(yōu)化問題，即計(jì)算行和，用于最大化低于行和高于行的非文本字符數(shù)，以及在行和行之間的行文本字符數(shù)，相應(yīng)的就是最大化對應(yīng)的目標(biāo)函數(shù)，如公式所示。 其中，是原始網(wǎng)頁源代碼中行的總字符數(shù)，是剔除HTML標(biāo)簽后行的的文本字符數(shù)，為網(wǎng)頁源代碼總行數(shù)，編號從0到。

19、算法不需要針對特定網(wǎng)頁書寫正則表達(dá)式，不需要解析HTML以建立DOM結(jié)構(gòu)，不被病態(tài)的HTML標(biāo)簽所累，可以高效、準(zhǔn)確地定位網(wǎng)頁正文內(nèi)容塊。實(shí)驗(yàn)相關(guān)流程1. 基本流程和模塊大致如下圖所示：2. 爬取網(wǎng)頁的基本流程如下圖所示：3. 倒排索引的建立流程如下圖所示：4. 搜索過程流程如下圖所示：實(shí)驗(yàn)結(jié)果及分析：1. 爬取網(wǎng)頁的結(jié)果如下：初始網(wǎng)址：第一次爬取得到的網(wǎng)址保存到本地文件test0.txt中：然后循環(huán)讀取第一次爬取到的網(wǎng)址繼續(xù)爬取網(wǎng)址得到第二次爬取到的網(wǎng)址，保存在本地文件test1.txt中：考慮到時(shí)間和大小等因素，實(shí)驗(yàn)只爬取了兩層網(wǎng)址即停止。2. 提取正文：由于保存網(wǎng)址時(shí)使用哈希表存取，再寫

20、入本地文件，哈希表中使用網(wǎng)址作為key值，所以不會出現(xiàn)重復(fù)網(wǎng)址，即實(shí)現(xiàn)了網(wǎng)址去重，所以提取正文時(shí)只需循環(huán)讀取本地文件中保存的網(wǎng)址，用上面提到的正文提取方法提取正文即可，提取到的正文按順序?qū)懭氡镜匚募Aurlc中，文件中第一行為網(wǎng)頁的網(wǎng)址，后面為網(wǎng)頁正文,如下圖所示：本實(shí)驗(yàn)共提取了683篇正文：3. 建立倒排索引：利用分詞工具將提取到的正文分詞，即使用分詞工具將urlc文件夾中的文件內(nèi)容分詞，然后建立倒排索引，將建立好的倒排索引保存到本地文件irtable中：文件中第一項(xiàng)為關(guān)鍵詞，后面為關(guān)鍵詞出現(xiàn)的文檔序號，由于文檔中第一行為網(wǎng)址，所以根據(jù)文檔序號即可以得到改關(guān)鍵詞出現(xiàn)在哪一個網(wǎng)頁中。如果該關(guān)鍵

21、詞在正文中多次出現(xiàn)，那么改文檔號也會在改關(guān)鍵詞key對應(yīng)的value中多次出現(xiàn)，這樣在搜索過程中即可根據(jù)該詞在文檔中出現(xiàn)的頻率對輸出結(jié)果排序，出現(xiàn)頻率高的網(wǎng)頁會在前面顯示，出現(xiàn)頻率低的網(wǎng)頁會在后面顯示。4. 搜索：例如我們搜索“我在南海的回憶”，首先根據(jù)停用詞表會去除“在”、“的”這些對搜索沒有意義的詞匯：經(jīng)過去除停用詞之后分詞結(jié)果為：然后根據(jù)倒排索引搜索，并根據(jù)出現(xiàn)頻率排序，得到的結(jié)果如下：這3個詞在第264篇文檔中共出現(xiàn)了13次，網(wǎng)址為在第284篇文檔中出現(xiàn)了12次，網(wǎng)址為 ， 所以第264的網(wǎng)址排在了第284的前面。這里需要注意的是，第264篇文檔并以一定就是urlc文件夾中名為con264.txt這篇文檔，從網(wǎng)址我們可以看出：網(wǎng)址并非因?yàn)樵谧x取