深入解析传统搜索引擎排序算法：Direct Hit、PageRank与竞价排名服务

一、传统搜索引擎排序算法概述

1. 1 搜索引擎排序算法概述

搜索引擎查询结果按一定规则排序供用户查看，此规则即搜索引擎排序算法。目前通用的搜索引擎排序算法有 Direct Hit 排序算法、PageRank、排名竞价服务和词频位置加权排序算法。Direct Hit 排序算法是动态排序算法，搜索引擎返回的排序结果会随用户点击和网页被浏览时间而变化。PageRank 是 Google 使用的排序算法，利用网页链接结构计算 PR 值来排序。竞价排名服务是一些网站购买关键字排名，搜索引擎按点击（或按时间段）计费的服务。词频位置加权排序算法是从关键字出现次数和位置考虑进行排序的算法。文章主要讨论词频位置加权排序算法。

1. 2 词频位置加权排序算法

如果能对网页进行分块并按一定算法尽量去除广告和导航等噪音信息，将会有效提高相关度计算的准确度。

二、 网页分块算法介绍

目前针对网页进行分块的方法研究有很多。其中较为有效的是微软亚洲研究院提出的 VIPS（基于视觉的页面分割）。笔者仅对 VIPS 进行讨论。在 VIPS 算法中，对 Web 页面的结构定义为：把网页视为一个三元组。

将网页看作一个三元组

其中

给定页面上的语义块集合，这些语义块互不重叠覆盖，且每一个语义块都可被定义为前面所描述的三元组。

如此迭代循环.

当前页面上所有分隔条的集合。当确定一个页面上的两个语义块后，这两个语义块之间的分隔条就被确定了。在 VIPS 中，分隔条并非真正存在，而是虚拟的。分隔条包括水平分隔条和垂直分隔条，且每一个分隔条都有一定的宽度和高度。

则描述了集合中两个语义块之间的关系, 这种关系可以描述为

其中每个δ都属于形如( v i, v j )的二元组，这意味着在块 v i 和 v j 之间存在一个分割条。

VIPS 借助 Web 页面的一些视觉提示，像背景颜色、字体颜色与大小、边框以及逻辑块之间的间距等，并且和 DOM 树相结合来对页面进行分块。它包含三个步骤，分别是页面块提取、分隔条提取以及语义块重构。这三个步骤共同构成一次语义块检测的完整流程。首先，Web 页面会被分割成几个比较大的语义块，与此同时，这些语义块所构成的层次结构会被记录下来。对于检测出来的每一个大的语义块，分块过程还可以继续进行，一直到语义块的 Doc（连贯性程度）值达到预先设定的 Pdoc（允许的连贯性程度）为止。VIPS 的分割效果如图 1 所示。

三、搜索引擎排序算法改进

3. 1 网页净化规则

网页分出块之后，关键问题在于如何判别语义块中的广告、导航条等噪声网页块，以净化网页并提高搜索引擎排序准确度。经过大量的统计与分析，利用网页块的文字和链接数量、网页块的空相对空间位置以及网页块内容属性，笔者总结出三条规则来识别噪声语义块。首先，将网页窗口原点坐标定义为网页的左上顶角，网页块中心横坐标 X 为该块中心点在窗口中的横坐标，同时还有网页块中心纵坐标 Y、网页宽度 M 和网页高度 N 。通过网页块的相对空间位置来定义网页空间位置，其定义方式为……

网页的位置分为上、下、左和右。如果某个网页分块在这些位置上，并且该分块中文字数量与链接数量的比小于 F1，那么这个分块就是噪音分块。

网页块处于中间位置，并且文字数量与链接数量的比小于 F2 ，那么这个块就是噪音分块。

如果网页块的内容是整块的 Flash 文件，那么就可以判断该块是噪音块。

网页中存在行数超过 3 的 Text 控件，就可以判断该块是噪音块。

3. 2 改进的排序算法描述

本算法使用 VIPS 来对网页进行划分成块的操作，并且运用所制定的规则对网页进行净化处理，以此来达成优化排序算法的目的。具体的算法情况如下：

网页库 P 以及查询 Q，还有阈值 F1 、F2 、R1 、R2 、R3 、R4 。

输出: 排好序的页面集合Sp .

( 1) 统一化网页, 规整网页中不规则的标签.

( 2) 对网页P i 利用VIPS 进行分块.

利用规则来进行判断，同时去除网页中的噪音，以此达到净化网页的目的。

( 4) 过滤停用词.

( 5) 获取关键词.

利用关键词的位置来计算查询词 Q 与网页 P i 的相关度，同时利用关键词的频次进行加权计算，得出查询词 Q 与网页 P i 的相关度。

( 7) Return Sp .

从算法中能够看出，所有文档都要先经过净化，然后才去参与相关度的计算，并且是在用户进行检索的时候实时计算出来的。式(1)是词频位置加权算法的典型公式，它用于计算某文档对应于用户查询关键字的得分。

式中：文档 j 对应于用户查询词的得分是 sj；文档 j 中包含的所有可供查询的词条数量是 cj；查询词 i 在文档 j 中出现的频率是 tij；查询词 i 在文档中出现的倒排词频是 fi；b 为在索引过程中设置的字段参数，通常为 1.0。

文档的排名不会受其影响，此与文档无关。在式(2)里，l j 代表文档 j 的长度。可以发现，经过网页分块且净化网页之后，对 r 的影响较为显著，而 r 是式(1)中影响排序得分的重要因素。假设有两篇文本，内容如下：

b. txt : I am a student.

根据式(2)，能够算出 r 分别是 0.3125 和 0.5。b.txt 是 a.txt 去除广告主题后的内容，由此可以看出 b.txt 中内容的 r 有所提高，进而整个的排序得分也提高了。在进行网页分块、净化之后，改进算法用净化后的网页来代替整张网页参与检索，以此提高排序的正确性。