信息检索中,索引的本质
信息检索中,索引的本质
翟志军 发表于2年前
信息检索中,索引的本质
  • 发表于 2年前
  • 阅读 3725
  • 收藏 95
  • 点赞 17
  • 评论 12

腾讯云实验室 1小时搭建人工智能应用,让技术更容易入门 免费体验 >>>   

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

信息检索问题

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

信息检索背后的模型其实很简单:就是从大量的信息中找出需要的信息。这类问题有个更专业的名字:信息检索(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》

小结

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

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

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



共有 人打赏支持
翟志军
粉丝 335
博文 75
码字总数 79851
作品 2
评论 (12)
阿波罗2080
VeryGood!
丁富贵
并没有什么卵用
封心
未完待续吗?
LC
好奇有些让用户自己加tag的产品, 有没有对用户乱加、错加、有意加tag的情况做后续筛选处理, 类似于反seo
RisingV
题目起得有点大。“一一对比”这种词容易给人误解。其实很简单,如果我有一台超级量子计算机,我不介意将query和target一一比较一下,多么简单,两重循环就搞定。但是这样的机器不存在,在有限的cpu时钟,有限的RAM,有限的IO带宽下,我们只能空间换时间,通过预建合理的数据结构,来减少比较。
翟志军

引用来自“RisingV”的评论

题目起得有点大。“一一对比”这种词容易给人误解。其实很简单,如果我有一台超级量子计算机,我不介意将query和target一一比较一下,多么简单,两重循环就搞定。但是这样的机器不存在,在有限的cpu时钟,有限的RAM,有限的IO带宽下,我们只能空间换时间,通过预建合理的数据结构,来减少比较。
这个题目,我觉得不算大。原因是因为我认为的索引的本质我已经说到。只是细节部分,我们可以放在另一篇文章来讲。 而你说的“一一对比”问题。我说了,那是解决域模型,具体实现时是不是“一一对比”另说。如果我改成“对比”,也许就不会那么误解人了。
买合苏提
对于索引的概念性入门,谢谢分享
TuWei
还以为数据库索引…
亚林瓜子
谢谢分享
xto
这只是讲了key-value索引,key-value索引是b-tree索引的特例。key-value索引不太适合范围检索。因此对于关系型数据库,大部分都是b-tree.
魏曼奇
索引是对信息经过某种指定规则进行排列的特征组合。至少我是这么认为。单独的信息特征并不构成索引。所以索引的本质是信息特征的有向集合。
翟志军

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

索引是对信息经过某种指定规则进行排列的特征组合。至少我是这么认为。单独的信息特征并不构成索引。所以索引的本质是信息特征的有向集合。
信息的特征的组合方式是另一个回事了。我认为信息的特征就是那样子了。组合成什么样子,要看你需要怎么用它们了。
×
翟志军
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: