大连理工大学搜索引擎与文本挖掘课程设计说明-搭建小型搜索引擎

1、22022-6-20l 联系人：刘文飞l Email：l URL：http:/l 地址：创新园大厦A0923室联系方式32022-6-20l 理解搜索引擎的工作原理l 搭建一个可运行的实验系统 在理解搜索引擎原理及整体流程的基础上，通过亲自动手搭建一个完整、可运行的小型全文检索实验系统训练目标42022-6-20搜索引擎基本框架索引库索引库索索 引引 检检 索索 用用 户户 接接 口口spiderspider文档库文档库信息采集索引与检索Web接口52022-6-20l Web信息的搜集l 基于Lucene的索引与检索 l 基于Tomcat的Web服务提纲62022-6-20信息的搜集概念l

2、原理： 把整个互联网看成一个大的图，则信息搜集可以看成是图的遍历。 信息采集系统也常常称为Robot, Spider, Crawler等等l 目标： 快速获得高质量的网页l 实际上是图的遍历过程 通过种子页面或站点(Seed)，获取更多的链接，将它们作为下一步种子，不断循环。 这个过程一般永远不会结束！72022-6-20信息的搜集策略82022-6-20信息的搜集信息指纹的应用l 概念 任何一段文字信息，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint）。 如：MD5算法，可以把任意长信息变换成定长（128b）的整数l 信息指纹在爬虫中的应用 去重、压缩920

3、22-6-20信息的搜集网页的维护与更新l 批量搜集 每次搜集替换上一次的内容 l 增量搜集 开始时搜集一批 往后：1、搜集新出现的网页；2、搜集在上次搜集后有改变的网页； 3、删除上次搜集后不存在的网页l 比较： 定期批量重采非常简单，但是浪费带宽，周期也长； 增量采集可以节省带宽，网页更新周期相对较短，但是系统的复杂性增大。102022-6-20信息的搜集速度保证 局域网联接多机进行并行采集 广域网分布式采集 多进程并行 多线程并行112022-6-20信息的搜集质量保证 URL重复的检测和排除 内容重复的检测和排除 入度高的网页相对重要 URL浅的网页相对重要 含有被别人广泛链接的内容的

4、网页重要122022-6-20信息的搜集“礼貌” 遵守网站上发布的Robots.txt 采集限制协议 搜集时尽量不要太过密集地采集某个网站 这种密集访问类似于黑客攻击，导致正常浏览网站产生困难。 有些网站会严密控制这种密集访问行为。132022-6-20信息的搜集开源采集工具142022-6-20信息的搜集WeblechMIT Licence http:/ 使用方法： 1）按需求修改配置文件Sperties 2）运行run.bat开始爬行 3）如果程序中断，运行resume.bat继续爬行162022-6-20信息的搜集Weblech配置说明lsaveRootDirector

5、y = c:/weblech/sistes 设置文件的存放路径，默认为当前文件夹lmailtoLogFile = mailto.txt 设置邮件链接(mailto links)的存放文件lrefreshHTMLs = true lrefreshImages = false lrefreshOthers = false /设置如果本 地硬盘已经存在待爬取的文件，是否重新载入文件lhtmlExtensions = htm,html,shtm,shtml,asp,jsp,php 设置spider要下载资源的扩展名limageExtensions = 同上lstartLocation = http:/

6、 设置spider爬行的起始页面ldepthFirst = false 设置进行广度优先爬行或深度优先爬行lmaxDepth = 5 爬行的最大深度（第一个页面深度为0，其链接的深度为1）lurlMatch 基本的URL过滤。下载的网页的网址中中必须包括urlMatch串linterestingURLs= 优先级最高的网页lboringURLs= 优先级最低的网页lbasicAuthUser = myUser lbasicAuthPassword = 1234 设置需要验证的网站的用户名和密码lspiderThreads = 15 爬行的线程数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协议，获得url的内容content，url URL完成队列（List 2）； 3、存储content； 4、解析content URLs； 5、判断URLs是否在List 2中，如果否，加入到List 1中； 6、如果List 1非空，执行2； 7、如果List 1为空，完成。l 要求： 利用Spider程序，完成网页爬取工作。 1、开发一个spider程序，多线程，支持断点续爬。 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) 对字典排序 把字典读入内存 如果字典太大，对字典建立二级索引，把

10、字典的索引读入内存262022-6-20建立倒排索引的流程272022-6-20英文词根还原(Stemming)282022-6-20中文分词 例子：李明天天都准时上班 字：李/明/天/天/都/准/时/上/班索引量太大，查全率百分百，但是查准率低；比如，查“明天” 这句话也会出来 词：李明/天天/都/准时/上班索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响；比如，上面可能会切分成：李 明天 天都 准时 上班 二字串：李明/明天/天天/天都/都准/准时/时上/上班292022-6-20去除停用词302022-6-20检索模型l 什么叫检索？ 用户提交一个查询（Query）

11、，搜索引擎查找与该查询相关结果的过程。l 检索模型： 布尔模型 向量空间模型 概率模型 统计语言模型 312022-6-20布尔模型l 简单的检索模型，建立在集合论和布尔代数的基础上。l 遵循两条基本规则: 每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为 0或1。 查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式。l 优点： 简单，易于实现，能够保证较高的查全率。l 缺点： 只能精确判断文档是否出现某一查询词，但并没有给出每个词的重要程度，不能给出相关性排序322022-6-20布尔模型AND OR 332022-6-20向量空间模型l 查询和文档

12、都转化成标引项(Term)及其权重组成的向量表示 康奈尔大学 Salton 1970年代提出并倡导，原型系统SMART 例如： 文档1：(,)， 文档2：(,) 查询：(,) 查询和文档进行向量的相似度计算：夹角余弦或者内积 文档1：1*1+3*2=7 文档2：2*2=4 优点：简洁直观，效果好，可以应用到很多其他领域。 缺点：理论上不够完善，标引项之间的独立性假设与实际不符342022-6-20向量空间模型 TF（Term Frequency）：Term的频度，TF越高权重越高 DF（Document Frequency）：Term的文档频度，DF越高区分度越低，因此权重也越低 IDF（In

13、verse DF）：逆文档频率 文档的长度：长度归一化(Length Normalization)352022-6-20查询扩展362022-6-20Lucene介绍372022-6-20Lucene的其他语言版本382022-6-20Lucene功能392022-6-20Lucene系统的组织结构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: 创建与更新索引数据l Directory: 获取Lucene索引的位置l Analyzer: 从文本中提取要建索引的项(Term)l Document: 字段(

17、Field)的集合，可视为虚拟的文档（网页、Email或文本）l Field: 每个Document由一个或多个Field组成，每个Field对应于可进行索引和检索的一部分数据，即每个数据单元可以用（FieldName, Value）表示。442022-6-20Lucene的核心接口-检索l IndexSearcher：打开并在索引数据中查找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输入的查询语句封装发送给检索服务器 （2）显示结果：从检索服务器获取结果，缓存并分页呈现给用户 Tomcat 5 JDK 1.5 + JSP482022-6-20用户查询界面492022-6-20结果显示界面502022-6-20参考资料l Lucene in action（中文版）l 开发自己的搜索引擎:Lucene + Heritrixl Search Engines Information Retrieval in Practice512022-6-20作业要求l 动手搭建一个完整、可运行的小型全文检