倒排索引

倒排索引

倒排索引

编辑

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排
索引文件,简称
倒排文件(inverted file)。

 
中文名

倒排索引

外文名

inverted index
构建方法

使用hash去重单词term

特殊要求

海量数据


概述

编辑

在关系数据库系统里,索引
[1]
  是检索数据最有效率的方式,。但对于搜索引擎,它并不能满足其特殊要求:

1)海量数据:搜索引擎面对的是海量数据,像Google,百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ,面对如此海量数据 ,使得数据库系统很难有效的管理。
2)数据操作简单:搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、 删、 改、 查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 ,搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。


相关概念及定义

编辑




倒排列表

倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词,每个文档会记录文档编号(DocID),单词在这个文档中出现的次数(TF)及单词在文档中哪些位置出现过等信息,这样与一个文档相关的信息被称做倒排索引项(Posting),包含这个单词的一系列倒排索引项形成了列表结构,这就是某个单词对应的倒排列表。右图是倒排列表的示意图,在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。

在实际的搜索引擎系统中,并不存储倒排索引项中的实际文档编号,而是代之以文档编号差值(D-Gap)。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值,一般在索引构建过程中,可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号,所以文档编号差值总是大于0的整数。如图2所示的例子中,原始的 3个文档编号分别是187、196和199,通过编号差值计算,在实际存储的时候就转化成了:187、9、3。

之所以要对文档编号进行差值计算,主要原因是为了更好地对数据进行压缩,原始文档编号一般都是大数值,通过差值计算,就有效地将大数值转换为了小数值,而这有助于增加数据的压缩率。



倒排索引

倒排索引
[2]
 
(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

  

倒排索引
倒排索引

倒排索引
[2]
  有两种不同的反向索引形式:

  一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。

  一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。

  后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。

  现代搜索引擎的索引
[3]
  都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构,
“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构.



构建方法

编辑




简单法

索引的构建
[4]
  相当于从正排表到倒排表的建立过程。当我们分析完网页时 ,得到的是以网页为主码的索引表。当索引建立完成后 ,应得到倒排表 ,具体流程如图所示:

流程描述如下:
1)将文档分析成单词term标记,
2)使用hash去重单词term

  3)对单词生成倒排列表

  倒排列表就是文档编号DocID,没有包含其他的信息(如词频,单词位置等),这就是简单的索引。

  这个简单索引功能可以用于小数据,例如索引几千个文档。然而它有两点限制:

  1)需要有足够的内存来存储倒排表,对于搜索引擎来说, 都是G级别数据,特别是当规模不断扩大时 ,我们根本不可能提供这么多的内存。

  2)算法是顺序执行,不便于并行处理。



合并法

归并法
[4]
  ,即每次将内存中数据写入磁盘时,包括词典在内的所有中间结果信息都被写入磁盘,这样内存所有内容都可以被清空,后续建立索引可以使用全部的定额内存。
归并索引
归并索引

如图 归并示意图:

合并流程:
1)页面分析,生成临时倒排数据索引A,B,当临时倒排数据索引A,B占满内存后,将内存索引A,B写入临时文件生成临时倒排文件,

  2) 对生成的多个临时倒排文件 ,执行多路归并 ,输出得到最终的倒排文件 ( inverted file)。
合并流程
合并流程

索引创建过程中的页面分析 ,特别是中文分词为主要时间开销。算法的第二步相对很快。这样创建算法的优化集中在中文分词效率上。



更新策略

编辑

