面向主题的搜索引擎的设计与实现.docx
《面向主题的搜索引擎的设计与实现.docx》由会员分享，可在线阅读，更多相关《面向主题的搜索引擎的设计与实现.docx（21页珍藏版）》请在冰点文库上搜索。
面向主题的搜索引擎的设计与实现
面向主题的搜索引擎的设计与实现
由于互联网的飞速发展，普通搜索引擎无法满足人们的需要；早期的搜索引擎把因特网中的资源服务器的地址起来，根据其提供的资源类型的不同而分到不同的目录，再一层层地进行分类。
人们要找自己想要的可按他们的分类一层层进入，就能最后到达目的地，找到自己想要的；但是这只适用于因特网不多的时候，但是如果一旦多起来，查找的时候所花费的时间就会变长；因此，在一个web文档数上亿的互联网中，需要更快速地找到所需要的，就需要建立一个高效的搜索系统。
该课题总结了现有面向主题的搜索引擎的技术特点，实现一个能满足基本需求的主题搜索引擎；在该课题中叙述了面向主题搜索引擎的重要性、实现方法、实现过程；主要是web文档抓取、特征提取、web文档分类技术；特征值应具有明显的特征，以此提高搜索引擎质量；在实现自动web文档分类时采用向量空间模型计算web文档间的相似度。
1绪论
1.1搜索引擎历史背景
任何搜索引擎的祖先，是1990年由Montreal的McGillUniversity学生AlanEmtage、PeterDeutsch、BillWheelan发明的Archie。
虽然当时WorldWideWeb还未出现，但网络中文档传输还是相当频繁的，由于大量的文档散布在各个分散的FTP主机中，查询起来很不便，因此AlanEmtage等想到了研发一个能够用文档名查找文档的系统，于是便有了Archie。
Archie是第一个自动索引互连网上匿名FTP网站文档的程式，但他还不是真正的搜索引擎。
Archie是个可搜索的FTP文档名列表，用户必须输入精确的文档名搜索，然后Archie会告诉用户哪一个FTP地址能够该文档。
由于Archie深受欢迎，受其启发，NevadaSystemComputingServices大学于1993年研发了一个Gopher搜索工具Veronica。
Jughead是后来另一个Gopher搜索工作.
Robot一词对编程者有特别的意义。
ComputerRobot是指某个能以人类无法达到的速度不断重复执行某项任务的自动程式。
由于专门用于检索的Robot程式象蜘蛛相同在网络间爬来爬去，因此，搜索引擎的Robot程式被称为spider程式。
世界上第一个Spider程式，是MITMatthewGray的WorldwideWebWanderer，用于追踪互连网发展规模。
刚开始他只用来统计互连网上的服务器数量，后来则发展为也能够捕获网址。
和Wanderer相对应，1993年10月MartijnKoster创建了ALIWEB，他相当于Archie的HTTP版本。
ALIWEB不使用网络搜寻Robot，假如网站主管们希望自己的web文档被ALIWEB收录，需要自己提交每一个web文档的简介索引，类似于后来大家熟知的Yahoo。
随着互连网的迅速发展，使得检索任何新出现的web文档变得越来越困难，因此，在Wanderer基础上，一些编程者将传统的Spider程式工作原理作了些改进。
其设想是，既然任何web文档都可能有连向其他网站的链接，那么从一个网站开始，跟踪任何web文档上的任何链接，就有可能检索整个互连网。
到1993年底，一些基于此原理的搜索引擎开始纷纷涌现，其中最负盛名的三个是：
Scotland的JumpStation、Colorado大学OliverMcBryan的TheWorldWideWebWorm、NASA的Repository-BasedSoftwareEngineeringspider。
JumpStation和WWWWorm只是以搜索工具在数据库中找到匹配的先后次序排列搜索结果，因此毫无关联度可言。
而RBSE是第一个索引Html文档正文的搜索引擎，也是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。
1995年，一种新的搜索引擎形式出现了——元搜索引擎。
用户只需提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的单独搜索引擎，并将从各单独搜索引擎返回的任何查询结果，集中起来处理后再返回给用户。
第一个元搜索引擎，是Washington大学硕士生EricSelberg和OrenEtzioni的Metacrawler。
元搜索引擎概念上好听，但搜索效果始终不理想，所以没有哪个元搜索引擎有过强势地位。
大约在1996年出现的第二代搜索引擎系统大多采用分布式方案来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50，000，000web文档的索引数据库，每天能够响应10，000，000次用户检索请求。
1997年11月，当时最先进的几个搜索引擎号称能建立从2，000，000到100，000，000的web文档索引。
目前，搜索引擎的研究、开发十分活跃，各大搜索引擎公司都在投巨资研制搜索引擎系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎已经成为领域的产业之一。
它要用到了检索、人工智能、数据库、数据挖掘、自然语言理解等领域的理论和技术，具有综合性和挑战性。
又由于搜索引擎有大量的用户，由此衍射出许多商机，具有很好的经济价值。
根据搜索引擎所用的技术原理，主要可以分为以下三类：
目录式搜索引擎：
以人工方式或半自动方式搜集，由员查看之后，人工形成，并将置于事先确定的分类框架中。
大多面向网站，提供目录浏览服务和直接检索服务。
该类搜索引擎因为加入了人的智能，所以准确、导航质量高，缺点是需要人工介入、维护量大、量少、更新不及时。
典型有：
Yahoo、LookSmart、OpenDirectory等。
基于Robot搜索引擎：
基于Robot的搜索引擎多提供对全文的检索，有时也叫做全文搜索引擎。
通过Robot程序从互联网上搜集而建立索引数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户。
这类搜索引擎的代表是：
Google、Fast/AllTheWeb、AltaVista、Inktomi、Teoma、WiseNut等；国内代表为：
XX，"天网"、OpenFind等。
元搜索引擎：
这类搜索引擎没有自己的数据库，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行去重、排序等处理后，作为自己的结果返回给用户。
服务方式为面向web文档的全文检索。
这类搜索引擎的优点是返回结果的量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。
著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等，中文元搜索引擎中具代表性的有搜星搜索引擎。
但是，即使比较有名的如Google、Baidu等搜索引擎对检索结果采用了基于超链接的相关度排序，但它们主要依据的也是web文档被其它web文档认同的程度，并非web文档与用户真实检索需求之间的关联程度，结果中包含了大量与用户查询请求不相关的文档，其比例高达75%以上。
所以本文提出了一种分类细致精确、数据全面深入、更新及时的搜索引擎——面向主题的搜索引擎，并详细介绍了其中的抽取技术。
1.2主题搜索引擎
随着多元化的增长，千篇一律的给所有用户同一个入口显然已经不能满足特定用户更深入的查询需求。
同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的是不太可能的。
这就需要一个分类细致精确、数据全面深入、更新及时的面向主题的搜索引擎。
由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比以前普通的搜索引擎更具有特性，能被多数人接受。
搜索最专业：
主题搜索引擎排除了其他杂乱的干扰，结果纯正、专业，是各行业推广的最佳选择，也是消费者品牌消费的最佳参谋和顾问。
结果最精准：
采用人工分类以及特征值提取等策略，提高搜索引擎的时效性及准确性，搜索结果精、准，不会出现垃圾，凸现了主题搜索引擎的独特优势。
结果最有价值：
品搜呈现给消费者的是最新、最旺的搜索结果，是消费者最希望看到的结果，也是消费者最喜欢的结果。
排行最公正：
主题搜索引擎克服了部分搜索引擎竞价排名的痼疾，打破了谁交的钱多谁就在最前面的局面。
品搜的排序客观、公正，按照企业自身对品搜的使用程度和社会对品牌的认可程度，把最新最旺的品牌和产品摆在消费者。
推广最自主：
主题搜索引擎使得企业级用户更自由，都可以把排到最前面，而且企业可以自行决定推广内容和效果。
品搜是全民搜索，个人和企业参与度极高，推广自主性极强。
本课题介绍面向主题搜索引擎的设计与实现；采用倒排索引方式进行索引，利用向量空间模型对web文档自动分类，由于web文档自动分类现在在技术上存在难题，所以在本课题中只叙述它的基本思想，不讲述实现，如果要实现自动分类，则需要才需要采用向量空间模型方法计算新获取的web文档与各分类之间是相似程度。
本课题中采用手工分类方法，对URL制订对应的一个分类，然后进行抓取。
2开发环境介绍2.1PHP简介
RasmusLerdorf为了创建他的在线简历而创造了“个人主页工具”。
这是一种非常简单的语言。
其后越来越多的人们注意到了这种语言并对其扩展提出了各种建议。
在许多人的无私奉献下以及这种语言本身的源代码自由性质，它演变成为一种特点丰富的语言，而且现在还在成长中。
PHP的语法与C，Perl，ASP或者JSP。
对于那些对上述之一的语言较熟悉的人来说，PHP太简单了。
相反的，如果你对PHP了解较多，那么你对于其他几种语言的学习都很简单了。
PHP数据库连接
PHP可以编译成具有与许多数据库相连接的函数。
PHP与MySQL是现在绝佳的组合。
你还可以自己编写外围的函数取间接存取数据库。
通过这样的途径当你更换使用的数据库时，可以轻松的更改编码以适应这样的变化。
PHPLIB就是最常用的可以提供一般事务需要的一系列基库。
PHP可扩展性
就像前面说的那样，PHP已经进入了一个高速发展的时期。
对于一个非程序员来说为PHP扩展附加功能可能会比较难，但是对于一个PHP程序员来说并不困难。
面向对象编程
PHP提供了类和对象。
基于web的编程工作非常需要面向对象编程能力。
PHP支持构造器、提取类等。
PHP可伸缩性
传统上web文档的交互作用是通过CGI来实现的。
CGI程序的伸缩性不很理想，因为它为每一个正在运行的CGI程序开一个独立进程。
解决方法就是将经常用来编写CGI程序的语言的解释器编译进你的web服务器。
PHP就可以以这种方式安装，虽然很少有人愿意这样以CGI方式安装它。
内嵌的PHP可以具有更高的可伸缩性。
2.2MYSQL数据库简介
MySQL是最流行的开放源码SQL数据库管理系统，它是由MySQLAB公司开发、发布并支持的。
MySQLAB是由多名MySQL开发人创办的一家商业公司。
它是一家第二代开放源码公司，结合了开放源码价值取向、方法和成功的商业模型，它具有很多优点：
）MySQL是一种数据库管理系统。
MySQL是一种关联数据库管理系统。
MySQL软件是一种开放源码软件。
MySQL数据库服务器具有快速、可靠和易于使用的特点。
MySQL服务器工作在客户端/服务器模式下，或嵌入式系统中。
有大量可用的共享MySQL软件。
MYSQL最大表尺寸增加到了65536TB，因此MySQL数据库的最大有效表尺寸通常是由操作系统对文件大小的限制决定的，而不是由MySQL内部限制决定的，win32w/FAT/FAT32最大有效表尺寸2G/4G，win32w/NTFS最大有效表尺寸2TB，Linux2.4+最大有效表尺寸4TB。
MySQL服务器采用了多层设计和独立模块。
在此列出一些：
Replication
大量使用复制功能的服务器均处于生产模式下，结果良好。
InnoDB表
自3.23.49版以来，InnoDB事务存储引擎一直很稳定。
InnoDB正用于大型、重负荷生产系统。
BDB表
BerkeleyDB码十分稳定，但在MySQL服务器中，我们仍在改进BDB事务存储引擎。
全文本搜索
全文本搜索的使用范围十分广泛。
在MySQL4.1中，增加了重要的特性增强。
MyODBC3.51MyODBC3.51采用了ODBCSDK3.51，并广泛用于生产活动中。
某些出现的情况看上去与应用程序相关，与ODBC驱动程序或底层数据库服务器无关。
3需求分析
3.1功能需求
由于网络资源的越来越丰富，分布的位置越来越广泛，不局限与某一个狭小的环境，因此用户对散布在各地的文档的检索工作变得愈加困难。
如何准确快速地从广泛的网络资源中找到我们需要的已经成为现在网络所面临的一大难题。
当前搜索引擎主要有三种，全文搜索引擎、目录搜索引擎、元搜索引擎；这三种搜索引擎都不能解决我们所需要对主题的搜索，因此，要解决这一问题就需要另外构建一种新的搜索引擎，它能为人们快速搜索所需要的具有一定的专业性的。
3.1.1系统流程图
首先建立各种分类，对应不同的主题；然后建立切分、统计词典，利用词典词条对搜索回来的web文档进行词条的切分和词频统计，并根据词频分布生成各web文档的特征向量和初始阀值，建立索引；在抓取web文档的时候要考虑要抓取的web文档是否已经被抓取过，当需要抓取的URL很多时，这是非常值得考虑的，这样可以节省时间和空间。
当用户进行查询是，系统接受用户输入，对输入的查询进行处理，然后到数据库里搜索，最后把搜索的结果采用分页方式返回给用户，用户根据需要链接，其过程如图3.1所示。
3.1.2功能模块
这个搜索引擎系统的主要目的是为用户提供搜索，因此，系统由两个大模块组成，一个是搜索模块，另一个是管理模块，管理模块又分为八个子部分，具体模块划分如图3.2所示。
搜索模块
搜索模块为用户提供搜索功能，用户直接在搜索页输入需要搜索的，然后系统处理用户输入，对数据库进行搜索，然后把得到的结果显示给用户。
列表模块
列表模块列出管理员指定搜索的URL，管理员可以对这些URL的抓取属性进行，使得对该URL的抓取可以得到很好的控制。
添加模块
添加模块用来管理需要抓取的URL，管理员可以从这里添加新的URL。
类别列表模块
类别列表模块用来显示系统中也存在的类别，在这里可以对类别属性进行。
添加类别模块
添加类别模块用来添加新的类别，管理员可以从这里直接为系统增加新类别。
索引模块
索引模块每次只对单个URL进行抓取，而在列表中可以一次要求抓取多个UR。
清除模块
清除模块主要是对列表、数据库等进行彻底清除。
统计模块
统计模块对URL、关键词等进行相关统计工作。
3.2性能需求
由于搜索引擎对web文档抓取和处理用户的搜索请求两方面是非常重要的，在web文档抓取工程中，需要对抓取工作进行严格的控制，要怎样抓取、到什么地方停止都需要进行控制；抓取web文档回来后要对web文档进行处理，对它的处理速度要快，处理该文档后就要立即处理下一个web文档。
当用户请求搜索时，响应时间要尽量短，因为响应时间直接影响到用户的使用过程。
3.3可靠性和可用性需求
搜索引擎应该能接受大量的同时搜索操作，在此时系统需要及时处理，并不能出现死机等现象；由于系统绝大部分依赖于数据库，所以数据库也应该有非常好的稳定性，当数据库出现问题时也应该能及时地恢复过来。
个人使用该系统，应完全能承受。
4面向主题的搜索引擎原理
4.1搜索引擎的主要指标及分析
搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。
这些指标决定了搜索引擎的技术指标。
搜索引擎的技术指标决定了搜索引擎的评价指标。
好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。
召回率：
一次搜索结果中符合用户要求的数目与用户查询相关的总数之比。
准确率：
一次搜索结果中符合用户要求的数目与该次搜索结果总数之比。
相关度：
用户查询与搜索结果之间相似度的一种度量。
精确度：
对搜索结果的排序分级能力和对垃圾web文档的抗干扰能力。
4.2文档表示与特征匹配
文档表示是指以一定的规则和描述来表示文档或文档类，使得一个web文档变得容易分析。
文档表示模型有多种，常用的有：
布尔逻辑型、向量空间型、概率型以及混合型等。
向量空间模型是近年来应用较多且效果较好的一种模型，本系统就采用了VSM进行文档的表示与特征的匹配。
在VSM中，将每一文档都映射为由一组规范化正交词条矢量所组成的向量空间中的一个点，对于所有的文档或未知文档，都可用此空间中的词条向量：
来表示，从而将文档的表示与匹配问题转化为向量空间中向量的表示和匹配问题来处理。
在web文档自动分类中，假设用户目标为U，未知文档为V，两者的相似程度可用向量之间的夹角来度量，夹角越小说明相似度越高，相似度计算采用公式4.1。
4.3特征提取
文档表示中词条Ti及其权值Wi的选取称为特征提取。
特征提取是文档类共性与规则的归纳过程，是分类系统的核心，特征提取算法的优劣直接影响到文档分类的效果。
词、词组和短语是组成文档的基本元素，并且在文档中的出现频率有一定的规律性，适合所有文档的特征项。
不同的词条在文档中的作用是不同的，常用词在所有文档中都有很高的出现频数，而稀有词则在全部训练文档中出现的次数都很少，这两类的词频统计特性很难确定，不适合作为特征项，应予以滤除。
还有一些词在文档中出现的频率都基本相同，区分性差，不能作为特征项也应滤除。
同简单的词汇相比，词组和短语的表达能力强，更能体现文档内容，因此应尽量多的采用词组和短语作为特征项，提高特征项的表达能力。
权重评价需要在大量训练文本的基础上，根据各特征项对文档内容的贡献，经过多次统计学习完成。
自然语言文档中，各词条在不同内容的文档中所呈现出来的频率分布是不同的，因此我们可根据词条的频率特性进行权重评价。
一个有效的特征项集，必须具备以下两个特征：
完全性：
特征项能够体现目标内容。
区分性：
根据特征项集，能将目标同其他文档区分。
根据以上两个特征可得，词条的权重与它出现在这个web文档中的次数成正比，与出现此词条的web文档数量成反比。
因此我们可构造词条权值评价公式4.2。
其中tfik表示词条Tk在文档Di中的出现频数，N表示全部样本文档总数，nk表示词条Tk出现的文档数。
在web文档自动分类是，是将一个文档类的所有训练文档合并为一个类文档进行文档类的特征提取和权重评价的。
实用中，为降低个别高频率项对其它中低项的抑制作用，计算权值时还应对词频进行均频处理。
对式进行均频，规范化处理后可得公式4.3。
此外，在实际应用中组成特征向量的特征项的个数也不宜过多，可以只保留权值较高的项，否则会大大降低系统的处理速度。
图4.1为“Java技术”类和“网络安全”类的前100个特征项的模值分布图，其中“Java技术”类属于特征项较为突出的文档类，仅前10项的模值就达到整个向量模值的80℅以上，“网络安全”类属于特征较平均的文档类，但前30项的模值也占到了83.7℅。
从图4.1中可看出，第60以后的项对整个向量的影响就很小了，他们所具有的模值和只占到总模值的4℅-7℅左右，因此在对实时性要求较高的情况下，对于较粗的分类，向量长度为30-60即可达到较好的效果。
4.4阀值确定
不同文档类所对应的特征向量和相关性阀值也不相同。
在该系统中各文档类向量的初始相关性阀值TI是按如下步骤确定的：
对文档类，任取N个样本，2N个样本；
根据公式计算出Sim和Sim；
分别做出的文档分布曲线，如图4.2所示;
图4.1特征项的模值图4.2文档分布曲线
如两曲线相交，取交点处T为初始相关性阀值；如不相交，则取曲线处为初始相关性阀值。
按上述步骤所得到的阀值只是一个经验性初值，还需根据测试集的测试结果反馈，由用户手动或自动对阀值进行修正，以达到最佳效果。
4.5分词
中文与英文不同，句子中各词语间没有间隔符，因此在进行词频统计和处理用户查询时先要对文档进行词条切分处理。
分词有很多种方法，基本上分为两类，一类是基于字符串匹配的分词方法，主要有正向最大匹配分词法、逆向最大匹配分词法、最少切分分词法等方法；另一类是基于统计的分词方法；经过统计结果表明，单纯正向最大匹配法明显差于单纯逆向最大匹配法，单纯的基于统计的分词法又优于单纯的逆向最大匹配法，从实现难度和使用角度方面考虑，因此采用了基于词典的逆向正向匹配的机械分词方法。
根据以下表格１可以更容易地说明逆向最大匹配分词法分词过程。
现有的分词系统一般都较为复杂和庞大，分词速度慢，且在处理专业技术文档时分词准确度较低，不适合在实时性要求高，文档内容专业的情况下使用。
本系统的分类对象是特定领域的技术文档，技术文档的特征项一般都是专业词汇，所以在进行特征提取时无需对普通词汇进行切分和词频统计。
因此为了提高系统运行效率和技术词条切分的准确度，我们舍弃了大型的通用切分词表，大型词典维护难度较大，且没有必要用于主题搜索引擎，仅建立了较为详尽的专业分词词典，用于中文文档的词条切分和词频统计。
在切分词条时，先根据标点进行粗切分，然后再分别使用正向或逆向最大。
如果切分结果相同，则认为切分正确；如果不相同，则在不同之处取包含两部分的最小长度串，作为词典候补词条。
专业词典只包含在本领域中可能出现的专业词条而不包含大量的普通词汇，因而能在保证提取准确性的前提下大幅度提高系统运行效率。
4.6词典结构与词频统计
VSM是建立在所有表示词条都相互正交基础上的，因此特征项词条必须保持语义上的相互独立。
自然语言具有丰富的表达形式，例如词汇间就存在同义，近义，蕴含，关联等多种关系，为解决特征词条相互独立与自然语言多样性之间的矛盾，我们建立了三个词典：
主词典，同义词词典和蕴含词词典，用于进行词条切分与词频统计，其中主词典中的词条要求在含义上保持尽可能的相互独立，其结构如图4.3所示。
1
我们是中华人民共和国的公民
取后7个字
2
民共和国的公民
字典匹配失败
……
……
……
公民
字典匹配成功
公民
华人民共和国的
减词并取后七个字
华人民共和国的
字典匹配失败
公民
……
……
的
单字直接分出
的/公民
中华人民共和国
字典匹配成功
中华人民共和国/的/公民
……
……
NULL
减词
我们/是/中华人民共和过/的/公民
进行词频统计和特征提取时，以主词典中的词条为表示词条进行处理，其中词条频数统计公式为：
式中：
TMf为主词典词条词频数；TTf为同义词词条词频数；TIf为蕴含词词条词频数；k为扩展系数，取值区间为［0，1］，用户可以指定；即表示词条在文档中的出现频数是由主词条、同义词词条、蕴含词词条3部分的词频数加权累计得到。
例如，如图4.3所示，统计表示词条“电脑”的词频时，其频数应为：
Tf=TMf+TTf+TTf+e设置同义词词典和蕴含词词典既可以解决自然语言多样性的问题，又可以解决同一事物因地域不同而产生的称谓差异问题，并且还可以起到英文文档处理中的Stemming功能。
在实际应用中还可以根据需要建立相应的近义词词典和关联词词典等进一步提高分类的准确度。
4.7数据存储结构
搜索引擎检索的文档数量巨大，所得到的数据也非常庞大，所以一个好的搜索引擎需要寻找一种好的数据存储结构，当需要对数据进行操作是能快速地得到结果；存储结构主要有顺序存储、链接存储、索引存储和散列存储方法，本课题中对关键词采用倒排索引存储方法，其具体实现如表2所示。
4.8网络蜘蛛
Internet是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议之上。
Web就是建立
在HTTP协议基础上，而HTTP又是建立在TCP/IP协议之上，它同时也是一种Socket协议。
所以网络机器人本质上是一种基
主词典
同义词词典蕴含词词典
KeyWord
DOCID
K1
DOC1DOC2
K2
DOC2DOC3DOC4
K3
DOC1DOC3DOC5
K4
DOC4DOC5DOC6
K5
DOC1DOC3DOC5
……
……
于Socket的网络
升级会员 