论文部分内容阅读
摘 要 是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎等。
关键词 搜索 算法
一、概述
搜索引擎是采用特定的程序（spider）完成从互联网中提取信息的数据库系统，它的主要功能是为用户提供全网范围的快速查询。它将信息存储为表格的形式，这就是索引（index）。在索引数据库中，网页中所有内容，包括文本内容以及相应的格式、控制、关键词语出现的位置等信息都有相应的记录。我们搜索关键字时，相关的页面会被找出来，并按照关键词相关程度、用户欢迎程度等指标排出顺序，这就是排序算法。
搜索引擎一般分为全文搜索引擎、目录式搜索引擎、元搜索引擎。1、全文搜索引擎：目前百度、谷歌、AltaVista、Lycos等是全文搜索引擎的代表，但其中有部分搜索引擎没有自己的蜘蛛程序，需要租用其它搜索引擎的数据库，但用自己的排序算法对搜索结果进行排序。从这里可以知道，排序算法才是搜索引擎最核心的机密。搜索引擎获取信息有两种方式：一种是主动定时采集，也就是用爬行器对各网段进行定时检索；第二种是由网站自行提交网址，由搜索引擎审核。
2、目录式搜索引擎：目录搜索引擎没有爬虫程序，此类搜索引擎的功能只有对提交给它的网站进行分类整理。网站对它提交关键住处，引擎对他们分类，形成一个链接到站点的目录列表。这些引擎的代表为新浪目录、Dmoz、雅虎搜索等等。3、元搜索引擎：它们实际上只是搜索引擎与用户之间的接口，用户提出请求之后，它在众多搜索引擎上检索，排自己的算法进行筛选和排序。问答聚合就是一个元搜索引擎。
二、搜索引擎组成
1、Spider/爬虫：搜索引擎使用大量爬虫检索整个网络，将各服务器中的数据采集到本地数据库中。爬虫从已有数据库开始，在网页中逐级逐个查找链接，直到找完所有链接。从理论上讲，爬虫可以找到互联网所有网页。但有数据表明，部分网页无法找到；另外，个别搜索引擎通过不正当手段采集信息孤岛。
2、索引器与索引数据库：索引器的主要功能是将收集来数据进行分析，提炼出其中的索引项，用倒排索引的方式建立数据表，按关键字搜索对应的文档。
3、 检索器：检索器获得网页，然后计算文内容与查询要求的相关程度，根据相关程度的高低来排序展现。因此，排序算法是评价搜索引擎优劣重要指标。
三、 排名引擎算法
1、 第一代排序算法： 词频统计和词位置加权。
文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高，其相关度越大。但当关键词为常用词时，使其对相关性判断的意义非常 小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。TF（Term Frequency）：单文本词汇频率，用关键词的次数除以网页的总字数，其商称为“关键词的频率”。IDF（Inverse Document Frequency）：逆文本频率指数，其原理是，一个关键词在N个网页中出现过，那么N越大，此关键词的权重越小，反之亦然。当关键词为常用词时，其权 重极小，从而解决词频统计的缺陷。词位置加权是通过对检索关键词在Web页面中不同位置和版式，给予不同的权值，从而根 据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有：是否是标题，是否为关键词，是否是正文，字体大小，是否加粗等等。同时，锚文本的信 息也是非常重要的，它一般能精确的描述所指向的页面的内容。
tf-idf模型：
2、第二代算法：链接分析
链接分析排序的思路是，网页被引用的次数越多，说明该网页越受欢迎，被越权威的网页引用，说明该网页质量越高。下面介绍两个经典算法：
（1）PageRank算法
PageRank算法是Google搜索引擎采用的静态算法。它的基本思想来源于学术文献引用，论文被引用的次数越多，价值越大。若引用者的权威性高，则被引用者权威性也增加。相应的，网页重要程度也由两个方面衡量：一、引用该页的页面个数，二、引用该页的页面重要程度。
d：阻尼系数。为避免链接沉淀问题提出的系数，常指定为0.85；
PR（Ti）：网页Ti的PageRank值；
C（Ti）：网页Ti链出的链出数量。
这个公式是收敛的，多次迭代后将得到稳定的值。实验证明，迭代十次后值趋于稳定。
（2）HITS算法
HITS（Hyperlink Induced Topic Search）算法，是另一个著名的超链分析算法。该算法将网页分为hub（中心页面）和Authority（权威页面）。Authority页是与用户查询的关键词最相近的页面，hub页的主要内容是大量指向Authority页的链接，相当于Authority页的目录。一般来说，好的Hub网页指向许多好的Authority网页，好的Authority网页是由许多好的Hub网页所指向，这便是相互加强模型。通过这种关系可以计算出Authority属性较高的网页，也就是重要性强的网页。
中心值和权威值相互加强的公式：
，迭代以后规范化，即可得到期望结果。
四、发展趋势
1、垂直搜索引擎，此类搜索引擎是对数据库中数据的再次筛选，只搜索特定领域或行业的内容。在某种程度上，这可能会解决搜索引擎结果太过宽泛的问题问题。
2、 个性化搜索引擎，它基于用户习惯的详细分析。这需要对用户进行长期的监视，显然与保护个人隐私有着不可回避的矛盾。3、知识搜索引擎，它不是单纯搜索工具，而是实现知识管理的一种工具，通过搜索引擎技术完成知识管理。实现知识汇聚、知识发现、知识分类、知识聚类、知识门户的构建等。
关键词 搜索 算法
一、概述
搜索引擎是采用特定的程序（spider）完成从互联网中提取信息的数据库系统，它的主要功能是为用户提供全网范围的快速查询。它将信息存储为表格的形式，这就是索引（index）。在索引数据库中，网页中所有内容，包括文本内容以及相应的格式、控制、关键词语出现的位置等信息都有相应的记录。我们搜索关键字时，相关的页面会被找出来，并按照关键词相关程度、用户欢迎程度等指标排出顺序，这就是排序算法。
搜索引擎一般分为全文搜索引擎、目录式搜索引擎、元搜索引擎。1、全文搜索引擎：目前百度、谷歌、AltaVista、Lycos等是全文搜索引擎的代表，但其中有部分搜索引擎没有自己的蜘蛛程序，需要租用其它搜索引擎的数据库，但用自己的排序算法对搜索结果进行排序。从这里可以知道，排序算法才是搜索引擎最核心的机密。搜索引擎获取信息有两种方式：一种是主动定时采集，也就是用爬行器对各网段进行定时检索；第二种是由网站自行提交网址，由搜索引擎审核。
2、目录式搜索引擎：目录搜索引擎没有爬虫程序，此类搜索引擎的功能只有对提交给它的网站进行分类整理。网站对它提交关键住处，引擎对他们分类，形成一个链接到站点的目录列表。这些引擎的代表为新浪目录、Dmoz、雅虎搜索等等。3、元搜索引擎：它们实际上只是搜索引擎与用户之间的接口，用户提出请求之后，它在众多搜索引擎上检索，排自己的算法进行筛选和排序。问答聚合就是一个元搜索引擎。
二、搜索引擎组成
1、Spider/爬虫：搜索引擎使用大量爬虫检索整个网络，将各服务器中的数据采集到本地数据库中。爬虫从已有数据库开始，在网页中逐级逐个查找链接，直到找完所有链接。从理论上讲，爬虫可以找到互联网所有网页。但有数据表明，部分网页无法找到；另外，个别搜索引擎通过不正当手段采集信息孤岛。
2、索引器与索引数据库：索引器的主要功能是将收集来数据进行分析，提炼出其中的索引项，用倒排索引的方式建立数据表，按关键字搜索对应的文档。
3、 检索器：检索器获得网页，然后计算文内容与查询要求的相关程度，根据相关程度的高低来排序展现。因此，排序算法是评价搜索引擎优劣重要指标。
三、 排名引擎算法
1、 第一代排序算法： 词频统计和词位置加权。
文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高，其相关度越大。但当关键词为常用词时，使其对相关性判断的意义非常 小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。TF（Term Frequency）：单文本词汇频率，用关键词的次数除以网页的总字数，其商称为“关键词的频率”。IDF（Inverse Document Frequency）：逆文本频率指数，其原理是，一个关键词在N个网页中出现过，那么N越大，此关键词的权重越小，反之亦然。当关键词为常用词时，其权 重极小，从而解决词频统计的缺陷。词位置加权是通过对检索关键词在Web页面中不同位置和版式，给予不同的权值，从而根 据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有：是否是标题，是否为关键词，是否是正文，字体大小，是否加粗等等。同时，锚文本的信 息也是非常重要的，它一般能精确的描述所指向的页面的内容。
tf-idf模型：
2、第二代算法：链接分析
链接分析排序的思路是，网页被引用的次数越多，说明该网页越受欢迎，被越权威的网页引用，说明该网页质量越高。下面介绍两个经典算法：
（1）PageRank算法
PageRank算法是Google搜索引擎采用的静态算法。它的基本思想来源于学术文献引用，论文被引用的次数越多，价值越大。若引用者的权威性高，则被引用者权威性也增加。相应的，网页重要程度也由两个方面衡量：一、引用该页的页面个数，二、引用该页的页面重要程度。
d：阻尼系数。为避免链接沉淀问题提出的系数，常指定为0.85；
PR（Ti）：网页Ti的PageRank值；
C（Ti）：网页Ti链出的链出数量。
这个公式是收敛的，多次迭代后将得到稳定的值。实验证明，迭代十次后值趋于稳定。
（2）HITS算法
HITS（Hyperlink Induced Topic Search）算法，是另一个著名的超链分析算法。该算法将网页分为hub（中心页面）和Authority（权威页面）。Authority页是与用户查询的关键词最相近的页面，hub页的主要内容是大量指向Authority页的链接，相当于Authority页的目录。一般来说，好的Hub网页指向许多好的Authority网页，好的Authority网页是由许多好的Hub网页所指向，这便是相互加强模型。通过这种关系可以计算出Authority属性较高的网页，也就是重要性强的网页。
中心值和权威值相互加强的公式：
，迭代以后规范化，即可得到期望结果。
四、发展趋势
1、垂直搜索引擎，此类搜索引擎是对数据库中数据的再次筛选，只搜索特定领域或行业的内容。在某种程度上，这可能会解决搜索引擎结果太过宽泛的问题问题。
2、 个性化搜索引擎，它基于用户习惯的详细分析。这需要对用户进行长期的监视，显然与保护个人隐私有着不可回避的矛盾。3、知识搜索引擎，它不是单纯搜索工具，而是实现知识管理的一种工具，通过搜索引擎技术完成知识管理。实现知识汇聚、知识发现、知识分类、知识聚类、知识门户的构建等。