文档章节

信息检索中,索引的本质

翟志军
 翟志军
发布于 2015/06/09 06:55
字数 2020
阅读 3918
收藏 95
点赞 17
评论 12

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

信息检索问题

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

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

小结

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

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

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



© 著作权归作者所有

共有 人打赏支持
翟志军

翟志军

粉丝 338
博文 75
码字总数 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 ⋅ 0

Lucene4.3开发之第九步之渡劫中期(九)

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

heroShane ⋅ 2014/02/21 ⋅ 0

lucene4.7 索引文件(九)

下图是一个典型的Lucene4.x的索引结构图: Lucene4.x之后的所有索引格式如下所示: 文件名 后缀 描述 Segments File segments.gen, segments_N 存储段文件的提交点信息 Lock File write.lock...

一枚Sir ⋅ 2014/04/11 ⋅ 1

了解搜索引擎技术

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

长平狐 ⋅ 2013/01/06 ⋅ 0

初探Sql Server聚族和非聚族索引

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

Rksi5 ⋅ 2014/03/10 ⋅ 0

全文检索:Apache Lucene框架入门实例

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

pangfc ⋅ 2016/12/07 ⋅ 0

MySQL聚簇索引&聚集索引&索引组织表

MySQL聚簇索引&聚集索引&索引组织表 http://www.cnblogs.com/hustcat/archive/2009/10/28/1591648.html 聚簇索引和聚集索引(Clustered Index) 说起索引,不能不说B+树。 引用:http://blog.c...

秋风醉了 ⋅ 2015/07/05 ⋅ 2

lucene全文检索概述 简介 整体知识

一,信息检索的过程简介 全文检索和数据库应用最大的不同在于:让最相关的头100条结果满足98%以上用户的需求 1,构建文本库 在开发功能前,一个信息检索系统需要做些准备工作,首先,必须要构...

晨曦之光 ⋅ 2012/04/11 ⋅ 0

Elasticsearch笔记(二)—索引及其构建

一、概述 Elasticsearch采用倒排索引机制,将文件“封装”为索引,将文本信息切分成称为Token的信息单元,再利用这些Token构造倒排索引。Elasticsearch的索引类似于数据库,而其中的类型类似...

j_hao104 ⋅ 2016/03/23 ⋅ 0

全文检索——Lucene

简单介绍: 全文检索是一种将文件中所有文本与检索项匹配的文字资料检索方法。全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件系统。 像我们平时用的百度谷歌搜索引擎,...

邵鸿鑫 ⋅ 2016/06/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

使用 vue-cli 搭建项目

vue-cli 是一个官方发布 vue.js 项目脚手架,使用 vue-cli 可以快速创建 vue 项目,GitHub地址是:https://github.com/vuejs/vue-cli 一、 安装 node.js 首先需要安装node环境,可以直接到中...

初学者的优化 ⋅ 24分钟前 ⋅ 0

设计模式 之 享元模式

设计模式 之 享元模式 定义 使用共享技术来有效地支持大量细粒度对象的复用 关键点:防止类多次创建,造成内存溢出; 使用享元模式来将内部状态与外部状态进行分离,在循环创建对象的环境下,...

GMarshal ⋅ 40分钟前 ⋅ 0

SpringBoot集成Druid的最简单的小示例

参考网页 https://blog.csdn.net/king_is_everyone/article/details/53098350 建立maven工程 Pom文件 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM......

karma123 ⋅ 今天 ⋅ 0

Java虚拟机基本结构的简单记忆

Java堆:一般是放置实例化的对象的地方,堆分新生代和老年代空间,不断未被回收的对象越老,被放入老年代空间。分配最大堆空间:-Xmx 分配初始堆空间:-Xms,分配新生代空间:-Xmn,新生代的大小一...

算法之名 ⋅ 今天 ⋅ 0

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 今天 ⋅ 8

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部