文档章节

信息检索中,索引的本质

翟志军
 翟志军
发布于 2015/06/09 06:55
字数 2020
阅读 4027
收藏 95

如有不正确的或者理解不到位的地方,欢迎斧正。

信息检索问题

首先我们来看问题域。每一种技术产物都是为解决某类问题。不从问题域出发,我们就很难理解为什么它是这样的。就像那些没学过“程序语言”设计的人,只能被程序语言牵着走。

信息检索背后的模型其实很简单:就是从大量的信息中找出需要的信息。这类问题有个更专业的名字:信息检索(Information Retrieval)。生活中,这样的问题数不胜数:

  • 我们怎么能快速地找出某个单词在书中第几页呢?

  • 如果没有搜索引擎和目录,在大型图书馆如何找到我们要的书?

  • 找房人通过浏览每一份房产信息来找到自己期望的房子,这样的效率是不是有些低?

  • 怎么方便地找出附近所有的中餐厅呢?



解决信息检索问题


上面只是介绍信息检索的背后最简单的一面。它的背后存在更复杂的问题。


想象一下你需要在以下一串数字中找最大的那个数字:

     1, 23, 56 , 3, 40, 41.1, 900, 12 

这很简单,你一眼看过去就可以得出答案,但如果存在100亿个数字呢?假如一个人一秒能辨认出10个数中最大的数字,那么他365x24小时不停地看,也要31.6887646 年才能得到答案


这样无聊而且不人道的事情,我们交给机器做。这引出我们信息检索的第一个问题:信息量太大了,以至于我们人在有限的时间找不到我们真正想要的,需要机器来帮助我们。


可是,机器怎么知道我们要找什么样的东西呢?这时,引出我们信息检索的第二个问题:如何让机器理解我们要找什么样的东西呢?答案很简单:我们人告诉它不就可以。这个思路是正确的,在我看来。沿着这个思路去实现时,我想我们大概会遇到如下问题:

     1. 我们人类如何表达“我们要找啥”这个问题?

         我们通常的做法是给出我们要找的信息的一部分特征。在搜索领域中,这“一部分特征”的术语称为关键字。事实上,“关键字”就是我们大脑中要找的信息的“特征”。

     2. 如何让机器理解“我们要找啥”这个问题?

          这个问题就很复杂了。当我们在谷歌里搜索“IR”时,它怎么知道我要搜索是“Information Retrieval”,还是“Ingersoll Rand”?

     3. 机器怎么知道哪些信息就是我们要找的?

          

本文重点是要回答第3个问题。虽然本质上,这3个问题应该放在一起讨论。



索引的本质

面对“机器怎么知道哪些信息是我们要找的”这个问题,我所见到的解决域模型是:告诉机器如何抽取(或逐个地)信息的特征(索引),然后机器拿这些“索引”与搜索者大脑中信息的特征(关键字)对比,就可以知道哪些信息是用户想找的了。


这里,我们就已经得出了索引的本质:信息的特征


回到一开始举的例子:

  • 字典的都会有按字母顺序排的目录和按笔画排的目录,字母和笔画是字的特征,所以,可以拿它来做索引

  • 图书馆中每一本书都会有一个编号,编号可由有意义的字母表示,比如T2300004可代表科技类2楼3排等等。我们可以很容易的根据这个编号找出这本书。这里给我们一个提示,当被搜索的信息的自有特征不明显时,我们可以人工为其加上。比如一部电影,我们可以人工的为其加上标签如动作片、简爱,以便搜索。因为有些人不一定只根据电影名搜索,他还可能搜索“爱情片”

  • 附近的餐厅的特征可以有:地理坐标、是否好吃、价格是否优惠等。


既然索引就是信息的特征,那么我们如何组织索引才能方便我们使用索引呢?目前有两种方式组织索引:

  • 信息后关联一批特征

  • 每一种特征后关联一批信息


正向索引:信息后关联一批特征

以我的经验,先讲正向索引,比先讲反向索引能让读者更好的理解索引的本质。

其实正向索引的结构很简单:


反向索引:每一种特征后关联一批信息

在信息检索领域,反向索引实际上称为:Inverted index。国内经常翻译成倒排索引。和大多数人一样,一开始对这个名词一头雾水。所以,我更喜欢将它翻译成反向索引。之所以称为inverted,应该就是因为正向的存在吧。

然而,解决域模型决定了我们会使用反向索引结构,而不会使用正向的。也许这就是为了什么大多信息检索类的书籍对正向索引只字不提。


实现反向索引

不论实现正向还是反向的索引,都需要从信息抽取出其特征。不同类型的信息表现出来的特征不同。

对于文本信息,我们认为“一个词的重要性取决于它在文档中出现的频率”(Luhn于1958年提出)。也就是说你在查询时,查询词在文档中出现的频率,决定文档的重要性。

基于这一点,实现对文本信息的特征抽取,我们似乎只需要简单的将文本所有的词都作为索引项(术语称为term)就好了。但实际情况并没有这么简单。这个过程称为分词(tokenizing)。只是这个处理过程,不同的人或框架又分为几个环节。

我们可以理解它是这样一个过程,比如存在两份信息:

1. The quick brown fox jumped over the lazy dog

