搜索引擎算法是解决什么问题的算法？(图)

　　搜索引擎算法是解决什么问题的算法？(图)

　　搜索引擎算法研究报告 在我了解和研究搜索引擎算法之前，我认为有必要了解搜索引擎。同时，了解搜索引擎算法是用来解决问题的。随着信息技术的发展，搜索引擎系统每天为大量用户提供信息检索服务。搜索引擎是万维网中的信息检索系统。它的定义是：搜索引擎是指按照一定的策略采集互联网上的信息，并使用特定的计算机程序，对信息进行组织和处理，向用户展示信息，并为用户提供检索服务的系统。简单的说，搜索引擎就是在万维网上为每个人提供海量信息，寻找你需要的信息服务。简单地对搜索引擎进行分类，只有两种类型。一种是全文索引搜索引擎，如谷歌必应和百度。二是目录索引搜索引擎，如雅虎和新浪。对于目录索引，虽然有搜索功能，但严格来说还不能称为真正的搜索引擎。目录索引只是按目录分类的网站 链接列表。因此，我对搜索引擎算法的研究仅限于对全文索引搜索引擎系统中的各个算法进行简单的理解和学习。要理解一个算法，首先要搞清楚这个算法解决什么样的问题，比如数值计算或者数据处理。因此，首先要了解全文索引搜索引擎系统的组成，了解该系统的工作原理，以及该系统具体解决哪些问题。我关注的全文索引搜索引擎系统，按照其原理可以分为三个部分。

　　第一部分是从互联网上获取网页，第二部分是建立索引数据库，第三部分是在索引数据库中搜索和排序。搜索引擎工作的第一步，也就是从互联网上抓取网页时，是依靠一个抓取程序来工作的。这个爬虫程序有几个版本，蜘蛛程序，爬虫程序（Craw），机器人程序（Robot）。这时候的工作就是通过互联网上的各种链接自动获取大量的网络信息内容。这一步完成后，只能得到大量的网页信息，比较杂乱或者没有重点。因此，后两部分的工作就是将这些网页信息按照一定的规则进行分析和排序，从而建立一个数据库，并在用户提出搜索时提供排序后的索引内容。由此可以看出，搜索引擎的算法一般是指解决如何分析和组织网页信息的算法。当然，搜索引擎系统在获取网页内容的时候，也是按照一定的算法进行的。但我主要关心的是搜索引擎？？如何理解分析和排序网络内容的算法。通过文献查阅，通过搜索引擎的帮助。据了解，在过去十年的发展中，网页分析算法大致可以分为三类：基于网络拓扑、基于网页内容和基于用户访问行为。基于网络拓扑的分析算法是基于网页之间的链接，通过已知的网页或数据，对直接或间接链接到它们的网页或网站进行评估。

　　所谓的链接分析算法。链接分析算法包括PageRank算法、HITS算法和SALSA PHITS Bayesian等算法。下面简单介绍一下PageRank和HITS算法。以下介绍是根据网上整理的相关内容。 PageRank 算法 PageRank 算法是 Google 的算法。谷歌的架构类似于传统的搜索引擎。谷歌与传统搜索引擎最大的不同在于，它根据权威值对网页进行排序，让最重要的网页出现在搜索结果的顶部。 Google 通过 PageRank 元算法计算网页的 PageRank 值，从而确定网页在结果集中的位置。 PageRank 值越高，在结果中的位置就越高。 PageRank 算法基于以下两个前提： 前提 1：一个网页被多次引用，可能很重要；一个网页虽然没有被多次引用，但是被重要的网页引用，也可能是重要的；一个网页的重要性均匀地传递给它所指的网页。这种重要的网页被称为权威网页。前提2：假设用户一开始随机访问了网页集合中的一个网页，然后不回退，而是按照该网页的传出链接向前浏览该网页，则浏览下一个网页的概率为该网页的PageRank值。正在浏览的网页。

