搜索引擎与文本挖掘课程设计说明搭建小型搜索引擎分析课件

1、利用开源工具搭建小型Web搜索引擎联系人：刘文飞Email：wenfeiliuURL：地址：创新园大厦A0923室联系方式 理解搜索引擎的工作原理 搭建一个可运行的实验系统在理解搜索引擎原理及整体流程的基础上，通过亲自动手搭建一个完整、可运行的小型全文检索实验系统训练目标搜索引擎基本框架www索引库索 引 检 索 用 户 接 口spiderspider文档库信息采集索引与检索Web接口 Web信息的搜集 基于Lucene的索引与检索 基于Tomcat的Web服务提纲信息的搜集概念原理：把整个互联网看成一个大的图，则信息搜集可以看成是图的遍历。信息采集系统也常常称为Robot, Spider,

2、Crawler等等目标：快速获得高质量的网页实际上是图的遍历过程通过种子页面或站点(Seed)，获取更多的链接，将它们作为下一步种子，不断循环。这个过程一般永远不会结束！信息的搜集策略广度优先 vs. 深度优先广度优先：先采集完同一层的网页，再采集下一层网页深度优先：先沿一条路径采到叶节点，再从同层其他路径进行采集有研究表明：广度优先的方法得到的网页集合的重要性更好网站采集 vs. 全局URL采集网站采集：一个网站一个网站采集全局URL采集：将所有URL放入一个URL池，从中使用某种方法进行选择网站采集在采集效率上可能不如全局URL采集，通常的搜索引擎采用全局URL采集的方法。孤立站点用户提交

3、信息的搜集信息指纹的应用概念任何一段文字信息，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint）。如：MD5算法，可以把任意长信息变换成定长（128b）的整数信息指纹在爬虫中的应用 去重、压缩信息的搜集网页的维护与更新批量搜集每次搜集替换上一次的内容 增量搜集 开始时搜集一批往后：1、搜集新出现的网页；2、搜集在上次搜集后有改变的网页； 3、删除上次搜集后不存在的网页比较：定期批量重采非常简单，但是浪费带宽，周期也长；增量采集可以节省带宽，网页更新周期相对较短，但是系统的复杂性增大。信息的搜集速度保证多机分布式并行局域网联接多机进行并行采集广域网分布式采集单机多

4、程序并行多进程并行多线程并行信息的搜集质量保证减少重复页面的采集URL重复的检测和排除内容重复的检测和排除保证重要页面的高优先级入度高的网页相对重要URL浅的网页相对重要含有被别人广泛链接的内容的网页重要信息的搜集“礼貌”范围：遵守网站上发布的Robots.txt 采集限制协议频率：搜集时尽量不要太过密集地采集某个网站这种密集访问类似于黑客攻击，导致正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。信息的搜集开源采集工具Nutch CrawlerLabinWgetWeblech信息的搜集Weblech全功能的网页爬虫性质：MIT Licence 网址：/版本：V0.0.3(2002-0

5、6-14)平台：Java特点：代码是用纯Java写的，可以在任何支持Java的平台上均可运行支持多线程下载网页可维持网页间的链接信息可配置性强信息的搜集Weblech使用方法：1）按需求修改配置文件Sperties2）运行run.bat开始爬行3）如果程序中断，运行resume.bat继续爬行信息的搜集Weblech配置说明saveRootDirectory = c:/weblech/sistes 设置文件的存放路径，默认为当前文件夹mailtoLogFile = mailto.txt 设置邮件链接(mailto links)的存放文件refreshHTMLs = true refreshIm

6、ages = false refreshOthers = false /设置如果本 地硬盘已经存在待爬取的文件，是否重新载入文件htmlExtensions = htm,html,shtm,shtml,asp,jsp,php 设置spider要下载资源的扩展名imageExtensions = 同上startLocation = / 设置spider爬行的起始页面depthFirst = false 设置进行广度优先爬行或深度优先爬行maxDepth = 5 爬行的最大深度（第一个页面深度为0，其链接的深度为1）urlMatch 基本的URL过滤。下载的网页的网址中中必须包括urlMatch串