2. Quick brown foxes leap over lazy dogs in summer

使用分词器处理后得到的结果是:

当我们搜索“quick brown”时,会得到结果:

然而使用不同的分词器,会得到不同的索引,最终影响到搜索结果。仔细的同学就会看出上面的反向索引有什么地方不对了。所以,建立索引时,一定要选择合适的分词器。

本小节的例子来自《Elasticsearch: The Definitive Guide》

小结

我们从了解问题域开始,一步步推导出索引的本质——信息的特征。有了这样的认识,我们就可以很容易的理解为什么现在的搜索引擎是这样子的,而不至迷失在错综复杂知识迷宫中。

但是,对于信息检索,除了索引这种解决域模型,我们就没有别的出路了吗?这是一个值得思考的问题。

本文说是信息检索,实际上更准确的应该说是文本信息检索。对于图片检索和语音检索,我们无法用分词器进行处理了,那怎么办呢?不要忘了我们的解决域模型:告诉机器如何抽取(或逐个地)信息的特征(索引),然后机器拿这些“索引”与搜索者大脑中信息的特征(关键字)对比,就可以知道哪些信息是用户想找的了。对于图片检索和语音检索,我们要做的就是想办法从图片和语音中抽取出它们自有信息特征。



© 著作权归作者所有

共有 人打赏支持
翟志军

翟志军

粉丝 349
博文 76
码字总数 79851
作品 2
深圳
程序员
私信 提问
加载中

评论(12)

翟志军
翟志军

引用来自“魏曼奇”的评论

索引是对信息经过某种指定规则进行排列的特征组合。至少我是这么认为。单独的信息特征并不构成索引。所以索引的本质是信息特征的有向集合。
信息的特征的组合方式是另一个回事了。我认为信息的特征就是那样子了。组合成什么样子,要看你需要怎么用它们了。
魏曼奇
魏曼奇
索引是对信息经过某种指定规则进行排列的特征组合。至少我是这么认为。单独的信息特征并不构成索引。所以索引的本质是信息特征的有向集合。
x
xto
这只是讲了key-value索引,key-value索引是b-tree索引的特例。key-value索引不太适合范围检索。因此对于关系型数据库,大部分都是b-tree.
亚林瓜子
亚林瓜子
谢谢分享
TuWei
TuWei
还以为数据库索引…
买合苏提
买合苏提
对于索引的概念性入门,谢谢分享
翟志军
翟志军

引用来自“RisingV”的评论

题目起得有点大。“一一对比”这种词容易给人误解。其实很简单,如果我有一台超级量子计算机,我不介意将query和target一一比较一下,多么简单,两重循环就搞定。但是这样的机器不存在,在有限的cpu时钟,有限的RAM,有限的IO带宽下,我们只能空间换时间,通过预建合理的数据结构,来减少比较。
这个题目,我觉得不算大。原因是因为我认为的索引的本质我已经说到。只是细节部分,我们可以放在另一篇文章来讲。 而你说的“一一对比”问题。我说了,那是解决域模型,具体实现时是不是“一一对比”另说。如果我改成“对比”,也许就不会那么误解人了。
RisingV
RisingV
题目起得有点大。“一一对比”这种词容易给人误解。其实很简单,如果我有一台超级量子计算机,我不介意将query和target一一比较一下,多么简单,两重循环就搞定。但是这样的机器不存在,在有限的cpu时钟,有限的RAM,有限的IO带宽下,我们只能空间换时间,通过预建合理的数据结构,来减少比较。
LC
LC
好奇有些让用户自己加tag的产品, 有没有对用户乱加、错加、有意加tag的情况做后续筛选处理, 类似于反seo
封心
封心
未完待续吗?
mysql索引的要点分析

mysql的索引并不是很好总结,所以日常工作中大家应该多使用 explain 来优化自己的查询和索引,做到用最少的索引来配合最高效的查询语句完整业务需求,这里我总结一些平日里遇到的比较多变的索...

big_cat
2016/02/26
107
0
Lucene4.3开发之第九步之渡劫中期(九)

下图是一个典型的Lucene4.X的索引结构图: Lucene4.x之后的所有索引格式如下: 复合索引文件是指,除了段信息文件,锁文件,以及删除的文件外,其他的一些列索引文件压缩一个后缀名为cfs的文...

heroShane
2014/02/21
0
0
了解搜索引擎技术

百度、Google搜索引擎核心技术是怎么实现的 搜索引擎 搜索引擎(search engine)是指根据一定的策略、运用特定的计算机程序搜集互联网上的信息,在对信息进行组织和处理后,并将处理后的信息显...

长平狐
2013/01/06
134
0
初探Sql Server聚族和非聚族索引

聚族索引:聚族索引的顺序就是数据物理存储排列顺序 非聚族索引:索引顺序与数据物理存储排列顺序无关 一个表最多只有一个聚族索引 在sql server中,索引是通过二叉树来描述的,具体定义: ...

Rksi5
2014/03/10
0
0
全文检索:Apache Lucene框架入门实例

一 简介 Lucene属于Apache开源项目的一部分,是一个开源的全文检索引擎工具包,但它不是一个完整的全文检索引擎,而是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析...

pangfc
2018/06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
7
0
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
2
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
4
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
3
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部