简易垂直搜索引擎的核心算法总结

1.   倒排索引

倒排索引源于实际应用中需要根据属性值（字段）来查找记录（所在的文件位置）。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。

目前主流的索引技术有三种：倒排索引、后缀数组以及签名。后缀数组虽然快，但是维护困难，代价高昂，不适合作为搜索引擎的索引。而签名的速度和性能都不如倒排索引。因此倒排索引是各种搜索引擎中被主要使用的一种索引技术，同时也是搜索引擎的一个核心技术。

建立倒排索引的步骤一般为：

1)        建立前向索引

假设有网页P1，P2，……，Pn，网页中的每一个关键字为W1，W2，……，Wn，每个关键字在网页出现的次数对应为N1，N2，……，Nn，关键字Wi在某一网页中出现的位置记录为数组POSi = <pos1, pos2, …, posk>。

那么，通过中文分词工具将网页逐一分解成关键字序列之后，就能按如下格式建立前向索引了：

Pi = {[N1, W1, POS1], [N1, W1, POS2], …, [Nj, Wj,POSj], …, [Nn, Wn, POSn]}

其中位置数组POSi = <pos1,pos2,…,posk>相互独立；Ni = 0（出现次数为0）的关键字Wi可以被舍弃而不出现在索引序列中。

2)        通过前向索引建立倒排索引

可见，前向索引是通过网页名来索引关键字及其位置（网页→关键字）。而在搜索引擎的应用中，实际上需要的是通过关键字来检索它所出现过的网页中的位置（关键字→网页），正好与前向索引相反。因此需要将前向索引转换成倒排索引。

实现中，可以通过将网页和关键字分别编号，建立矩阵Index[i][j]。其中i表示编号为i的网页，j表示编号为j的关键字，Index[i][j]表示关键字j在网页i中出现的次数与位置对象。

然后依次扫描每个关键字，按照下列各式建立倒排索引：

Wi = {[N1, P1, POS1], [N1, P1, POS2], …, [Nj, Pj,POSj], …, [Nn, Pn, POSn]}

其中Nj表示关键字Wi在网页Pj中出现的次数，POSj表示关键字Wi在网页Pj中出现的位置数组。

2.   向量空间模型

向量空间模型是通过特征向量将索引抽象为表示文本文件集合的代数模型的一种方式。抽象的目的是通过向量间的计算进行信息过滤、相关性排序等。

向量空间模型通常是基于关键词的，并且通过关键词在网页库各文件中出现的频率计算每个网页的特征向量。同时，可以给查询式中的每个分词（关键字）附加权重，以设定查询的偏好。

定义上，网页库中的各个文件和查询式都将用向量来表示，每个向量中向量项的顺序与倒排索引中关键字出现的顺序相同。对于文件：

Dj = <dj1, dj2, …, dji, …, djn>

向量 Dj表示编号为j的网页文件的特性向量。其中，向量项dji表示关键字i在文件j中的TFIDF权重，其计算过程如下：

1)        计算关键字i在文件j中出现的次数，记为TFji

2)        计算包含关键字i的文件的个数，记为DFi

3)        计算关键字i的反文档频率IDFi = log (M/ DFi)，其中M为文件总数

4)        计算dji = TFIDFji = TFji * DFi

对于查询式：

Q = <q1, q2, …, qi, …, qn>

按照倒排索引中关键字的顺序逐个比较查询式中的中文分词。对于索引中第i个关键字，若它出现中查询式中，则qi = 1；否则qi = 0。另外，也可以手动给查询式中特定词项赋予权重，以达到设定偏好的目的。

向量空间 D = < D1, D2, …, Dm>与查询式向量 Q计算完毕后，即可进行相似度计算。若采用的是余弦相似度，则需逐一扫描向量空间中的每一个向量，计算它与 Q的夹角，公式如下：

将计算所得的余弦值进行排序，即可得到相关性排序的结果。

3.   网络爬虫（深度优先策略）

网络爬虫是Web信息的采集器，它通过网页之间的链接关系从网络中自动下载网页数据，并且跟随网页中的链接不断向所需要的网页扩展。不同类型的信息检索系统因为其对资源性质的要求而有不同的技术需求。

爬取网页的一般过程如下：

1)        从一个URL种子集合开始搜索，将其全部存入某一集合数据结构之中；

2)        从该数据结构中取出一个URL，建立网络连接；

3)        远程读取网页数据并转存到本地；

4)        解析网页，提取出其中包含的URL，将其存入数据结构中；

5)        若数据结构中仍有URL或者下载的网页数量未达到下载上限，则返回2)，否则结束爬取。

在爬取过程中，需要注意如下几个问题：

一、    采用深度优先搜索策略进行爬取时，存取URL的数据结构选用栈；

二、    为了避免网页重复，在爬虫中需要维护一个哈希表，用来保存已经访问过的URL；当2)取出URL之后，将其与哈希表比对，判断哈希表中是否存在该URL，若存在则直接跳到5)，而不再对该网页进行下载；

三、    出于对中文编码格式不统一的考虑，读取网页和保存网页的过程一律采用字节流，而不采用字符流；解析网页的步骤同时析取出网页的编码方式，并加以保存；

四、    爬取规模较小，可以不采用多线程；如需采用多线程，则需要对URL栈添加同步锁以保证线程安全。

4.   中文内容提取

大部分网页中除了包含它的主要有用信息以外，还包含了许多噪声信息，例如导航、无用链接、广告等。另外，由于网络爬虫中并未对病态网页进行处理，因此有些网页中可能只包含一些脚本数据，而并没有正文信息。在这种情况下，在建立索引之前，还需要从给定的网页文件中抽取出有用的中文正文信息。这也是爬虫将网页保存到本地的目的。

若网页的格式相对较为单一，则可采用简单的文字加标签技术进行分析。其基本算法思想为：通过<div>或<table>标签切分内容块，通过中文标点符号（，。！）发现正文，通过链接数在正文中占的比例判断是否是噪声。

对任一网页进行中文内容提取的一般步骤如下：

1)        去除部分噪声：通过遍历网页，去掉特定的无用标签及标签中的内容，如<select>、<img>、<script>、<span>等；

2)        提取最内层的<div>或<table>块，建立内容块序列；

3)        逐一扫描内容块，每个内容块的正文权值 = (标点符号数 – 0.3 * 链接数) / (1 + 0.2 * n)，其中n表示该内容块中包含的<form>和<input>标签数量；

4)        扫描完成后，选取正文权值最大的内容块，抽取出其中的纯文本；

5)        比较纯文本的长度，短于设定值（假定为20个字）的将判断为病态页面，予以舍弃。

5.   指纹去重

完成正文提取的文本数据在保存为缓存文件以便建立倒排索引之前，需要进行网页去重。原因是网络中可能出现多个域名对应同一个网站或者网站间的互相转载。去重的目的是尽量使建立索引的文本库中的各个文本文件彼此独立，相互不同，提高搜索的有效性。

内容相同的网页主要分为三种情况：

1)        网页正文完全相同；

2)        网页正文大部分相同，只有少量变动；

3)        一个网页的正文是另一个网页正文的一部分。

对于简单的垂直搜索引擎，可只针对第一种情况进行分析，则只需采用计算正文MD5指纹的方式判断网页正文是否已经存在。其一般步骤如下：

1)        在中文内容提取中维护一个哈希表，用于保存正文的MD5指纹；

2)        对于提取完成的一段正文，将其作为字符串，计算其MD5值；

3)        判断该MD5是否已存在于哈希表中，若存在，则舍弃正文，反之则将其MD5值存入哈希表中。