7、interestingURLs= 优先级最高的网页boringURLs= 优先级最低的网页basicAuthUser = myUser basicAuthPassword = 1234 设置需要验证的网站的用户名和密码spiderThreads = 15 爬行的线程数checkpointInterval = 30000 设置写断点的时间间隔（ms）信息的搜集Weblech类说明主要类SpiderConfig.javaHTMLParser.javaDownloadQueue.javaURLGetter.javaURLObject.javaSpider.javaWeblech流程图Download

8、Queue.javaSpiderConfig.javaHTMLParser.javaURLGetter.javaSpider.javaURLObject.javaWeb信息采集小结如何写一个简单的Spider程序？1、种子URL队列（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为空，完成。要求：利用Spider程序，完成网页爬取工作。1、开发一个spide

9、r程序，多线程，支持断点续爬。2、利用开源工具。 Web信息的搜集 基于Lucene的索引与检索 基于Tomcat的Web服务提纲基于Lucene的索引与搜索 索引基本原理搜索基本原理Lucene使用介绍索引基本原理为加快搜索速度，建立特定的数据结构不可能是逐个文档扫描(太慢)反向索引、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文档2a38b14c610d29a15b

10、28c36d475710119反向索引(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号偏移位置dictionary文档 list反向索引(Inverted index)实际应用中：对字典排序把字典读入内存如果字典太大，对字典建立二级索引，把字典的索引读入内存建立倒排索引的流程索引源预处理分词建立倒排索引写临时索引文件合并临时索引文件索引压缩写索引文件英文词根还原(Stemming)进行词根还原：stop/stops/stopping/stopped stop好处：减少词典量，提高查全率；坏处：按词形查不到

11、，词根还原还可能出现错误不进行词根还原：好处：支持词形查询；坏处：增加词典量开源工具包：Snowball中文分词对于中文，分词的作用实际上是要找出一个个的索引单位例子：李明天天都准时上班索引单位字：李/明/天/天/都/准/时/上/班索引量太大，查全率百分百，但是查准率低；比如，查“明天” 这句话也会出来词：李明/天天/都/准时/上班索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响；比如，上面可能会切分成：李 明天 天都 准时 上班二字串：李明/明天/天天/天都/都准/准时/时上/上班去除停用词停用词(Stop words)：指那些出现频率高但是无重要意义；通常不会作为查询

12、词出现的词，如“的”、“地”、“得”、“都”、“the”等等消除：通常是通过查表的方式去除，好处-大大减少索引量，坏处-有些平时的停用词在某些上下文可能有意义保留：索引空间很大检索模型什么叫检索？用户提交一个查询（Query），搜索引擎查找与该查询相关结果的过程。检索模型：布尔模型向量空间模型概率模型统计语言模型布尔模型简单的检索模型，建立在集合论和布尔代数的基础上。遵循两条基本规则: 每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为 0或1。查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式。优点：简单，易于实现，能够保证较高的查全率。缺点：只能精确

13、判断文档是否出现某一查询词，但并没有给出每个词的重要程度，不能给出相关性排序布尔模型enginesearch357Search AND engine Search OR engine3713457913479向量空间模型查询和文档都转化成标引项(Term)及其权重组成的向量表示康奈尔大学 Salton 1970年代提出并倡导，原型系统SMART例如：文档1：(,)，文档2：(,)查询：(,)查询和文档进行向量的相似度计算：夹角余弦或者内积文档1：1*1+3*2=7文档2：2*2=4优点：简洁直观，效果好，可以应用到很多其他领域。缺点：理论上不够完善，标引项之间的独立性假设与实际不符向量空间模型

14、权重影响因子：TF（Term Frequency）：Term的频度，TF越高权重越高DF（Document Frequency）：Term的文档频度，DF越高区分度越低，因此权重也越低IDF（Inverse DF）：逆文档频率文档的长度：长度归一化(Length Normalization)查询扩展对用户的查询进行扩充：比如用户输入“计算机”，我们扩充一个词“电脑”同义词扩展：同义词词典通过统计构造的同义词词典相关词扩展：相关词：“2006世界杯” 与“德国”基于全局分析的查询扩展：对文档集合进行分析得到某种相关词典基于局部上下文的查询扩展基于概念的查询扩展查询重构：对用户的初始查询进行修改(

15、可以是加词、减词，或者对于向量模型表示的初始查询进行权重的修改等等)，是比查询扩展更泛的一个概念Lucene介绍Lucene简介完整、高效、易用、易扩展的开源全文检索工具包性质：Apache License作者：Doug Cutting网址：/版本：Lucene 4.10平台：跨平台支持：Apache Jakarta项目Lucene的其他语言版本Lucene功能结果排序最好结果优先强大的查询表达式处理功能短语、通配符、模糊查询等分字段检索指定日期范围检索根据字段排序支持多索引检索与结果合并支持更新与检索同时进行Lucene系统的组织结构Lucene的索引文件格式segments：存储索引的各个

16、segment的信息.del：已删除文档信息.fnm：域信息 (域名域标志等).fdt：域数据，存储文档的各种属性数据，例如文档路径，文档长度（按文档标号顺序组织）.fdx：文档域数据指针，每文档一个.tis：索引词（term）信息，即词典.tii：存储.tis中每IndexInternal个Term，这个文件装入内存以加快检索速度(二级索引).frq：存放索引词（term）的词频信息.prx ：索引词（term）的位置信息其它文件简单示例索引void IndexFiles(String INDEX_DIR, String docDir) StandardAnalyzer myAnalyzer

17、 = newStandardAnalyzer();/分词器 IndexWriter writer = newIndexWriter(INDEX_DIR,myAnalyzer, true); writer.setUseCompoundFile(false); /索引文件格式 writer.setMergeFactor(1000);/合并因子 indexDocs(writer, docDir); writer.optimize();/合并子索引，从物理上删除做过删除标记的文档 writer.close();/ IndexFiles简单示例索引static void indexDocs(IndexW

18、riter writer, File file) 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(n

19、ew Field(“title”, parser.getTitle(), Field.Store.YES, Field.Index.TOKENIZED); doc.add(new Field(“content”, parser.getContent(), Field.Store.YES,Field.Index.TOKENIZED); writer.addDocument(doc);/ 添加片段到Lucene索引理解索引中的核心类IndexWriter: 创建与更新索引数据Directory: 获取Lucene索引的位置Analyzer: 从文本中提取要建索引的项(Term)Document:

20、字段(Field)的集合，可视为虚拟的文档（网页、Email或文本）Field: 每个Document由一个或多个Field组成，每个Field对应于可进行索引和检索的一部分数据，即每个数据单元可以用（FieldName, Value）表示。Lucene的核心接口-检索IndexSearcher：打开并在索引数据中查找Term：用于检索的基本单位，形式为(Field，Value)Query：检索表达式类型TermQuery：最基本的Query类型，返回在指定字段包含指定关键词的文档QueryParser：解析用户输入的查询q，生成Query对象Hits：检索结果集简单示例检索void Sear

21、chFiles(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 = searcher.search(q); /查询结果放在Hits类中（只

22、存部分结果） for (int i=0; ih.length(); i+) Document doc = h.doc(i); System.out.println(“Result “ + i + doc.get(path); /for reader.close();/ SearchFiles Web信息的搜集 基于Lucene的索引与检索 基于Tomcat的Web服务提纲基于Tomcat的Web服务用户查询请求处理程序CGI或脚本语言（ASP,PHP,JSP,etc）功能（1）获取用户查询式：把用户通过Form输入的查询语句封装发送给检索服务器（2）显示结果：从检索服务器获取结果，缓存并分页呈现给用户例：Tomcat 5 JDK 1.5 + JSP用户