计算机毕业论文范文.doc

《计算机毕业论文范文.doc》由会员分享，可在线阅读，更多相关《计算机毕业论文范文.doc（12页珍藏版）》请在三一办公上搜索。

1、成人教育学院 毕业论文（设计） 论文题目：基于Internet的全文搜索引擎的模型设计 专 业：_计算机 _ 年 级：_10级_ 学生姓名：_钱梦阳_ 学 号：_z201001023_ 指导教师：_商迎美_ 2012 年 04 月 22 日基于Internet的全文搜索引擎的模型设计钱梦阳摘 要根据搜索引擎与信息获取的原理,设计了一个基于Internet的全文搜索引擎,该模型从技术上可以适用于任何有全文搜索需求的应用,并且由于基于Java语言设计,从而特别适于跨平台应用。该模型还采用了数据库管理作业和多线程技术,从而使全文搜索的性能和效率得到了进一步的提高。 关键词 : 搜索引擎;网络蜘蛛;分

2、析器;索引中图分类号：文献标识码：A目录摘要2目录3一、引言4二、搜索引擎系统分析4三、搜索引擎系统模型4 3.1从互联网上抓取图片5 3.2建立索引数据库 5 3.3在索引数据库中搜索6 3.4对搜索结果进行处理排序6四、模型的组成结构7五、搜索引擎实现机制9 5.1网络蜘蛛的实现机制9 5.2全文检索的实现机制10 5.2.1索引过程10 5.2.2检索过程中的结果显示10六、结论11参考文献12指导老师点评13一、 引言随着计算机技术和互联网技术的飞速发展，信息获取已经从手工获取，到计算机信息获取，以及到现在的通过网络进行信息获取。利用互联网，用户一方面可以快速、方便地接触到各种信息，但

3、是另一方面通过普通浏览的方式很难在信息的海洋中找到真正需要的信息。要在浩如烟海的网络世界寻找需要的信息，作为现代信息获取技术的主要应用搜索引擎(Search Engine)是必不可少的。中国互联网络信息中心（CNNIC）在京发布的“第十四次中国互联网络发展状况统计报告”显示， 搜索引擎是用户在互联网上获取信息最主要的方式。又由于搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、开发十分活跃，出现了很多值得注意的动向。二、 搜索引擎系统分析搜索引擎通常指的是基于Internet的搜索引擎，其作用是检索Web的内容。它们收集因特网上上亿个网页

4、，并且每一个网页上的每一个词都被搜索引擎所收录，也就是我们所说的全文检索。在构造搜索引擎时，布尔模型是用得最普遍的模型。在布尔模型中，一个文档通过一个关键词条的集会来表示，这些词条都来自一个词典。一个查询是由一些通过逻辑操作符号（如AND、OR和NOT）连接起来的关键词所组成。在查询与文档匹配的过程中，主要看该文档中的词条是否满足查询的条件。搜索引擎主要由网络蜘蛛（WebSpider）、索引(Index)与搜索(Search)引擎软件等部分组成。其实现原理，可以看作四步：从互联网上抓取网页（Data Gathering）建立Web内容索引数据库(Index creation)在索引数据库中搜索

5、(Search interface)对搜索结果进行处理和排序(Data display)。三、 搜索引擎系统模型 下面给出基于Internet的全文搜索引擎系统架构图，搜索引擎的各部分都会相互交错相互依赖。其处理流程按照如下描述：图 1基于Internet的全文搜索引擎系统架构3.1 从互联网上抓取网页 “网络蜘蛛”依据一定的网络协议在互联网中抓取、加工、整理网页，把网页送入“网页数据库”，从网页中“提取URL”，把URL送入“URL数据库”，“蜘蛛控制”得到网页的URL，控制“网络蜘蛛”抓取其它网页，反复循环直到把所有的网页抓取完成。在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优

6、先（本文模型采用的是广度优先）。广度优先是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。两种策略的区别，下图的说明会更加明确。图 2 网络蜘蛛抓取网页的两种策略的区别3.2 建立索引数据库 系统从“网页数据库”提取相关网页信息（包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网页的链接关系等），根据一定的词条算法进行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的权重（或重要性），然后用这些相关信息建立“索引数据库”。关键词在文档中的权重定义如下：其中，为关键词在文档中出现的频率，即词频；为信息库中文档的数目；为信息库中

7、包含词条的文档的个数；为文档中所有关键词的个数。有三种索引的基本技术：倒排文件、后缀数组和签名文件。倒排文件在当前大多数信息获取系统中得到应用，它对于关键词的搜索非常有效。本文模型采用倒排文件技术作为索引方法建立数据库。倒排文件结构由词汇和出现情况两部分组成。对于每个单词，都有一个列表（称为词汇列表）来记录单词在所有文本中出现的位置，这些位置可以是单词的位置（是文本中的第几个单词），也可以是字符的位置（是文本中的第几个字符）。一个在大小为个字符的文件上进行的倒排索引可以在时间内构造成功。所以已知的单词都放在一棵树结构中，在构造倒排索引的时候，对于每个读入的单词，首先在该树中查找，如果没有找到，

8、就在该树中加入一个空的词汇出现情况列表；否则将该词汇的新位置加入到树中对应词汇出现情况列表的末尾。索引被分成两个文件存放。第一个文件顺序存放词汇出现情况列表，第二个文件以字典序存放树中的词汇，还为每个词汇存放一个指向第一个文件中该单词对应的词汇出现情况列表的指针。这样第二个文件由于比较小而可以在搜索的时候放在内存中。在建“索引数据库”同时系统进行“链接信息提取”，把链接信息（包括锚文本、链接本身等信息）送入“链接数据库”，为“网页评级”提供依据。3.3 在索引数据库中搜索“用户”通过提交查询请求给“查询服务器”， “查询服务器”分解搜索请求，在“索引数据库”中进行相关网页的查找，对于单个词汇的

9、查询来说，只要从词汇表中找到对应的单词就可以找到指向该单词的出现情况列表；对于查询串由多个单词组成（这种情况在查询过程中比较常见）相对于单词汇查询要复杂得多，首先获取查询串中每个词汇的出现情况列表，然后遍历所有这些获取的列表，看看查询串中的词汇是否在文本中顺序出现（对于短语）或者比较靠近（近似查询）。这些列表的合并和交叉运算需要花费的时间比单词查询的长得多。3.4 对搜索结果进行处理排序所有相关网页针对该关键词的相关信息在索引库中都有记录，“网页评级”把查询请求和链接信息结合起来对搜索结果进行相关度的评价，通过“查询服务器”按照相关度进行排序(相关度越高，排名越靠前),并提取关键词的内容摘要，

10、组织最后的页面返回给“用户”。 对于包含 个词条的查询向量 和一个文档向量 来说，它们之间的相关度可以通过下面的公式 来计算：四、模型的组成结构基于Internet的全文搜索引擎的组成结构如下表：对于外部应用来说网页获取模块（spider）、索引模块(index)和检索模块(search)是主要的外部应用入口。 表1基于Internet的全文搜索引擎的组成结构命名空间包名主要实现的类mtn.dzjs.shine.threads/mtn.dzjs.shine.spider/mtn.dzjs.shine.search/mtn.dzjs.shine.index/mtn.dzjs.shine.anal

11、ysis/mtn.dzjs.shine.queryParser/mtn.dzjs.shine.document/mtn,dzjs.shine.xml/mtn.dzjs.shine.store/mtn.dzjs.shine.util/多线程网页获取入口搜索入口 索引入口 语言分析器查询分析器 存储结构XML解析器 底层IO/存储结构一些公用的数据结构ThreadFactory、TaskQueue、 ThreadPoolMessageHandler、Filter、ThreadMonitor、Fetcher Searcher、Query、 Hits IndexSearcher、 IndexWrite

12、rAnalyzer、TokenQueryParserDocument、FieldXMLDocumentHandlerDOM、 XMLDocumentHandlerSAXFSDirectory、AMDirectory、StoragePipelineBitVector、PriorityQueue 全文检索的API接口设计的比较通用，输入输出结构都很像数据库的表=记录=字段，所以我们可以用一个标准的中间格式XML作为数据导入接口，然后其他数据源，只要是能够映射成表=记录=字段这样层次结构的(比如PDF)，只需要通过解析器转换成标准的中间格式就可以进行数据索引了。我们也可以设计基于XML的搜索结果输出

13、，这样方便了通过XSLT进行前台的结果显示。 对于网页内容用数据库储存的网站，只要将数据库数据用脚本导出成XML格式，再将XML数据导入索引，就可以很方便的实现站内全文搜索。 图3 全文检索的输入输出结构此外在应用的国际化支持方面,XML数据源用JAVA解析后是UNICODE，这样无论是日文，繁体中文还是德文的内容我们都可以在一个索引库中同时进行搜索。这样针对其他语言的支持只是设计各种语言界面的问题了。图 4全文检索对国际化的支持表2全文检索和数据库的比较全文检索数据库索引数据源doc(field1,field2.) indexer / _ | Shine Index| - / searche

