文档章节

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

botkenni
 botkenni
发布于 2016/10/13 10:24
字数 1162
阅读 164
收藏 1

搜索引擎的原理其实很简单,写出来没两页纸,但是实现中的各种细节写成的论文可以堆满两个图书馆。

让我们先从原理说起。

首先需要用输入数据创建索引,对于互联网搜索引擎,输入数据是一个个由爬虫从网上抓回来的网页,经过清洗之后进行内容抽取,然后整理成统一的格式交给索引程序创建索引。
索引由以下几个基本的组成部分:
1. 倒排索引,这一部分存放"关键字"->文档的映射,一般来说会把同一个关键字对应的所有文档按照统一方法整理成一个排好序的线性结构,以便遍历和各种AND/OR之类的操作。
2. 正排索引,这一部分存放每个文档的各种属性
索引程序要干的事就是从源数据中拿出每个关键字和各种属性,整理成索引文件。文本变成关键字的过程叫做关键字提取,对于英语等语言,这个过程相对容易,一般就是进行大小写、全角/半角转换,拼写检查,字根提取等工作,例如源文本中的“goes”,“going”,“went”统一转换为“go”等;对于中文来说这个过程会比较麻烦,需要进行分词,常用的分词方法有单字切分、正/反向最大匹配、n元分词、隐马模型等。没有那一种单一的方法能满足所有需求,所以实际应用中一般会将多种方法结合使用。

索引创建好之后就可以搜索了,一个典型的搜索过程有这几个步骤:
1. 倒排索引的查询,一般称为“全文检索”,根据输入的关键字序列T1,T2..Tn,在倒排索引中找到对应的文档链,根据查询需求进行AND或者OR的组合,得到一个满足条件的结果集,对于典型的全文搜索引擎,这个阶段还需要计算每个文档的文本相关性以便排序,常用的文本相关性算法有TF-IDFBM25VSMLM等。
2. 正排索引过滤,在得到满足全文检索的文档集后,对每个文档检查其属性是否满足过滤条件,如果不满足则丢弃,剩下的就是最终的结果集。
3. 排序,全文搜索引擎一般的做法是:基于倒排索引查询得到的文本相关性,结合正排索引中的各种属性进行加权,例如给较新的文档加分等,最终得到一个分值,然后对结果集进行排序,保留前若干个结果返回给用户。

以上的过程就是全文搜索引擎的大致工作过程,其中复杂之处在于如何评估输入的查询条件和文档之间的匹配程度,文本相关性只能满足一部分需求,还需要其它一些因素来对文档得分进行调整,例如Google的PageRank就是通过进出的链接对文档重要性进行评估的一种方法。

垂直搜索引擎的基本工作原理和上述的一样,但是侧重点不同,一般来说垂直网站更重视文本之外的各种属性,例如电商网站会很关注商品的库存量和售价,如果排序结果将无库存或者过于昂贵的商品放在最前面会严重影响销售量;本地搜索网站会很关注POI和用户之间的距离,如果将一家距离用户很远的商户排在结果的前面同样也会造成很不好的体验。

另外还有一个很重要的问题就是索引的更新,对于互联网搜索引擎来说,一般会采用定期重建的策略,例如google就是每个几个小时将一个索引块整个重建,但是这种策略对于电商网站显然不行,例如在淘宝上可以进行拍卖,用户出价会导致拍卖价格迅速变化,需要在很短时间内迅速将这个价格的变化反映到搜索结果中,这就需要一些专门设计的索引结构来支持。

下一节我们将看看搜索引擎中的一些基本数据结构

© 著作权归作者所有

botkenni
粉丝 20
博文 409
码字总数 434882
作品 0
西城
程序员
私信 提问
Apache Nutch v1.7 发布,可插入式索引

Apache Nutch v1.7 修复了超过 20 个 bug,包括一些改进,最值得关注的就是新的可插入式索引机制。 Nutch 是一个开源Java 实现的搜索引擎。它提供了我们运行自己的搜索引擎所需的全部工具。包...

oschina
2013/06/25
2.2K
4
黑帽手法,且行且珍惜。

随着SEO的发展,很多人掌握了搜索引擎的抓取习惯,研究出来许多作弊的手法,甚至开发出了专门的作弊工具,这就是人们俗称的黑帽。当然,各大搜索引擎的工程师自然也都不是吃白饭的。顶尖的程...

成都辰星建站
2016/07/02
0
0
搜索引擎如何改变我们的大脑

Google 一开始只是做了一个微不足道的搜索引擎,然而经过多年发展,它现在已经成为了一个巨无霸。 Google 的触角伸向四面八方,它打造了一系列影响我们生活的产品——比如说 Gmail 、 Google...

oschina
2015/08/31
4.8K
18
什么是网络营销?

什么是网络营销随着网络的逐渐发展,现在买个东西都不需要出门什么都能买到,由于各个产品的生产,在很久以前人们都是靠着发传单来宣传自己的产品。但是随着现在网络的兴起,传单少之又少,而...

梦中想着她
2018/01/03
0
0
Apache Nutch 1.8 发布,Java 搜索引擎

Apache Nutch 1.8 发布,此版本包括 Crawler Commons 0.3 和 Apache Tika 1.4 的库更新;同时还包括 30 个 bug 修复和 18 处改进。更多内容请看更新日志,现已提供下载,建议每位 1.x 系列的...

oschina
2014/03/18
2.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

我为什么要写微信公众号

埋一颗种子,细心呵护,静待她枝繁叶茂,葱郁参天 V2论坛上有个帖子【做程序员最重要的还是一定要有自己的作品】,作者写道: 能有一个作品和你的名字联系在一起,应当成为在职业生涯前期着意...

运维咖啡吧
44分钟前
3
0
数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
5
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
6
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部