精华内容
下载资源
问答
  • 反向索引

    2017-06-26 15:35:53
    倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构 ...

    概念介绍

    倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构

    例子

    描述

    相关理解

    一、 正向索引和反向索引的区别。
    1.正向索引 从索引文档找到关键词
    2.反向索引 根据关键字来找到文档

    展开全文
  • 目录 正向索引:从文档到单词。 反向索引:从词到文档。...在谈论搜索引擎的索引时,会涉及到两个概念正向索引(forward index)和反向索引(inverted index)。</p> 听上去,它们...

    在谈论搜索引擎的索引时,会涉及到两个概念正向索引(forward index)和反向索引(inverted index)。

    听上去,它们像是一种全新数据结构。让我们看看维基百科的解释。

    正向索引:从文档到单词。

    假如有三个 txt 文档,

    • Document_1: The cow says moo.
    • Document_2: The cat and the hat.
    • Document_3: The dish ran away with the spoon.

    解析每个文档出现的单词,然后建立从文档 (document) 到词组 (words) 的映射关系,这就是正向索引。

    Document Words
    Document_1 the,cow,says,moo
    Document_2 the,cat,and,the,hat
    Document_3 the,dish,ran,away,with,the,spoon

    反向索引:从词到文档。

    反向索引方向则是正向索引的逆向,建立从单词 (word) 到文档(document lsit) 的映射关系。

    Word Documents
    the Document_1, Document_3, Document_4, Document_5, Document_7
    cow Document_2, Document_3, Document_4
    says Document_5
    moo Document_6

    怎么看这都不是什么全新的数据结构啊?

    现实世界中的索引

    使用 index 快速检索信息并不是21世纪新的发明。

    1876年,杜威发明图书分类法(Dewey Decimal Classification)。我们通过这个方法,给图书建立索引,按书架快速查找(get)和摆放(set)书籍。

    分类 图书
    哲学与心理学 《苏菲的世界》,《理想国》
    宗教 《圣经》,《古兰经》
    社会科学 《宏观经济学》,《微观经济学》
    ... ...

    通常书籍最后的章节会罗列所有涉及到的行业术语,你可以通过这个列表查看哪一页交代了这些术语,并快速跳转到定义的地方,这也是一种索引 word -> page

    问题

    index 从来都不是一个新发明,从19世纪的图书分类法,到21世纪的数据库索引,我们一直在用。而且当大家提起索引这个术语时,脑海中都是按 word -> document 方向来建立。

    反向索引,其实就是普通的索引嘛。

    为什么有人仍然坚持创建出一个新的术语 inverted index ?

    此外 forward index 在现实世界中根本毫无用处,压根不能称之为索引,为什么要造这个词?

    无论是 Stack Overflow 还是 ElasticSearch 的官方文档也只是一而再,再而三的强调「是什么」,并没有回答「为什么」[1]。

    最终 Stack Overflow 一个不起眼的回答道出了玄机。[2]

    索引(index) 是个很老的概念。但是搜索引擎横空出世之后,却把这个概念包装了一下,称之为「反向索引」。并不是有什么本质性的区别,乃是因为搜索引擎在创建会先解析文档的关键词,创建一个正向索引,然后再基于正向索引,把方向逆转过来,创建反向索引,仅此而已。

    This should be the accepted answer as it answers the question why we call an index "inverted" even if it is just what everybody thinks of a "normal index". A SQL b-tree index stores for each word a pointer to all rows ("documents") containing it. There we call it "index". But in search engines we suddenly call this exact same procedure "inverted index". Not because it's fundamentally different, but because we first created a "forward index" (split text) and then "inverse" it. So, all in all, the name "inverse" comes from the process of creating it, not from the final structure of the index.

    搜索引擎如何创建索引?

    如果要进一步理解正向索引,需要了结搜索引擎 analyzer 的基本工作步骤。所有的文档在建立索引之前都要经过一个 pipeline。

    1. character filter,过滤一些词,比如 html 标签。
    2. tokenization。分词,转换时态,转换单复数等。
    3. token filter。过滤一些token,比如 the,a,an,this,these 等停用词。

    最终 pipeline 的输出就是一个单词列表。我猜测这个单词列表就用来创建正向索引。

    结论

    说到底,反向索引就是生活中处处可见的普通索引。

    反向索引之所以在搜索引擎中中被冠以新词,是因为在它之前要先创建正向索引。

    Reference

    1. Elasticsearch: Inverted Index

    2. Stack Overflow 的这个回答 没有被选为最佳答案,真是可惜。

    原文链接

    http://mednoter.com/inverted-index.html

    展开全文
  • 倒排索引也叫做反向索引(inverted单词也有反转的意思,只不过大家喜欢翻译成倒排索引)。倒排索引在搜索引擎中经常用到,倒排索引也叫做反向索引。某天在想,为什么叫做倒排索引呢?倒过来的,反转过来的。那么,非倒...

    倒排索引也叫做反向索引(inverted单词也有反转的意思,只不过大家喜欢翻译成倒排索引)。

    倒排索引在搜索引擎中经常用到,倒排索引也叫做反向索引。某天在想,为什么叫做倒排索引呢?倒过来的,反转过来的。那么,非倒排索引是什么样子的。解释一大堆。云里雾里。

    后来知道,反向索引是相对正向索引而言的,那什么是正向索引?我想,了解了正向索引,就能知道反向索引的产生背景了。

    下面是网上一些资料说法:

    每个文件都对应一个文件ID,文件内容被表示为一串关键词的*。实际上在搜索引擎索引库中,关键词也已经转换为关键词ID。这样的数据结构就称为正向索引。

    倒排索引正向索引还不能直接用于排名。假设用户搜索关键词2,如果只存在正向索引的话,排名程序需要扫描所有索引库中的文件,找出包含关键词2 的文件(索引文件),再进行相关性计算。这样的计算量无法满足实时返回排名结果的要求。所以搜索引擎会将正向索引数据库重新构造为倒排索引,把文件对应到关键词的映射转换为关键词到文件的映射,每个关键词都对应着一系列文件,这些文件中都出现了这个关键词。

    搜索引擎工作原理之预处理

    预处理总共分为几个步骤:1.提取文字、2.中文分词、3.去停止词、4.消除噪声、5.去重、6.正向索引、7.倒排索引、8.链接关系计算、9.特殊文件处理

    上面说法感觉不是很明白。现在整理一下自己的理解

    为每篇文档生成一个关键词集合,也就是提取这篇文档中的所有关词

    比如文档1

    经过分词,提取文档1中出现的关键词有20个

    这个20个关键词集合起来,每个关键词都会顺便记录它出现在文档的位置,出现的次数等信息

    正向索引的结构像下面这样子的:

    文档编号1  此文档中出现的关键词列表(单词1,出现位置,出现次数;单词2,出现位置,出现次数………..)

    文档编号2  此文档中出现的关键词列表

    这是正向索引。

    如果要搜索关键词”单词1”,则去正向索引可以直接查出来哪些文档包含了单词1。正向索引还是需要遍历扫描(扫描所有正向索引文件才知道哪些文档带有某个关键词),性能比较慢。

    顿时明白了某个资料中提到这句话:实际上,时间、内存、处理器等等资源的限制,技术上正向索引是不能实现的。

    跟正向索引相比,反向索引就是反过来。怎么个反过来法呢?

    左边是关键词,右边是文档编号,如下:

    关键词1   带有此关键词的文档编号1,文档编号2….

    关键词2   带有此关键词的文档编号1,文档编号2….

    很多介绍太学术化了,即便是做技术开发的,没有实际应用过,一时难以理解。

    展开全文
  • 背景业务操作的场景有很多需要数据进行模糊查询,这个时候就会用到关键字"like",虽然这样对用查询东西比较方便,但是随着数据量的增加,这样的语句越来愈慢。...优化思路反向索引like 的字段建立...

    背景

    业务操作的场景有很多需要数据进行模糊查询,这个时候就会用到关键字"like",虽然这样对用查询东西比较方便,但是随着数据量的增加,这样的语句越来愈慢。

    SELECT

    *

    FROM

    table_A A

    inner join table_B B f on A.ID = B.ID

    WHERE

    A.NAME LIKE '%s%'

    ORDER BY

    A.ID DESC

    LIMIT 10;

    优化思路

    反向索引

    like 的字段建立索引,但是由于前面加了%索引会失效。这个时候可以通过空间换时间的方式。把原来的like前面的%去掉,新增一个字段,存储NAME字段的方向数据,并且对新增的字段也加索引。例如原来的字段里面存的是“abcd”,那新增的字段就是存“dcba”的数据,这个时候语句变成如下:

    SELECT

    *

    FROM

    table_A A

    inner join table_B B f on A.ID = B.ID

    WHERE

    A.NAME LIKE 's%'

    or A.RES_NAME LIKE CONCAT(REVERSE('s'),'%')

    ORDER BY

    A.ID DESC

    LIMIT 10;

    新增的字段需要对要查找的值进行反转,这样的话,该语句可以达到前面的语句的功能,而且两个字段的索引都有效

    合并索引

    虽然上面的like的字段都可以用上索引了,但是因为用了or并且进行排序,性能没有得到多大的提升,通过分析是因为需要进行排序导致查询比较慢,但是排序是业务需要,没有办法去掉。通过修改为下面的语句:

    SELECT

    *

    FROM

    table_A A

    left join table_B B f on A.ID = B.ID

    WHERE

    A.NAME LIKE 's%'

    or A.RES_NAME LIKE CONCAT(REVERSE('s'),'%')

    ORDER BY

    A.ID DESC

    LIMIT 10;

    通过把inner join 改为left join后,对语句进行解释,发现extra字段出现“Using sort_union”,修改前该字段现实“Using where”。对于修改后的最终版本进行测试,原来的语句执行需要1.00s,优化后0.00s。

    展开全文
  • lintcode 反向索引

    2019-03-29 10:44:46
    lintcode 反向索引描述样例思路代码 描述 创建给定文档的反向索引 确保数据不包含标点符号. 样例 出一个包括id与内容的文档list(我们提供了document类). 返回一个反向索引(hashmap的key是单词, value是文档的id). 例...
  • oracle反向索引

    2018-03-20 17:14:49
    oracle反向索引 2013-05-07 13:52:20 0个评论  收藏 我要投稿 oracle反向索引   如 create index idx_rev on tiger.test(test_name) reverse;    把索引表空间存放在能够把...
  • 反向索引 1.1 反向索引的定义 反向索引作为B-tree索引的一个分支,主要是在创建索引时,针对索引列的索引键值进行字节反转,进而实现分散存放到不同叶子节点块的目的。 1.2 反向索引针对的问题 使用...
  • 关键词:索引、倒排索引(反向索引) (1)为什么要用索引 索引的建立,能使查找更加快速 (2)索引的数据结构 数组: 方便查找,但是数据更新太慢 链表:方便更新,但是查找太慢(从头到尾,或者从尾到头)...
  • Lucene系列二:反向索引及索引原理

    千次阅读 2018-10-14 23:15:43
    了解关系型数据库的童靴都了解它底层结构采用b+tree的实现,而Lucene则是基于反向索引实现,并将它发挥到了极致。如果不了解Lucene是什么,可以参阅《系列一之全文检索》 目录 1. 什么是反向索引 2. 如何设计反向...
  • Python与索引我一直在研究一个普通的Python代码来将数据从csv中分离出来。我的目标是使用多种策略重新创建这段代码,以便更好地理解Python。稍后将对该代码进行改进。我的代码是有效的,但有一些事情我不明白。这里...
  • 反向索引 1.1 反向索引的定义 反向索引作为B-tree索引的一个分支,主要是在创建索引时,针对索引列的索引键值进行字节反转,进而实现分散存放到不同叶子节点块的目的。 1.2 反向索引针对的问题 使用...
  • Mapreduce 反向索引

    2015-06-01 10:25:00
    反向索引主要用于全文搜索,就是形成一个word url这样的结构 file1: MapReduce is simple file2: MapReduce is powerful is simple file3: Hello MapReduce bye MapReduce 那么经过反向索引后就是: Hello ...
  • 反键索引又叫反向索引,不是用来加速数据访问的,而是为了均衡IO,解决热块而设计的比如数据这样: 1000001 1000002 1000005 1000006 在普通索引中会出现在一个叶子上,如果部门数据需求极大,也就是热块,多个需求之间...
  • 关于正向索引与反向索引

    千次阅读 2017-02-27 16:23:26
    前面我们说过索引包含正向索引和反向索引两部分,首先我们看看正向索引的结构。 正向索引用来存储文档的各种属性,从逻辑上讲,正向索引其实就是一个大数组,数组中每个元素就是一个文档的属性集合。 ...
  • 什么是反向索引

    千次阅读 2018-11-04 15:38:12
    反向索引英文名叫做Inverted index, 顾名思义, 是通常意义下索引的倒置。 举个例子:我们用不同的数字索引不同的句子(比如以下三句在文本中是按照0,1,2的顺序排列的) 0 : “I love you” 1 :“I love you ...
  • 好吧,长话短说,问题是:我在做反向索引。我在网上找到了一些教程和提示,我做了以下几点:类文档,用于词干的词干,并使用词干的起始位置和结束位置返回单词。类的反向索引,它获取文档的集合(列表中的列表),将...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,607
精华内容 1,042
关键字:

反向索引