欢迎来到上海园丁鸟网络科技有限公司|企业网站建设企业建站企业官网建设企业官网
咨询热线:18017747315当前位置: 首页 > 网站优化百科 >
联系我们
企业网站建设 建站咨询
电话咨询:13524991327
E-mail:1424374510@qq.com
QQ:1424374510

搜索引擎原理介绍与分析

作者/整理:http://www.voez.net/ 来源:http://www.voez.net/ 日期:2019-01-07

本文对当前的搜索引擎原理进行了简要的分类介绍,概述了中•文搜索引擎的特殊性和难点,并給出了两种中文分词算法。
1.引言
信息的飞速增长,使搜索引擎成为人们查找信息的首选X 具,GSogle、百度、中搜、雅虎、等大型搜索引擎一直是人们讨论的 话题,另外还有许多针对不同信息如新闻、图片、铃声、购物等的 特定搜索引擎。通过使用搜索引擎,使人们检索信息啦能力获得 了极大的提高,成本有效的降低。但是,当前人们对搜索引擎的工 作原理还不是很了解,随着因特网的普及、网络用户的增多、搜索 技术的多样化,研究搜索引擎原理对帮助人们方便的、准确的、及 时的、专业的检索信息具有重要的规实意义。
2.不同搜索引擎的简单介绍
2.1按技术原理,搜索引擎大体可分为三大类
2.1.1全文检索搜索引擎
全文搜索引擎(Full Text Search Engine)是名副其实的搜索引 擎,国外具代表性的有 Google, Yahoo .AltaVista、Teoma、WiseNut 等,国内著名的有百度(Baidu)、北大天网、中搜等。它们都是从互 联网上提取各个网站的信息(以网页文字为主)而建立的数据库 中,检索与用户査询条件匹配的相关记录,然后按一定的排列顺 序将结果返回给用户,因此它们是真正的搜索引擎。
从搜索结果来源的角度,全文检索搜索引擎又可细分为两 种,一种是租用其他引擎的数据库,如Lycos引擎。另一种是拥有 自己的检索程序(Indexer),俗称“蜘蛛”(Spider)程序或“机器人” (Robot)程序。绝大部分搜索引擎都采用这种形式。
拥有自己检索程序的搜索引擎由三个主要部分构成: CrawLw、数据库和查询模块。Crawler是一个程序,在开始工作时 从一事先制订好的UtlL列表出发自动访问Web站点,分析提取 网页中超文本的URL,将其加人列表、并根据URL列表进一步访 问其他站点.Crawler采集到的网页信息全部存于其中。数据库的 规模直接影响了系统查询的茶权利。有些记录了网页的全部内 容,对整个HTML文件的所有单词都建立索引、有的只记录网页 地址、标题、关键词、摘要等信息,还有的能处理HTML文件中的 META的标记或其他不可见的特殊标记。査询模块提供用户访问 的査询界面和服务端的査询程序、当用户查询一个关键词时,搜 索引擎将搜索数据库,找出与关键词相符合的网页,按照一定算 法生成结果网页返回用户浏览器。
2.1.2目录搜索引擎_
目录搜索引擎(Search Index/Directory)虽然有搜索功能、但在 严格意义上算不上是真正的搜索引擎,仅仅是按目录分类的网站 链接列表而已。用户完全可以不用进行关键词查询,仅靠分类目 录也可找到需要的信息。目录搜索引擎中最具代表性的奠过于大 名鼎痛的Yahoo雅虎。其他著名的还有Open Directory Project (DMOZ)、LookSmart、About等。国内的搜狐、新浪、网易也都属于 这一类。 |
目录搜索引擎比Robot搜索引擎需更多的人T干预、其数据 库由人工建立。编辑人员先访问某个Web站点,根据内容归类,再 把网址、简介、类别等描述信息存入库中,査询时,搜索软件只需 检索这些描述。
目录界面一般采用分级结构,用户从基本的大类人口 一级级 向下访问,直至找到中意的内容;用户也可利用目录提供的拽索 功能直接査询关键词。由于自录依靠人X分类,因此搜索出的结 果往往比Robot搜索引擎更精确,但目录只在保存的站点描述中 进行捜索,站点本身的变化不会反映到捜索结果中。
由于目录和基于Robot的搜索引擎有各自的优缺点,很多搜 索引擎都同时提’供目录和基于Robot的搜索服务,以便尽可能地 提供全面准确地査询结果。
2.1.3元搜索引擎
元搜索引擎(Meta Search Engine)在接受用户查询请求时,同 时在其他多个引擎上进行搜索,它自己不进行WWW的遍历,也 没有自己的索引数据库。当用户查询一个关键词时,它把查询请 求转换为其他搜索引擎的命令格式,分别向其它搜索引擎提交, 然后汇总这些搜索引擎返回的结果,组织后返回用户浏览器。利 用Meta搜索引擎、査询范围可涉及多个搜索引擎的数据库。著名 的搜星搜索引擎就是一个中文元搜索引擎。
2.1.4其他搜索引擎 -
除了前面三大搜索引擎外,还有以下几种非主流形式:
集合式搜索引擎:如HotBot在2002年底推出的引擎。该 引擎类似META搜索引擎,但区别在于不是同时调用多个引擎进 行搜索,而是由,用户从提供的4个引擎当中选择,因此叫它“集合 式”搜索引擎。
门户搜索引擎:如AOL Search,MSN Search等虽然提供搜 索服务,但自身即没有分类目录也没有数据库,其搜索结果完全 来自其它引擎。
免费链接列表(Free For All Links,简称FFA):这类网站一 般只简单地滚动排列链接条目,少部分由简单的分类目录,不过 规模比起Yahoo等目录索引来要小得多。
2.2按工作语种区分
捜索引擎按工作语种区分为下列类型:
单语种搜索引擎:单语种搜索引擎是指搜索时只能用一 种语言查询的搜索引擎。
多语种搜索引擎•.多语种搜索引擎是指那些可以用多种 语言查询的搜索引擎。如“Altavista",该网站可以用25种语言进行查询。
2.3按搜索范围区分 ,
搜索引擎按搜索范围可以区分为下划类型:
独立搜索引擎:这类搜索引擎检索时只在自己的数据库 内进行,尤其反馈出相应的查询信息,或者是相联结的站点指向。 每个独立的搜索引擎都会有各自的査询特色,例如:目录査询、全 文査询、简单査询、高级査询等。
多元搜索引擎:多元搜索引擎又称集成搜索引擎。它是将 多个独立捜索引擎集合在一起,提供一个统一的检索界面,苗用 户提出检索提问后,它会将其发送给多个搜索引擎,同时检索多 个数据库,并进行相关度排序后,将结果显示给用户。利用这类搜 索引擎能够获得更大范围的信息源,检索的综合性,全面性也有 所提高^不过这样的搜索引擎的缺点是查询时间相对较长。
3.捜索引擎的组成
通常来说,一个搜索引擎由搜索器、索引器、检索器和用户接 口等四个部分组成。
搜索器:搜索器的功能是在互连网中漤游,发现和搜集信 息。它常常是一个计算机程序,日夜不停地运行。它要尽可能多、尽 可能快地搜索各种类型的新信息,同时因为互连网上的信息更新 很快,所以还有定期更新已经搜集过的旧信息,以避免死连接和无 效连接。
索引器:索引器的功能是理解捜索器所搜索的信息,从中 抽取出索引项,用于表示文档以及生成文档库的索引表。索引器可 以使用集中式索引算法或分布式索引算法,当数据量很大时,必须 实现即时索引,否则不能够跟上信息量急剧增加的速度。索引算法 对索引器的性能(如大规模峰值查询时的响应速度)有很大的影 响。一个搜索引擎的有效性在很大程度上取决于索引的质量。
检策器:检.索器的功能是根据用户的査询在索引库中快 速检出文档,进行文档与査询的相关度评价,对将要输出的结果 进行排序,并实现某种用户相关性反馈机制。
用户接口:用户接口的作用是输入用户査询、显示査询结 果、提供用户相关性反馈机制。主要目的是方便用户使用搜索引 擎,高效率、多方式地从搜索引擎中得到有效、及时地信息。用户 接口的设计和实现使用人机交互的理论和方法,以充分适应人类 的思维习惯。
4.中文搜索引擎介绍
国内的Intemet从1994年开始发展,至今已积累了相当庞大 的中文信息资源。为了方便检索,中文搜索引擎是必然产物。中文 搜索引擎的工作原理和机制与国外搜索引擎大致相同,但中文搜 索引擎由于汉语语言文字的特殊性,在搜索信息算法方面有其自 身特点。
4.1中文信息处理的特殊性和难点
在进行中文信息处理时,须考虑汉字系统的以下特点:
(1)汉宇字符数量多、编码方式复杂
与英文相比,汉字系统的一个显著特点就是其字符数目很 多。英文中的基本元素是26个英文字母和一些附加字符。在计算 机中用标准的ASCII字符集就足够处理了。而汉语中的基本字符 非常的多,每一个汉字都是最基本的独立宇符,汉字的数目达约 有数万个之多。
(2)中文词的处理
与英文不同,宇是汉语的基本独立单位,但是具有一定语义的 最小单位却是词,词由单个或多个字构成,一般用得最多的是二字 词,其次是单字词,另外还有一些多字词(如成语、专有名词等)。
中文词的一个特点是数量繁多。汉语中常用的词有几万条, 《现代汉语词典》中收录的词就达六万个之多。而且,随着社会的 发展,不断地有新词产生。中文词的另一个特点就是使用灵活、变 化多样,例如同样的两个连续汉字,在有的句子中构成一个词,而 在另外的句子环境中,确可能不构成词。这给计箅机的词法分析工作带来了极大的困难。
..处理中女信息的另一个难点源于汉字的书写习惯。在英文系 统中,词与词之闾在书写上用空格隔开,计算机处理时可以非常 容易地从文档中识别出一个一个的词。而在汉语系统中,书写以 句子为单位,句间有标点隔开,在句内,宇和词则是连续排列的, 它们之间没有任何分隔。这样,如果要对中文文档进行基于词的 处理,必须先要进行词的切分处理,以正确地识别出每一个词。
基于中文字词的特点,,中文搜索引擎必须要有专门的中文信 息处理模块来完成中文文档的分词处理、码制转换和全角处理等 工作。
4.2中文自动分词方法
目前的分词方法很多,常用的有正向最大匹配法、逆向最大 匹配法、最佳匹配法、逐词遍历法、抽取中频字串諉,此外还有邻 近约束法、最少分词法等。但归纳起来不外乎两类:一类是理解式 切词法,即利用汉语的语法知识和语义知识以及心理学知识进行 分词,需要建立分词数据库、知识库和推理机:另一类是机械式分 词法,一般以分词词典为依据,通过文档中的汉字串和词表中的 词逐一匹配来完成词的切分。相比而言,第一类分词方案的算法 复杂度高%其有效性与可行性尚需在实际工作中得到进一步地验 证。因为汉语毕竟是缺乏词的标志和严格的构词规则。语言界现 有的词法、句#及组合规则仍然是十分笼统和复杂的。能否有效 的、系统地转k成可为计算机采用的形式恐怕难以定论。因此,这 种分词方法仅是处于研究阶段,距离实用化还有很大差距,一般 不宜釆用。第二类分词法实现简单,比起第一类较具体、实用。而 且也可以达到较髙的准确度。因此,本文将采用基于词典的正向 最大匹配法和逆向匹配法相结合的分词方案,既保证了分词的效 率和速度,又可以消除一部分交集性歧义,保证较高的分词准确 度。下面将介绍正向最大匹配法和逆向最大匹配法。
4.2.1_.正向最大匹配法 .
正向最大匹配法又称MM &,其目的是将最长的复合词分离 出来,它的基本思想是:假定分词词典中的最长词有i个汉字字 符,则用被处理文档的当前宇串中的前i个字作为匹配字段,查找 字典。若字典中存在这样的一个i字词,则匹配成功。匹配字段被 作为一个词切分出来。如果词典中找不到这样的一个i字词,则匹 配失败。将匹配字段中的最后一个字去掉,对剩下的字串重新进 行匹配处理……如此进行下去,直到匹配成功,切分出一个词或 剩余字串的长度零为止。这样就完成了一轮匹配,然后取下一个i' 字串进行匹配处理,直到文档被扫描完为止。
其算法描述如下:
句子:s=c,c2 cn;
假设诃为词典中最长词的字数;
(1)令i=0,当前指针P,指向输入字串的初始位置,执行下面 的操作: '
_ (2)计算当前指针Pi到字串末端的字数(即未被切分字串的 长度)n,if n=l,转(3)。否则另m等于词典中最长单词的字数,if n< m,令 m=n;
(3)从当前Pi起取m个汉字作为w,,作如下判断:
如果Wi确实是词典中的词,则在w后添加一个切分标 志,转(c);
如果不是词典中的词且Wi的长度大于1,将从右端 去掉一个字,转(2)中的i步;否则(w的长度等于1),则在Wi后添 加一个切分标志,将%作为单字词添加到词典中,执行(c);
(C)根据w的长度修改指针&的位置,如果Pi指向字符串末 端,转(3),否则_i=i+li返囬(1);
(3)输出切分结果,结束分词程序。
4:2.2逆向最大匹配法
这种方法又称为RMM法,其基本原理和MM法相同,不同的 是分词切分的方向与MM法相反,并且使用的分词词典也不同。
逆向最大匹配法从被处理的文档的末端开始K配扫描,每次取最 末端的2i个字符作为匹配字段,若匹配失败,则去掉匹配宇段最 前面的一个字,继续匹配。相应地,它使用的分词词典是逆序词 典,其中的每个词条都按逆序存放。在实际处理时,先将文档进行 倒排处理,生成逆序文档。然后根据逆序词典,对逆序文档用正向 最大匹配法处理即可。据统计,逆向最大匹配法比正向最大匹配 法的误差要小。例如切分宇段“硕士研究生产”,正向最大匹配的 结果会是“硕士研究生/产”,而逆向最大匹配法利用逆向扫描可 得到正确的切分结果“硕士 /研究/生产”。
当然,由于最大匹配法是一种基于分词词典的机械分词法, 不能根据文档上下文的语义特征来切分词语,对词典的依赖性较 大。所以在实际使用时,难免会造成一些分词错误。
为了提髙系统分词的准确度,本文采用了正向最大匹配法和 逆向最大四配法相结合的分词方案,先根据标点对文档进行粗切 分,把文档分解成若干个句子,然后再对这些句子用正向最大匹 配法和逆向最大匹配法进行扫描切分。如果两种分词方法得到的 匹配结果相同,则认为分词正确,否则,按最小集处理。
5.总结
本文介绍了当前搜索引擎的原理,并对它们进行了分类,概 述了中文搜索引擎的特殊性与难点,介绍了一种基于词典的正向 最大匹配法与逆向最大匹配法相结合的分词方案,可以高效.准 确地实现中文文档的主题词条的抽取和词频统计。当然,随着 Internet的网络的进一步发展,随着搜索引擎的多样化和中文信息 应用水品的不断提高,人们会对搜索引擎的要求越来越高,搜索引 擎的原理、分类、算法等方面也会随之发生复杂的变化。