更新策略有四种
[2]
  :完全重建、再合并策略、原地更新策略以及混合策略。
    1. 完全重建策略:当新增文档到达一定数量,将新增文档和原先的老文档整合,然后利用静态索引创建方法对所有文档重建索引,新索引建立完成后老索引会被遗弃。此法代价高,但是主流商业搜索引擎一般是采用此方式来维护索引的更新(这句话是书中原话)
    2. 再合并策略:当新增文档进入系统,解析文档,之后更新内存中维护的临时索引,文档中出现的每个单词,在其倒排表列表末尾追加倒排表列表项;一旦临时索引将指定内存消耗光,即进行一次索引合并,这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序,这样直接顺序扫描合并即可。其缺点是:因为要生成新的倒排索引文件,所以对老索引中的很多单词,尽管其在倒排列表并未发生任何变化,也需要将其从老索引中取出来并写入新索引中,这样对磁盘消耗是没必要的。
    3. 原地更新策略:试图改进再合并策略,在原地合并倒排表,这需要提前分配一定的空间给未来插入,如果提前分配的空间不够了需要迁移。实际显示,其索引更新的效率比再合并策略要低。
    4. 混合策略:出发点是能够结合不同索引更新策略的长处,将不同索引更新策略混合,以形成更高效的方法。
    5. https://baike.baidu.com/item/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95/11001569?fr=aladdin
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/113134.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • OC动态创建的问题变量数组.有数组,在阵列13要素,第一个数据包阵列,每3元素为一组,分成若干组,这些数据包的统一管理。最后,一个数组.(要动态地创建一个数组).两种方法

    OC动态创建的问题变量数组.有数组,在阵列13要素,第一个数据包阵列,每3元素为一组,分成若干组,这些数据包的统一管理。最后,一个数组.(要动态地创建一个数组).两种方法

    2022年1月12日
    36
  • 河南计算机职称考试模块选择,2016职称计算机考试模块Dreamweaver选择冲刺题1

    河南计算机职称考试模块选择,2016职称计算机考试模块Dreamweaver选择冲刺题1单选题1.网页的主体内容将写在什么标签内部:A.标签B.标签C.标签D.标签答案:A2.下面关于查看源代码说法正确的是:A.一般不能在IE中查看网页的源代码B.在DreamweaverMX中可以使用代码监视器(CodeInspector)查看的页面的源代码C.在DreamweaverMX中只有一种方法可以查看网页的源代码D.以上说法都错答案:B3.在Dreamweaver中,下面关于使…

    2022年6月2日
    35
  • Qemu kvm_qemu详细教程

    Qemu kvm_qemu详细教程重新创建vm修改虚拟机的xml文件virshshutdown原来的虚拟机virshundefine原来的虚拟机virshdefine新的xml文件,创建虚拟机virshstart虚拟机

    2022年8月11日
    4
  • 【Matlab】如何规范地编写一个MATLAB函数文件

    【Matlab】如何规范地编写一个MATLAB函数文件在matlab中,M文件分为脚本文件和函数文件。如果M文件的第一个可执行语句以function开头,那这个M文件就是函数文件。函数文件内定义的变量为局部变量,只在函数文件内部起作用,当函数文件执行完后,这些内部变量将被清除。本文介绍如何规范地编写一个函数文件。通常,函数文件由函数声明行、H1行、在线帮助文本区、编写和修改记录、函数主体等几个部分组成。格式如下:function输出形参…

    2022年7月17日
    10
  • 普通索引和唯一索引的区别b+tree_两个字段建立唯一索引

    普通索引和唯一索引的区别b+tree_两个字段建立唯一索引转自:https://blog.csdn.net/u014071328/article/details/78780683唯一索引和普通索引使用的结构都是B-tree,执行时间复杂度都是O(logn)。1、普通索引  普通索引(由关键字KEY或INDEX定义的索引)的唯一任务是加快对数据的访问速度。因此,应该只为那些最经常出现在查询条件(WHEREcolumn=)或排序条件(ORDER…

    2022年9月15日
    0
  • 凶残的挖矿脚本,奴役我数千机器!

    凶残的挖矿脚本,奴役我数千机器!本文转载自不正经程序员温馨提示:本文中出现的命令和脚本,不要在自家服务器上随便运行,除非你知道自己在做什么。挖矿是把机器当作奴隶,一刻不停歇的去计算、运转,本质上是个无用的工作。但可惜的是,它能赚钱。用别人的机器去赚钱,更是很多人梦寐以求的,所以挖矿脚本屡禁不止。有钱的地方,就有技术。但反过来并不一定成立。牢记这个准则,就能够心平气和的学习新技术,而不是气急败坏的纠结为啥没钱。1.脚本从哪来?下面是一个http的报文。GET/console/images/%2E%2E%2F

    2022年7月13日
    12

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号