大連理工大學(xué)搜索引擎與文本挖掘課程設(shè)計(jì)說明-搭建小型搜索引擎

1、22022-6-20l 聯(lián)系人：劉文飛l Email：l URL：http:/l 地址：創(chuàng)新園大廈A0923室聯(lián)系方式32022-6-20l 理解搜索引擎的工作原理l 搭建一個(gè)可運(yùn)行的實(shí)驗(yàn)系統(tǒng) 在理解搜索引擎原理及整體流程的基礎(chǔ)上，通過親自動(dòng)手搭建一個(gè)完整、可運(yùn)行的小型全文檢索實(shí)驗(yàn)系統(tǒng)訓(xùn)練目標(biāo)42022-6-20搜索引擎基本框架索引庫索引庫索索 引引 檢檢 索索 用用 戶戶 接接 口口spiderspider文檔庫文檔庫信息采集索引與檢索Web接口52022-6-20l Web信息的搜集l 基于Lucene的索引與檢索 l 基于Tomcat的Web服務(wù)提綱62022-6-20信息的搜集概念l

2、原理： 把整個(gè)互聯(lián)網(wǎng)看成一個(gè)大的圖，則信息搜集可以看成是圖的遍歷。 信息采集系統(tǒng)也常常稱為Robot, Spider, Crawler等等l 目標(biāo)： 快速獲得高質(zhì)量的網(wǎng)頁l 實(shí)際上是圖的遍歷過程 通過種子頁面或站點(diǎn)(Seed)，獲取更多的鏈接，將它們作為下一步種子，不斷循環(huán)。 這個(gè)過程一般永遠(yuǎn)不會(huì)結(jié)束！72022-6-20信息的搜集策略82022-6-20信息的搜集信息指紋的應(yīng)用l 概念 任何一段文字信息，都可以對(duì)應(yīng)一個(gè)不太長(zhǎng)的隨機(jī)數(shù)，作為區(qū)別它和其它信息的指紋（Fingerprint）。 如：MD5算法，可以把任意長(zhǎng)信息變換成定長(zhǎng)（128b）的整數(shù)l 信息指紋在爬蟲中的應(yīng)用 去重、壓縮920

3、22-6-20信息的搜集網(wǎng)頁的維護(hù)與更新l 批量搜集 每次搜集替換上一次的內(nèi)容 l 增量搜集 開始時(shí)搜集一批 往后：1、搜集新出現(xiàn)的網(wǎng)頁；2、搜集在上次搜集后有改變的網(wǎng)頁； 3、刪除上次搜集后不存在的網(wǎng)頁l 比較： 定期批量重采非常簡(jiǎn)單，但是浪費(fèi)帶寬，周期也長(zhǎng)； 增量采集可以節(jié)省帶寬，網(wǎng)頁更新周期相對(duì)較短，但是系統(tǒng)的復(fù)雜性增大。102022-6-20信息的搜集速度保證 局域網(wǎng)聯(lián)接多機(jī)進(jìn)行并行采集 廣域網(wǎng)分布式采集 多進(jìn)程并行 多線程并行112022-6-20信息的搜集質(zhì)量保證 URL重復(fù)的檢測(cè)和排除 內(nèi)容重復(fù)的檢測(cè)和排除 入度高的網(wǎng)頁相對(duì)重要 URL淺的網(wǎng)頁相對(duì)重要 含有被別人廣泛鏈接的內(nèi)容的

4、網(wǎng)頁重要122022-6-20信息的搜集“禮貌” 遵守網(wǎng)站上發(fā)布的Robots.txt 采集限制協(xié)議 搜集時(shí)盡量不要太過密集地采集某個(gè)網(wǎng)站 這種密集訪問類似于黑客攻擊，導(dǎo)致正常瀏覽網(wǎng)站產(chǎn)生困難。 有些網(wǎng)站會(huì)嚴(yán)密控制這種密集訪問行為。132022-6-20信息的搜集開源采集工具142022-6-20信息的搜集WeblechMIT Licence http:/ 使用方法： 1）按需求修改配置文件Sperties 2）運(yùn)行run.bat開始爬行 3）如果程序中斷，運(yùn)行resume.bat繼續(xù)爬行162022-6-20信息的搜集Weblech配置說明lsaveRootDirector

5、y = c:/weblech/sistes 設(shè)置文件的存放路徑，默認(rèn)為當(dāng)前文件夾lmailtoLogFile = mailto.txt 設(shè)置郵件鏈接(mailto links)的存放文件lrefreshHTMLs = true lrefreshImages = false lrefreshOthers = false /設(shè)置如果本 地硬盤已經(jīng)存在待爬取的文件，是否重新載入文件lhtmlExtensions = htm,html,shtm,shtml,asp,jsp,php 設(shè)置spider要下載資源的擴(kuò)展名limageExtensions = 同上lstartLocation = http:/