　　简单的PageRank算法描述如下：u是一个网页，u指向的网页的集合，指向u的网页的集合，以及指向u外的链接数。显然=|??|，c是一个normalization Factor（谷歌通常取0.85），（这个记法也适用于后面介绍的算法），那么u的Rank值计算如下：算法的形式描述，算法也可以用矩阵来描述，设A为方阵，行列对应网页集合的网页。如果网页i有网页j的链接，否则= 0.设V为网页集合对应的向量，V=cAV，V A的特征根就是c的特征向量，其实只需要最大特征根的特征向量，就是最终的页面集对应的PageRank值，可以通过迭代法计算。?如果有两个网页相互指向a、b，则它们不指向任何其他网页，并且有某个网页c指向对a和b之一，比如a，那么在迭代计算中，a和b的秩值是不dis的贡品，但不断积累。如下图：为了解决这个问题，Sergey Brin 和 Lawrence Page 改进了算法，引入了衰减因子 E(u)，E(U) 是对应网页集的向量，对应初始秩值，算法改进如下： 其中，=1，对应的矩阵形式为V'=c(AV'+E)。 ?另外还有一些特殊的链接，没有网页的外链。

　　PageRank计算时，先去掉这种链接，计算完成后再添加。这对网页最初计算的排名值影响不大。 HITS算法 HITS（Hyperlink-Induced Topic Search）算法是一种使用Hub/Authority方法的搜索方法。算法如下： 基于关键字匹配将查询q提交给传统搜索引擎。搜索引擎返回的网页很多，其中的前n个网页作为根集，用S表示。S满足以下三个条件： 1. S中的网页数量相对较少2． S中的大部分网页都是与查询q3相关的网页。 S 中的网页收录更多的权威网页。通过添加S引用的网页和引用S到S的网页，将S扩展为更大的集合T。将T中的Hub网页作为顶点集V1，权威网页作为顶点集V2，来自V1中的网页到V2中的网页作为边集E，形成二部有向图SG=(V1,V2,E)。对于V1中的任意顶点v，用h(v)表示网页v的Hub值，对于V2中的顶点u，用a(u)表示网页的Authority值。开始时h(v)=a(u)=1，对u进行I操作修改其a(u)，对v进行O操作修改其h(v)，然后归一化a(u)，h (v )，从而重复计算以下操作 I 和 O，直到 a(u) 和 h(v) 收敛。

　　（证明该算法收敛可见）操作I：?? (1）O操作:?(2）每次迭代后，a(u),h(v)需要归一化：公式(1)反映了如果一个网页被很多好的Hub所指向，它的权威值会相应增加（即权威值增加到所有指向它的网页的现有Hub值之和）。公式（2)反映了如果一个网页指向很多好的权威页面， Hub 值会相应增加（即Hub 值增加到该网页链接的所有网页的权威值之和）。和PageRank 算法一样，HITS 可以用矩阵的形式来描述算法。HITS 算法输出一组Hub值较大的网页和权限值较大的网页，其他链接分析算法我没做过多了解，PageRank和HITS算法是最常见的链接分析算法，都是通过递归和网页间链接度的标准化计算，评估每个网页的重要性。 PageRank算法虽然考虑了用户访问行为的随机性和Sink网页的存在，但忽略了大多数用户有目的的访问。性质，即网页和链接查询主题的相关性。针对这个问题，HITS算法提出了两个关键概念：权威和枢纽。对于基于网页内容的网页分析算法，我理解的基于网页内容的分析算法是指利用网页内容（文本、数据等资源）的特性对网页进行评价。

　　网页内容已从基于超文本的内容演变为动态页面数据。后者的数据量大约是直接可见的页面数据的400到500倍。另一方面，多媒体数据、Web Service等各种形式的网络资源日益丰富。因此，基于网页内容的分析算法已经从最初的简单的文本检索方法发展为涵盖网页数据提取、机器学习、数据挖掘、语义理解等多种方法的综合应用。对基于用户访问行为的页面分析算法没有了解。