大連理工大學搜索引擎與文本挖掘課程設計說明-搭建小型搜索引擎

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

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

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

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

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

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

7、00 設置寫斷點的時間間隔（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信息采集小結l 如何寫一個簡單的Spider程序？ 1、種子URL

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

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

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

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

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

13、verse DF）：逆文檔頻率 文檔的長度：長度歸一化(Length Normalization)352022-6-20查詢擴展362022-6-20Lucene介紹372022-6-20Lucene的其他語言版本382022-6-20Lucene功能392022-6-20Lucene系統(tǒng)的組織結構402022-6-20Lucene的索引文件格式412022-6-20簡單示例索引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();/合并子索引，從物理上刪除做過刪除標記的文檔 writer.close();/ IndexFiles422022-6-20簡單示例索引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: 從文本中提取要建索引的項(Term)l Document: 字段(

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

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

19、rcher.search(q); /查詢結果放在Hits類中（只存部分結果） 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服務提綱472022-6-20基于Tomcat的Web服務 CGI或腳本語言（ASP,PHP,JSP,etc） 功能 （1）獲取用戶查詢式：把用戶通過Form輸入的查詢語句封裝發(fā)送給檢索服務器 （2）顯示結果：從檢索服務器獲取結果，緩存并分頁呈現(xiàn)給用戶 Tomcat 5 JDK 1.5 + JSP482022-6-20用戶查詢界面492022-6-20結果顯示界面502022-6-20參考資料l Lucene in action（中文版）l 開發(fā)自己的搜索引擎:Lucene + Heritrixl Search Engines Information Retrieval in Practice512022-6-20作業(yè)要求l 動手搭建一個完整、可運行的小型全文檢