6、 設(shè)置spider爬行的起始頁面ldepthFirst = false 設(shè)置進(jìn)行廣度優(yōu)先爬行或深度優(yōu)先爬行l(wèi)maxDepth = 5 爬行的最大深度（第一個(gè)頁面深度為0，其鏈接的深度為1）lurlMatch 基本的URL過濾。下載的網(wǎng)頁的網(wǎng)址中中必須包括urlMatch串linterestingURLs= 優(yōu)先級(jí)最高的網(wǎng)頁lboringURLs= 優(yōu)先級(jí)最低的網(wǎng)頁lbasicAuthUser = myUser lbasicAuthPassword = 1234 設(shè)置需要驗(yàn)證的網(wǎng)站的用戶名和密碼lspiderThreads = 15 爬行的線程數(shù)lcheckpointInterval = 300

7、00 設(shè)置寫斷點(diǎn)的時(shí)間間隔（ms）172022-6-20信息的搜集Weblech類說明l 主要類 SpiderConfig.java HTMLParser.java DownloadQueue.java URLGetter.java URLObject.java Spider.java182022-6-20Weblech流程圖DownloadQueue.javaSpiderConfig.javaHTMLParser.javaURLGetter.javaSpider.javaURLObject.java192022-6-20Web信息采集小結(jié)l 如何寫一個(gè)簡(jiǎn)單的Spider程序？ 1、種子URL

8、隊(duì)列（List 1）； 2、Http協(xié)議，獲得url的內(nèi)容content，url URL完成隊(duì)列（List 2）； 3、存儲(chǔ)content； 4、解析content URLs； 5、判斷URLs是否在List 2中，如果否，加入到List 1中； 6、如果List 1非空，執(zhí)行2； 7、如果List 1為空，完成。l 要求： 利用Spider程序，完成網(wǎng)頁爬取工作。 1、開發(fā)一個(gè)spider程序，多線程，支持?jǐn)帱c(diǎn)續(xù)爬。 2、利用開源工具。202022-6-20l Web信息的搜集l 基于Lucene的索引與檢索 l 基于Tomcat的Web服務(wù)提綱212022-6-20基于Lucene的索引與

9、搜索 l 索引基本原理l 搜索基本原理l Lucene使用介紹222022-6-20索引基本原理 不可能是逐個(gè)文檔掃描(太慢) 反向索引、B+樹、簽名表等 Inverted file 所有的搜索引擎都用倒排索引 速度快232022-6-20前向索引(Forward index)文檔1文檔2a38b14c 610d29a15b28c 36d475710119242022-6-20反向索引(Inverted index)文檔ID號(hào)偏移位置dictionary文檔 list252022-6-20反向索引(Inverted index) 對(duì)字典排序 把字典讀入內(nèi)存 如果字典太大，對(duì)字典建立二級(jí)索引，把

10、字典的索引讀入內(nèi)存262022-6-20建立倒排索引的流程272022-6-20英文詞根還原(Stemming)282022-6-20中文分詞 例子：李明天天都準(zhǔn)時(shí)上班 字：李/明/天/天/都/準(zhǔn)/時(shí)/上/班索引量太大，查全率百分百，但是查準(zhǔn)率低；比如，查“明天” 這句話也會(huì)出來 詞：李明/天天/都/準(zhǔn)時(shí)/上班索引量大大降低，查準(zhǔn)率較高，查全率不是百分百，而且還會(huì)受分詞錯(cuò)誤的影響；比如，上面可能會(huì)切分成：李 明天 天都 準(zhǔn)時(shí) 上班 二字串：李明/明天/天天/天都/都準(zhǔn)/準(zhǔn)時(shí)/時(shí)上/上班292022-6-20去除停用詞302022-6-20檢索模型l 什么叫檢索？ 用戶提交一個(gè)查詢（Query）

11、，搜索引擎查找與該查詢相關(guān)結(jié)果的過程。l 檢索模型： 布爾模型 向量空間模型 概率模型 統(tǒng)計(jì)語言模型 312022-6-20布爾模型l 簡(jiǎn)單的檢索模型，建立在集合論和布爾代數(shù)的基礎(chǔ)上。l 遵循兩條基本規(guī)則: 每個(gè)索引詞在一篇文檔中只有兩種狀態(tài)：出現(xiàn)或不出現(xiàn)，對(duì)應(yīng)權(quán)值為 0或1。 查詢是由三種布爾邏輯運(yùn)算符 and, or, not 連接索引詞組成的布爾表達(dá)式。l 優(yōu)點(diǎn)： 簡(jiǎn)單，易于實(shí)現(xiàn)，能夠保證較高的查全率。l 缺點(diǎn)： 只能精確判斷文檔是否出現(xiàn)某一查詢?cè)~，但并沒有給出每個(gè)詞的重要程度，不能給出相關(guān)性排序322022-6-20布爾模型AND OR 332022-6-20向量空間模型l 查詢和文檔

