文档章节

实现自己的搜索引擎(二)

botkenni
 botkenni
发布于 2016/10/13 17:52
字数 1172
阅读 61
收藏 0

这一节我们来看看搜索引擎中最重要的几个数据结构。

前面我们说过索引包含正向索引和反向索引两部分,首先我们看看正向索引的结构。

正向索引用来存储文档的各种属性,从逻辑上讲,正向索引其实就是一个大数组,数组中每个元素就是一个文档的属性集合。
如果正向索引是有Schema的,那么它其实就类似一个关系表或者说二维数组,纵轴是文档,横轴是属性;如果正向索引是Schema Free的,那么它就类似一个Map的数组,每个文档都是一个Map,key是属性名,value是属性值。
文档在正向索引这个大数组中的下标也是有用的,在很多搜索引擎的实现中,这个下标被称为文档的逻辑ID,叫它ID是因为它唯一的标示了某个特定的文档,叫它“逻辑”是因这个ID只在这个索引中有意义,而且文档也许有自己的类似于ID的属性,要避免混淆。
创建正向索引的过程极其简单,只需要在这个大数组后面追加新的文档即可,每次追加一个文档就会给这个文档产生一个新的逻辑ID。
在搜索引擎中,一般不会从正向索引中删除任何文档,如果需要进行删除操作,则在每个文档中设立一个是否删除的标志,已删除的文档置1。

正向索引其实就这么点东西,下面我们来看看反向索引,这个稍微复杂点。

要实现关键字查询,就必须有一个可以用关键字找到文档的数据结构,所以反向索引逻辑上来说就是一个字典,key是关键字,value就是一个文档集。
在这里刚好用上我们之前在正向索引里产生的逻辑ID,因为逻辑ID唯一的标示一个文档,所以反向索引中的文档集就变成了一个逻辑ID的集合,实现中当然没这么简单,我们等下再说复杂的。
当然,如果仅仅使用这样一个结构,我们一次只能查询一个关键字,即便是作为一个玩具来说功能也太弱了点,下面我们来看看多关键字联合查询怎么做。
两个关键字的“联合”,最简单的有AND和OR两种关系,对于AND关系,我们需要将两个关键字对应的结果集取交集;对于OR则需要取并集;多个关键字只需照此办理即可。现在我们有一个实际的问题,那就是每个关键字对应的结果集可能超大,对它们求交集并集可能是一个昂贵的操作,昂贵到无法消受。
从前面说过的逻辑ID的产生规则可以知道,逻辑ID是由小到大顺序产生的,没有重复,利用这一点我们可以做一些有效的优化。
首先,由于文档是顺序进入正向索引的,所以逻辑ID在加入反向索引时保持升序,如果我们能保持这个顺序,反向索引中每个关键字对应的文档集就变成了一个有序的线性结构,AND和OR操作也就变成了两个有序ID链的交和并。
回顾一下学校中关于算法和数据结构的教材,如果我没记错的话应该有这样的作业题,我就不帮大家做作业了。

很多搜素引擎还支持过滤条件,例如日期、价格等,最简单的方法就是,拿到反向索引匹配的结果集后,对其中的每个文档,在正向索引中检查它们的属性是否满足过滤条件,如果满足则保留,否则丢弃,最后剩下来的就是即匹配了关键字又满足过滤条件的文档。

到目前为止,我们已经实现了一个最基本的全文搜索引擎,它可以支持多关键字的AND/OR查询,还可以支持过滤条件,从功能上来说基本相当于一个玩具版Lucene :D:D

从下一节开始,我们来说说如何把目前的这个“玩具”一步步变成一个功能比较完备的产品。

© 著作权归作者所有

botkenni
粉丝 20
博文 429
码字总数 444521
作品 0
西城
程序员
私信 提问
Nutch:从搜索引擎到网络爬虫---分享公开课

Nutch:从搜索引擎到网络爬虫—分享公开课 开源力量公开课,每周二晚线上线下同时开课,让我们一起向IT技术大牛们学习! 课程题目: 开源力量公开课第三十一期- Nutch:从搜索引擎到网络爬虫 ...

liuhua0312
2013/09/13
232
4
Nutch:从搜索引擎到网络爬虫

开源力量公开课第三十一期- Nutch:从搜索引擎到网络爬虫 开源力量公开课,每周二晚线上线下同时开课,让我们一起向IT技术大牛们学习! 课程题目: 开源力量公开课第三十一期- Nutch:从搜索引...

liuhua0312
2013/09/10
1K
1
Nutch:从搜索引擎到网络爬虫--开源力量公开课第三十一期

开源力量公开课第三十一期- Nutch:从搜索引擎到网络爬虫 开源力量公开课,每周二晚线上线下同时开课,让我们一起向IT技术大牛们学习! 课程题目: 开源力量公开课第三十一期- Nutch:从搜索引...

liuhua0312
2013/09/10
503
5
使用jQuery整合Google搜索API到站内搜索

作者:Terry li - GBin1.com 网站搜索经常是web开发者需要处理的功能之一,很多网站都放弃自己开发搜索引擎,一是因为需要开发周期,二是因为耗费自己站点服务器资源,所以大家最常用的方式是...

gbin1
2011/07/19
130
0
Maven下 urlrewrite 地址重写

环境: 使用Url重写能给你网站带来哪些好处呢? 第一:有利于搜索引擎的抓取,因为现在大部分的搜索引擎对动态页面的抓取还比较弱,它们更喜欢抓取一些静态的页面。而我们现在的页面大部分的...

Leons
2015/08/10
705
0

没有更多内容

加载失败,请刷新页面

加载更多

parseint和isNaN用法

本文转载于:专业的前端网站➭parseint和isNaN用法 <!doctype html><html><head><meta charset="utf-8"><title>无标题文档</title></head><body><script> var a='12'; alert......

前端老手
42分钟前
7
0
Kylin 精确去重在用户行为分析中的妙用

作者:史少锋,Apache Kylin committer & PMC,2019/10/11 在上次文章《如何在 1 秒内做到大数据精准去重》中,我们介绍了 Apache Kylin 为什么要支持大数据集上的精确去重,以及基于 Bitmap...

ApacheKylin
53分钟前
5
0
学习记录(二) es6基本语法(rest参数,模板化,axios模块,拦截器)

日常学习记录 模块化:把一个大文件分成多个小文件,按照一定规范进行拼接 es5写法: 导出:module.exports = 数据 导入:require("路径") /路径未添加后缀名时 //默认添加.js //把路径作为文件名...

Pole丶逐
57分钟前
4
0
以程序员的角度怎么购买一台「性价比高的电视」

前俩天有小伙伴在我的文章下留言,说能否把 【国内电视机都介绍一下】,今天我已在TV端开发多年的程序员的角度。谈谈已程序员的角度如何购买一台性价比高的电视。 国内大的电视机品牌介绍 长...

我们都很努力着
今天
4
0
PhotoShop 色调:理解直方图/RGB通道信息

一、直方图:图表的形式,展示图像像素分布的情况 1.平均值:表示平均亮度 2.标准偏差值:表示亮度值范围内的中间值 3.像素: 表示用于计算直方图的像素总数 4.色阶:显示指针下面的区域亮度...

东方墨天
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部