《大连理工大学搜索引擎及文本挖掘课程设计说明搭建小》由会员分享,可在线阅读,更多相关《大连理工大学搜索引擎及文本挖掘课程设计说明搭建小(57页珍藏版)》请在金锄头文库上搜索。
1、利用开源工具 搭建小型Web搜索引擎,联系人:刘文飞 Email: URL:http:/ 地址:创新园大厦A0923室,联系方式,理解搜索引擎的工作原理 搭建一个可运行的实验系统 在理解搜索引擎原理及整体流程的基础上,通过亲自动手搭建一个完整、可运行的小型全文检索实验系统,训练目标,搜索引擎基本框架,www,索引库,索 引,检 索,用 户 接 口,spider,spider,文档库,信息采集,索引与检索,Web接口,Web信息的搜集 基于Lucene的索引与检索 基于Tomcat的Web服务,提纲,信息的搜集概念,原理: 把整个互联网看成一个大的图,则信息搜集可以看成是图的遍历。 信息采集系统
2、也常常称为Robot, Spider, Crawler等等 目标: 快速获得高质量的网页 实际上是图的遍历过程 通过种子页面或站点(Seed),获取更多的链接,将它们作为下一步种子,不断循环。 这个过程一般永远不会结束!,信息的搜集策略,广度优先 vs. 深度优先 广度优先:先采集完同一层的网页,再采集下一层网页 深度优先:先沿一条路径采到叶节点,再从同层其他路径进行采集 有研究表明:广度优先的方法得到的网页集合的重要性更好 网站采集 vs. 全局URL采集 网站采集:一个网站一个网站采集 全局URL采集:将所有URL放入一个URL池,从中使用某种方法进行选择 网站采集在采集效率上可能不如全局
3、URL采集,通常的搜索引擎采用全局URL采集的方法。 孤立站点 用户提交,信息的搜集信息指纹的应用,概念 任何一段文字信息,都可以对应一个不太长的随机数,作为区别它和其它信息的指纹(Fingerprint)。 如:MD5算法,可以把任意长信息变换成定长(128b)的整数 信息指纹在爬虫中的应用 去重、压缩,信息的搜集网页的维护与更新,批量搜集 每次搜集替换上一次的内容 增量搜集 开始时搜集一批 往后:1、搜集新出现的网页;2、搜集在上次搜集后有改变的网页; 3、删除上次搜集后不存在的网页 比较: 定期批量重采非常简单,但是浪费带宽,周期也长; 增量采集可以节省带宽,网页更新周期相对较短,但是系
4、统的复杂性增大。,信息的搜集速度保证,多机分布式并行 局域网联接多机进行并行采集 广域网分布式采集 单机多程序并行 多进程并行 多线程并行,信息的搜集质量保证,减少重复页面的采集 URL重复的检测和排除 内容重复的检测和排除 保证重要页面的高优先级 入度高的网页相对重要 URL浅的网页相对重要 含有被别人广泛链接的内容的网页重要,信息的搜集“礼貌”,范围: 遵守网站上发布的Robots.txt 采集限制协议 频率: 搜集时尽量不要太过密集地采集某个网站 这种密集访问类似于黑客攻击,导致正常浏览网站产生困难。 有些网站会严密控制这种密集访问行为。,信息的搜集开源采集工具,Nutch Crawle
5、r Labin Wget Weblech,信息的搜集Weblech,全功能的网页爬虫 性质:MIT Licence 网址:http:/ 版本:V0.0.3(2002-06-14) 平台:Java 特点: 代码是用纯Java写的,可以在任何支持Java的平台上均可运行 支持多线程下载网页 可维持网页间的链接信息 可配置性强,信息的搜集Weblech,使用方法: 1)按需求修改配置文件Spider.properties 2)运行run.bat开始爬行 3)如果程序中断,运行resume.bat继续爬行,信息的搜集Weblech配置说明,saveRootDirectory = c:/weblech/
6、sistes 设置文件的存放路径,默认为当前文件夹 mailtoLogFile = mailto.txt 设置邮件链接(mailto links)的存放文件 refreshHTMLs = true refreshImages = false refreshOthers = false /设置如果本 地硬盘已经存在待爬取的文件,是否重新载入文件 htmlExtensions = htm,html,shtm,shtml,asp,jsp,php 设置spider要下载资源的扩展名 imageExtensions = 同上 startLocation = http:/ 设置spider爬行的起始页面
7、depthFirst = false 设置进行广度优先爬行或深度优先爬行 maxDepth = 5 爬行的最大深度(第一个页面深度为0,其链接的深度为1) urlMatch 基本的URL过滤。下载的网页的网址中中必须包括urlMatch串 interestingURLs= 优先级最高的网页 boringURLs= 优先级最低的网页 basicAuthUser = myUser basicAuthPassword = 1234 设置需要验证的网站的用户名和密码 spiderThreads = 15 爬行的线程数 checkpointInterval = 30000 设置写断点的时间间隔(ms)
8、,信息的搜集Weblech类说明,主要类 SpiderConfig.java HTMLParser.java DownloadQueue.java URLGetter.java URLObject.java Spider.java,Weblech流程图,DownloadQueue.java,SpiderConfig.java,HTMLParser.java,URLGetter.java,Spider.java,URLObject.java,Web信息采集小结,如何写一个简单的Spider程序? 1、种子URL队列(List 1); 2、Http协议,获得url的内容content,url UR
9、L完成队列(List 2); 3、存储content; 4、解析content URLs; 5、判断URLs是否在List 2中,如果否,加入到List 1中; 6、如果List 1非空,执行2; 7、如果List 1为空,完成。 要求: 利用Spider程序,完成网页爬取工作。 1、开发一个spider程序,多线程,支持断点续爬。 2、利用开源工具。,Web信息的搜集 基于Lucene的索引与检索 基于Tomcat的Web服务,提纲,基于Lucene的索引与搜索,索引基本原理 搜索基本原理 Lucene使用介绍,索引基本原理,为加快搜索速度,建立特定的数据结构 不可能是逐个文档扫描(太慢)
10、反向索引、B+树、签名表等 大规模数据的索引常常用反向索引(倒排) Inverted file 所有的搜索引擎都用倒排索引 速度快,前向索引(Forward index),概念:由文档到关键词 文档1:b d a b b c b a d c 文档2:a b c d a c d b d a b,文档1,文档2,a,3,8,b,1,4,c,6,10,d,2,9,a,1,5,b,2,8,c,3,6,d,4,7,5,7,10,11,9,反向索引(Inverted index),文档1:b d a b b c b a d c 文档2:a b c d a c d b d a b,文档ID号,偏移位置,di
11、ctionary,文档 list,反向索引(Inverted index),实际应用中: 对字典排序 把字典读入内存 如果字典太大,对字典建立二级索引,把字典的索引读入内存,建立倒排索引的流程,索引源,预处理,分词,建立倒排索引,写临时索引文件,合并临时索引文件,索引压缩,写索引文件,英文词根还原(Stemming),进行词根还原:stop/stops/stopping/stopped stop 好处:减少词典量,提高查全率; 坏处:按词形查不到,词根还原还可能出现错误 不进行词根还原: 好处:支持词形查询; 坏处:增加词典量 开源工具包: Snowball,中文分词,对于中文,分词的作用实际
12、上是要找出一个个的索引单位 例子:李明天天都准时上班 索引单位 字:李/明/天/天/都/准/时/上/班 索引量太大,查全率百分百,但是查准率低; 比如,查“明天” 这句话也会出来 词:李明/天天/都/准时/上班 索引量大大降低,查准率较高,查全率不是百分百,而且还会受分词错误的影响; 比如,上面可能会切分成:李 明天 天都 准时 上班 二字串:李明/明天/天天/天都/都准/准时/时上/上班,去除停用词,停用词(Stop words): 指那些出现频率高但是无重要意义;通常不会作为查询词出现的词,如“的”、“地”、“得”、“都”、“the”等等 消除:通常是通过查表的方式去除, 好处-大大减少索
13、引量, 坏处-有些平时的停用词在某些上下文可能有意义 保留:索引空间很大,检索模型,什么叫检索? 用户提交一个查询(Query),搜索引擎查找与该查询相关结果的过程。 检索模型: 布尔模型 向量空间模型 概率模型 统计语言模型 ,布尔模型,简单的检索模型,建立在集合论和布尔代数的基础上。 遵循两条基本规则: 每个索引词在一篇文档中只有两种状态:出现或不出现,对应权值为 0或1。 查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式。 优点: 简单,易于实现,能够保证较高的查全率。 缺点: 只能精确判断文档是否出现某一查询词,但并没有给出每个词的重要程度,不能给出相关
14、性排序,布尔模型,engine,search,Search AND engine,Search OR engine,向量空间模型,查询和文档都转化成标引项(Term)及其权重组成的向量表示 康奈尔大学 Salton 1970年代提出并倡导,原型系统SMART 例如: 文档1:(,), 文档2:(,) 查询:(,) 查询和文档进行向量的相似度计算:夹角余弦或者内积 文档1:1*1+3*2=7 文档2:2*2=4 优点:简洁直观,效果好,可以应用到很多其他领域。 缺点:理论上不够完善,标引项之间的独立性假设与实际不符,向量空间模型,权重影响因子: TF(Term Frequency):Term的频
15、度,TF越高权重越高 DF(Document Frequency):Term的文档频度,DF越高区分度越低,因此权重也越低 IDF(Inverse DF):逆文档频率 文档的长度:长度归一化(Length Normalization),查询扩展,对用户的查询进行扩充:比如用户输入“计算机”,我们扩充一个词“电脑” 同义词扩展: 同义词词典 通过统计构造的同义词词典 相关词扩展: 相关词:“2006世界杯” 与“德国” 基于全局分析的查询扩展:对文档集合进行分析得到某种相关词典 基于局部上下文的查询扩展 基于概念的查询扩展 查询重构:对用户的初始查询进行修改(可以是加词、减词,或者对于向量模型表示的初始查询进行权重的修改等等),是比查询扩展更泛的一个概念,Lucene介绍,Lucene简介 完整、高效、易用、易扩展的开源全文检索工具包 性质:Apache License 作者:Doug Cutting 网址:http:/lucene.apache.org/ 版本:Lucene 4.10 平台:跨平台 支持:Apache Jakarta项目,Lucene的其他语言版本,Lucene功能,结果排序最好结果优先 强大的查询表达式处理功能短语、通配符、模糊查询等 分字段检索 指定日期范围检索 根据字段排序 支持多索引检索与结果合并 支持更新与检索同时进行,