12、都轉(zhuǎn)化成標(biāo)引項(xiàng)(Term)及其權(quán)重組成的向量表示 康奈爾大學(xué) Salton 1970年代提出并倡導(dǎo)，原型系統(tǒng)SMART 例如： 文檔1：(,)， 文檔2：(,) 查詢：(,) 查詢和文檔進(jìn)行向量的相似度計(jì)算：夾角余弦或者內(nèi)積 文檔1：1*1+3*2=7 文檔2：2*2=4 優(yōu)點(diǎn)：簡(jiǎn)潔直觀，效果好，可以應(yīng)用到很多其他領(lǐng)域。 缺點(diǎn)：理論上不夠完善，標(biāo)引項(xiàng)之間的獨(dú)立性假設(shè)與實(shí)際不符342022-6-20向量空間模型 TF（Term Frequency）：Term的頻度，TF越高權(quán)重越高 DF（Document Frequency）：Term的文檔頻度，DF越高區(qū)分度越低，因此權(quán)重也越低 IDF（In

13、verse DF）：逆文檔頻率 文檔的長(zhǎng)度：長(zhǎng)度歸一化(Length Normalization)352022-6-20查詢擴(kuò)展362022-6-20Lucene介紹372022-6-20Lucene的其他語言版本382022-6-20Lucene功能392022-6-20Lucene系統(tǒng)的組織結(jié)構(gòu)402022-6-20Lucene的索引文件格式412022-6-20簡(jiǎn)單示例索引void IndexFiles(String INDEX_DIR, String docDir) StandardAnalyzer myAnalyzer = newStandardAnalyzer();/分詞器 Ind

14、exWriter writer = newIndexWriter(INDEX_DIR,myAnalyzer, true); writer.setUseCompoundFile(false); /索引文件格式 writer.setMergeFactor(1000);/合并因子 indexDocs(writer, docDir); writer.optimize();/合并子索引，從物理上刪除做過刪除標(biāo)記的文檔 writer.close();/ IndexFiles422022-6-20簡(jiǎn)單示例索引static void indexDocs(IndexWriter writer, File fil

15、e) if (file.isDirectory() String files = file.list(); if (files != null) for (int i = 0; i files.length; i+) indexDocs(writer, new File(file, filesi); / 遞歸 else if (file.getName().endsWith(“.htm”) Document doc = new Document(); HTMLParser parser = new HTMLParser(fis); doc.add(new Field(“title”, pars

16、er.getTitle(), Field.Store.YES, Field.Index.TOKENIZED); doc.add(new Field(“content”, parser.getContent(), Field.Store.YES,Field.Index.TOKENIZED); writer.addDocument(doc);/ 添加片段到Lucene索引432022-6-20理解索引中的核心類l IndexWriter: 創(chuàng)建與更新索引數(shù)據(jù)l Directory: 獲取Lucene索引的位置l Analyzer: 從文本中提取要建索引的項(xiàng)(Term)l Document: 字段(

17、Field)的集合，可視為虛擬的文檔（網(wǎng)頁、Email或文本）l Field: 每個(gè)Document由一個(gè)或多個(gè)Field組成，每個(gè)Field對(duì)應(yīng)于可進(jìn)行索引和檢索的一部分?jǐn)?shù)據(jù)，即每個(gè)數(shù)據(jù)單元可以用（FieldName, Value）表示。442022-6-20Lucene的核心接口-檢索l IndexSearcher：打開并在索引數(shù)據(jù)中查找l Term：用于檢索的基本單位，形式為(Field，Value)l Query：檢索表達(dá)式類型 TermQuery：最基本的Query類型，返回在指定字段包含指定關(guān)鍵詞的文檔l QueryParser：解析用戶輸入的查詢q，生成Query對(duì)象l Hits

18、：檢索結(jié)果集452022-6-20簡(jiǎn)單示例檢索void SearchFiles(String path, String query) IndexReader reader = new IndexReader(path); /打開索引 Searcher searcher = new IndexSearcher(reader);/生成查詢器實(shí)例 Analyzer analyzer = new StandardAnalyzer(); /字符分析器 Query q = ueryParser.parse(userquery,”content”,analyzer);/分析用戶查詢 Hits h = sea

19、rcher.search(q); /查詢結(jié)果放在Hits類中（只存部分結(jié)果） for (int i=0; ih.length(); i+) Document doc = h.doc(i); System.out.println(“Result “ + i + doc.get(path); /for reader.close();/ SearchFiles462022-6-20l Web信息的搜集l 基于Lucene的索引與檢索 l 基于Tomcat的Web服務(wù)提綱472022-6-20基于Tomcat的Web服務(wù) CGI或腳本語言（ASP,PHP,JSP,etc） 功能 （1）獲取用戶查詢式：把用戶通過Form輸入的查詢語句封裝發(fā)送給檢索服務(wù)器 （2）顯示結(jié)果：從檢索服務(wù)器獲取結(jié)果，緩存并分頁呈現(xiàn)給用戶 Tomcat 5 JDK 1.5 + JSP482022-6-20用戶查詢界面492022-6-20結(jié)果顯示界面502022-6-20參考資料l Lucene in action（中文版）l 開發(fā)自己的搜索引擎:Lucene + Heritrixl Search Engines Information Retrieval in Practice512022-6-20作業(yè)要求l 動(dòng)手搭建一個(gè)完整、可運(yùn)行的小型全文檢