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

标签: 简易 垂直 搜索引擎 | 发表时间:2013-05-05 22:42 | 作者:sadfishsc
出处:http://blog.csdn.net

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值存入哈希表中。

作者:sadfishsc 发表于2013-5-5 22:42:01 原文链接
阅读:47 评论:0 查看评论

相关 [简易 垂直 搜索引擎] 推荐:

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

- - CSDN博客架构设计推荐文章
倒排索引源于实际应用中需要根据属性值(字段)来查找记录(所在的文件位置). 这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址. 目前主流的索引技术有三种:倒排索引、后缀数组以及签名. 后缀数组虽然快,但是维护困难,代价高昂,不适合作为搜索引擎的索引. 而签名的速度和性能都不如倒排索引.

uSniff:BT种子搜索引擎

- leqoqo - 软件志
一、uSniff相关信息: 1、官方主页:http://www.usniff.com/ 2、简介:uSniff是一个BT种子搜索引擎,简单、易用、实时是其最大的优点,其搜索引擎数据库包含了17个知名种子站点的种子信息,目的是想发展成为世界上最大的BT种子搜索引擎,而且对于每个种子,该搜索引擎都会进行安全认证,以保证用户的正常使用.

人眼启发视觉搜索引擎

- feng823 - Solidot
Google上周宣布将支持声音和图片进行搜索,但一家创业公司在图像搜索方面走在了Google前面. 源自伦敦帝国学院研究项目的创业公司Cortexica,开发出视觉搜索工具,通过手机拍摄产品照片,它会自动呈现价格信息. Cortexica已经发布了一个用于比较酒价格的工具WINEfindr. Cortexica的视觉搜索技术是受到了人眼视觉系统的启发,它能识别出一个目标的关键特征,不受方位、大小、光线亮暗的影响.

比较好的学术搜索引擎

- hfut_chen - C++博客-首页原创精华区
     摘要: 1、http://scholar.google.com/. Google学术搜索滤掉了普通搜索结果中大量的垃圾信息,排列出文章的不同版本以及被其它文章的引用次数. 略显不足的是,它搜索出来的结果没有按照权威度(譬如影响因子、引用次数)依次排列,在中国搜索出来的,前几页可能大部分为中文的一些期刊的文章.

Blekko 对搜索引擎的新探索

- thinkingit - 知乎的博客
Blekko 这款搜索产品做的如何. 从目前我的使用过程来看,Blekko还是很让人激动的. 在谈Blekko之前就要先问:为何在搜索这个看似已经垄断的行业还会有人想去分一杯羹,这些小团队能与Google或微软这样的巨头抗衡吗. 比如之前的Powerset,后来的Cuil,和现在的Blekko. 在Google之前Yahoo是靠人工收录网页,Google的算法和蜘蛛革了搜索的命,一直垄断搜索业十余年,而现在随着WEB 2.0的发展,让人又看到了搜索业革命的火种,可以说Blekko就是这样的一个产品.

Mr.Icons:图标icon搜索引擎

- 壮壮爱 - 够趣堂
之前Anliu在如何更换更好的icon文章里面推荐了4个icon搜索引擎,目前部分已经不复存在. 不过Mr.Icons倒是又一个不错的选择,可以搜索图标icon进行下载,有PNG、ico格式以及不同大小提供下载. Mr.Icons还提供图标icon集打包下载,比如动物图标等. 和之前的介绍几款搜索引擎一样,依然不支持中文.

迅搜全文搜索引擎 XunSearch

- Le - 开源中国社区最新软件
迅搜(xunsearch)是采用 C/C++ 基于 xapian 和 scws 开发的全文搜索引擎解决方案,提供 PHP 语言的开发接口. 支持海量数据高速检索,功能强大,简单易用. 本项目旨在帮助一般开发者针对既有的海量数据,快速而方便地建立自己的全文搜索引擎. 全文检索可以帮助您降低服务器搜索负荷、极大程度的提高搜索速度和用户体验.

搜索引擎的特殊用法

- iVane - 崔凯,前端开发
下周组内分享要讨论“工具”,介绍几个搜索引擎的特殊用法,凑凑数:. 通配符,这么搜可以得到“崔凯前端开发”,也能得到“崔凯大连开发” 崔凯*开发. 用于搜索查询词出现在URL中的页面. 由于关键词出现在URL中对排名有一定影响,因此使用inurl:搜索也是定位竞争对手的一种方式. 该指令搜索结果返回的是页面title中包含关键词的页面.

美国购物搜索引擎评测

- - 月光博客
  专注于购物搜索引擎领域的CPCStrategy在其博客中对美国众多流行的购物搜索引擎在2012年第一季度的流量、收入以及转化率等方面进行了全面的分析与对比,其中的一些发现不管是对商家还是消费者都非常有价值. 我们对其进行了编译,希望对大家有帮助.   这项分析的数据样本主要来自CPCStrategy的100多位客户,涵盖约427万次点击,约8.3万张订单,约116万美金的营销成本以及所带来的约787万美金的收入.

如何高效使用搜索引擎

- - IT技术博客大学习
   把搜索词放在双引号中,代表完全匹配搜索,也就是说搜索结果返回的页面包含双引号中出现的所有的词,连顺序也必须完全匹配. bd和Google 都支持这个指令. 例如搜索: “javar高性能程序开发”.    减号代表搜索不包含减号后面的词的页面. 使用这个指令时减号前面必须是空格,减号后面没有空格,紧跟着需要排除的词.