14、r 结果输出：Hits(doc(field1,field2)Document：一个需要进行索引的“单元”一个Document由多个字段组成Field：字段Hits：查询结果集，由匹配的Document组成索引数据record(field1,field2.) SQL: insert/ _ | DB Index | - / SQL: select 结果输出：results(record(field1,field2.)Record：记录，包含多个字段Field: 字段RecordSet：查询结果集，由多个Record组成全文检索 like %keyword%五、 搜索引擎实现机制5.1 网络蜘蛛的实

15、现机制网络蜘蛛专门设计用来做基于内容的站点查找。它从URL服务器取得URL列表，同一时刻可保持多个网络连接。影响爬行速度的一个重要因素是DNS查询，为此每个爬行器都要维护一个自己的DNS缓冲。这样每个连接都处于不同的状态，包括：DNS查询、连到主机、发送请求、得到响应。这些因素综合起来使得爬行器变成一个非常复杂的系统。下面给出一个网络蜘蛛的详细工作模型。图 5网络蜘蛛工作模型信息处理程式（Message Handler）依次将队列(URLMessage Queue)中的URL信息送入过滤器链(Filters), 每一个过滤器都能决定是否向前传递URL信息, 改变URL信息, 或甚至删除URL信

16、息。如URLVisitedFilter确保URL只被放入流水线中一次，RobotExclusionFilter检查一个网页是否拒绝网络蜘蛛访问。信息处理程式运行在自己的线程中。过滤器也运行在信息处理程式线程里面,显然URL信息传递是一个生产者- 消费者一样的问题. 经过滤器链过滤的信息接着被分配给Fecther的线程池（Fetcher pool）处理,多个FetcherThreads并行处理任务。如果线程池中要处理的任务数多于现有的线程数,则暂时不能被处理的任务被保持在一个队列中,等待线程完成处理中的任务后接着去读取他们。每一个FetcherThread都是独立运行的，它得到网页，分析它，提取

17、其中的文本信息并把它们存储到Storage中。网页获取过程可以看到 爬行器通过异步输入/输出来管理事件，通过一定数量的队列来管理获取网页过程中的状态迁移。 对于许多数据是放在数据库的网站，需要通过本网站的数据库搜索才能获得信息，这些给网络蜘蛛的抓取带来很大的困难。5.2 全文检索的实现机制建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制，将数据源（比如多篇文章）排序顺序存储的同时，有另外一个排好序的关键词列表，用于存储关键词=文章映射关系，利用这样的映射关系索引：关键词=出现关键词的文章编号，出现次数（甚至包括位置：起始偏移量，结束偏移量），出现频率，检索过程就是把模糊查询

18、变成多个可以利用索引的精确查询的逻辑组合的过程。5.2.1索引过程从数据源读取文件名（多个），将文件分路径(path字段)和内容(body字段)2个字段进行存储，并对内容进行全文索引：索引的单位是Document对象，每个Document对象包含多个字段Field对象，针对不同的字段属性和数据输出的需求，对字段还可以选择不同的索引/存储字段规则，如对日期字段只索引存储不切分；对文件路径不索引；而对标题，内容字段则切分词、索引并存储。该过程主体程序如下：/用指定的语言分析器构造一个新的写索引器（第3个参数表示是否为追加索引） IndexWriter writer = new IndexWrite

19、r(indexPath, new Analyser(), false);/依次索引filesPath中的文件列表 for (int i=1; iField中的内容。假设根据body字段进行全文检索，可以将查询结果的path字段和相应查询的匹配度(score)显示出来。该过程主体程序如下：/指向索引目录的搜索器 Searcher searcher = new IndexSearcher(indexPath);/查询解析器：使用和索引同样的语言分析器 Query query = QueryParser.parse(queryString, body, new Analyser();/搜索结果使用H

20、its存储 Hits hits = searcher.search(query);/通过hits可以访问到相应字段的数据和查询的匹配度 for (int i=0; ihits.length(); i+) System.out.println(hits.doc(i).get(path) + ; Score: + hits.score(i); 可以看到在整个检索过程中，语言分析器，查询分析器，甚至搜索器（Searcher）都是提供了抽象的接口，可以根据需要进行定制。 检索过程中所用的语言分析器“Analyser”与索引过程用的是同一个分析器，否则，不能得出正确检索结果。六、结论 本文所提出的模型从

21、技术上可以适用于任何有全文搜索需求的应用，并且可以索引和搜索多种传统的应用文件（如Word, Excel, PDF, Text and HTML）。但搜索引擎是一个新的研究、开发领域。它要用到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，具有综合性和挑战性。因此本文只能是一定程度上的理论研究，还有许多实现上的细节需要作深入的研究、试验和测试。在今后的研究中我们将努力提高信息查询结果的精度，提高检索的有效性；加强基于智能代理的信息过滤和个性化服务；采用分布式体系结构提高系统规模和性能。参考文献：1Jeff Heaton. Progra

22、mming Spiders, Bots, and Aggregators in Java【M】.北京：电子工业出版社，2002.2Winter.中文搜索引擎技术揭密：网络蜘蛛 【EB】. 2004-05-263徐宝文,张卫丰.搜索引擎与信息获取技术【M】.北京：清华大学出版社，2003.4车东.基于Lucene/XML的站内全文检索解决方案【EB】. 2004-05-015Clemens Marschner,Otis Gospodnetic,Peter Carlson ,et al.Lucene Retrieval Machine，Lucene Framework，System Overview Document【Z】. cmarschn, 2002-12-01.