精华内容
下载资源
问答
  • 倒排表是什么
    2020-05-05 17:36:47

    问答系统的回顾

    在这里插入图片描述
    图中右侧是一个知识库,知识库需要包含两方面信息,每个数据需要包含每个问题和问题对应的答案。

    假设用户问了一句话:How do you like NLPCamp?这句话经过一系列的文本预处理之后,需要和知识库的每个问题进行匹配,计算用户输入与每个问题的相似度,返回相似度最高的问题对应的答案。

    这种方法有一个弊端,当知识库数据量太大时,需要计算N次相似度,对于用户的每个问题,都要和知识库的所有问题进行匹配,再返回相似度最高的。

    为了避免计算知识库中的所有数据,我们使用倒排表来解决该问题。

    倒排表

    倒排表的核心思路是要知道某一个单词出现在哪一个文档中。

    现在有一个知识库和词典库,词典库有所有出现的词,例如词典库是【我们,今天,运动,昨天,上,课】。

    对于下面四个文档:

    • doc1:我们今天运动;
    • doc2:我们昨天运动;
    • doc3:你们上课;
    • doc4:你们上什么课;

    对于词典中的每个词,【我们】出现在文档【doc1,doc2】,【今天】出现在【doc1】,以此类推,这样就形成了一个倒排表。

    当形成一个倒排表,当用户输入运动,需要返回一些和运动相关的文档,这时候我们可以直接查询出现【我们】的文档,也就是【doc1,doc2】,这样就不用遍历整个知识库。

    当用户输入【我们上班】,如果没有倒排表,需要将用户输入与整个知识库进行匹配,这样会耗费大量的时间。如果有了倒排表,可以直接查询与【我们】,【上】,【班】相关的文档。根据倒排表返回的文档和用户输入计算相似度,返回相似度最高的文档。

    当用户输入【How do you like NLPCamp】,可以先选择至少包含输入句子中一个单词的所有文档,这是一次过滤。

    更多相关内容
  • 倒排表讲解

    千次阅读 2021-12-02 17:19:10
    目录前言一、倒排表总结 前言 倒排表可以用来做过滤的相关操作。 一、倒排表 示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。 总结 提示:


    前言

    在问答系统中,我们应该根据用户提出的问题,然后在知识库里找相关的问题以及返回概率最高的答案,我们遇到的问题是假设知识库里有n个问题,那么我们每次需要做n次的相似度计算,这样的话对计算机的负担是极大的,那么如何降低复杂度呢?核心思路是根据倒排表做一个层次过滤,过滤掉不相关的问题以及答案。

    一、倒排表

    1-1、基本概念

    文档:比如Word、PDF、Excell等不同格式的文件都可以称之为文档。
    文档集合:由若干文档构成的集合称之为文档集合。
    文档编号:每个文档都会被赋予一个唯一的编号当作标识。
    单词编号:与文档编号类似,作为单词的唯一表征。
    倒排索引:实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:单词词典和倒排文件。
    单词词典:文档集合中出现的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
    倒排列表:记载了出现过某个单词的所有文档的文档列表以及单词在该文档中出现的位置信息,每条记录成为一个倒排项。根据倒排列表,即可以获知哪些文档包含某个单词。
    倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

    1-2、简单应用

    假设包含三个文档,对这三个文档建立倒排索引。
    在这里插入图片描述
    先对中文进行分词,然后再赋予每个单词唯一的编号,在倒排列表中记录下了哪些文档包含这个单词。除了记录哪些文档包含这个单词,还可以记录词频等信息。
    在这里插入图片描述

    参考文章:
    一文了解倒排表.
    NLP——倒排表.


    总结

    不知不觉就到12月了,今年可过的真快。

    展开全文
  • 一文了解倒排表

    千次阅读 2020-09-15 08:43:49
    倒排表 到排表是搜索引擎的核心架构 假设我们爬取了4个文档,里面的内容如下 基于4个文档,写出我们的词库 [我们,今天,运动,昨天,上,课,什么] 统计词库中的每个单词出现在哪些文档中,显然 我们 出现在[doc1,...

    1.前言

    我们先回顾最简单的问答系统:就是给定一个问题,去语料库中匹配相似度最高的问题所对应的答案
    语料库每个样本是:< 问题,答案 >
    在这里插入图片描述
    缺点: 假如我们语料库有 N 个 < 问题,答案> 对,那么,对于每个用户提出的问题,我们需要 计算 N 次相似度,才能返回最高相似度的。
    所以他的复杂度为:O(N)* (每次相似度计算的复杂度)

    解决的核心思路:层次过滤方法
    复杂度:过滤器1 < 过滤器2 < 过滤器3 < 过滤器4 < … < 余弦相似度的复杂度

    如图:通过第一层过滤,我们现在只有100个 < 问题,答案 >对,再经过一层过滤假设我们只有10个< 问题,答案 >对(蓝色圆柱体)
    这个复杂度:2 x 过滤器复杂度 + 10 x 余弦相似度复杂度
    一般过滤器复杂度很低,我们可以忽略,只考虑(10 x 余弦相似度复杂度)
    在这里插入图片描述
    那么这个过滤如何做呢???,那么就要用到经典的倒排序方法

    2.倒排表

    到排表是搜索引擎的核心架构

    假设我们爬取了4个文档,里面的内容如下
    基于4个文档,写出我们的词库 [我们,今天,运动,昨天,上,课,什么]
    统计词库中的每个单词出现在哪些文档中,显然 我们 出现在[doc1,doc2] 中
    在这里插入图片描述
    这样我们就可以把文档以到排表的方式存储了,这样做有什么优点呢???
    假如用户输入:我们 上课
    如果没有到排表,则只能一篇一篇的去搜索文档中 是否既包含我们又包含上课,这样复杂度太高了
    有了到排表:我们知道 我们[Doc1, Doc2], 上 [ Doc3,Doc4], 课[Doc3,Doc4], 如果有交集,我们可以直接返回交集,如果没有交集,那么直接返回
    并集[ Doc1,Doc2, Doc3,Doc4]

    3. 应用

    在这里插入图片描述
    词库: [ how do you like NLPCamp]
    统计
    How: [q1,q2,q6,q56,q89] # q1 指 question1
    do : [q3,q11,q23,q34,…]

    最后提取交集或者并集做过滤

    展开全文
  • 信息检索,倒排记录的合并算法实现,用户通过提示输入两个倒排记录,系统自动实现倒排记录的合并,并将合并结果输出。
  • 004开业前营运工作倒排表.zip
  • 为了进一步缩短查询时间,通过对当前索引文件自索引结构的分析,设计了倒排链表的多层自索引结构。此结构以定长元组为单位,使用迭代的方法提取数据段同步点形成上层自索引;在此基础上,实现了索引压缩与查询系统。...
  • 什么是倒排索引呢?索引我们都知道,就是为了能更快的找到文档的数据结构,比如给文档编个号,那么通过这个号就可以很快的找到某一篇文档,而倒排索引不是根据文档编号,而是通过文档中的某些个词而找到文档的索引...

    搜索引擎最核心的技术, 倒排索引技术,倒排索引可能需要分成几篇文章才说得完,我们先会说说倒排索引的技术原理,然后会讲讲怎么用一些数据结构和算法来实现一个倒排索引,然后会说一个 索引器怎么通过 文档来生成一个倒排索引。

    什么是倒排索引呢?索引我们都知道,就是为了能更快的找到文档的数据结构,比如给文档编个号,那么通过这个号就可以很快的找到某一篇文档,而倒排索引不是根据文档编号,而是通过文档中的某些个词而找到文档的索引结构。

    倒排索引技术简单,高效,简直是为搜索引擎这种东西量身定做的,就是靠这个技术,实现一个搜索引擎才成为可能,我们也才能在海量的文章中通过一个关键词找到我们想要的内容。

    我们看个例子,有下面的几个文档:

    文档编号文档内容
    1这是一个Go语言实现的引擎
    2PHP是世界上最好的语言
    3Linux是C语言和汇编语言实现的
    4谷歌是一个世界上最好的搜索公司

    直观的看,我们通过编号1,2,3,4可以很快的找到文档,但是我们需要通过关键词找文档,那么把上面那个表格稍微变化一下,就是倒排索引了

    倒排表(倒排索引)【只列出了部分关键词】

    关键词文档编号
    Go1
    语言1,2,3
    实现1,3
    搜索4
    引擎1
    PHP2
    世界2,4
    最好2,4
    汇编3
    公司4
    这样就非常好理解了吧,实际上倒排索引就是把文档的内容切词以后重新生成了一个表格,通过这个表格,我们可以很快的找到每个关键词对应的文档,好了,没有了,到这里,就是倒排索引的核心原理,也是搜索引擎最基础的基石,不管是谷歌还是某度,最核心的东西就是这两个表格,没这两表格,啥都干不了。

    看上去很简单吧,好吧,我们现在来模拟搜索引擎进行一次搜索,比如,我们键入关键词:搜索引擎

    1. 首先将 “搜索引擎” 这个词进行分词:搜索/引擎;
    2. 我们在表格2中查到 “搜索” 这个词出现在第4行, “引擎” 这个词出现在第5行;
    3. 找到第4行的第2列、第5行的第2列,把文档编号找出来,是1和4
    4. 去第一个表格通过文档编号把每个文档的实际内容找出来
    5. 将1和4的结果显示出来
    6. 搜索完成

    上面就是搜索引擎的最基础的技术了,如果来设计一个数据结构和算法来实现表2就成了搜索引擎技术的关键。
    在这里插入图片描述
    在实现数据结构和算法之前,我们需要知道搜索引擎搜索的是海量的数据,一般的中型电商的数据都是几十上百G的数据了,所以这个数据结构应该是存储在本地磁盘的而不是在内存中的,基于以上的考虑,为了快速搜索,要么自己实现cache来缓存热数据,要么考虑使用操作系统的底层技术MMAP,鉴于我自己实现的cache不见得(基本上是不太可能)比操作系统做得好,所以我使用的是MMAP。




    参考资料:
    搜索之倒排索引

    展开全文
  • 倒排表

    2020-03-26 12:01:42
  • Lucene倒排索引简述 之倒排表

    千次阅读 2018-10-09 20:31:55
    本篇博客将继续剖析Lucene关于倒排索引实现有另一个核心内容,倒排表(Postings)。我一直觉得Postings内容相对而言是比较简单,虽然内容很多,但是Lucene的官方文档讲得也非常详细了。如果对Lucene文档上的描述文件...
  • 倒排索引

    2016-02-09 01:07:59
    倒排索引的实现。 一个文件含有几个文件的名字,打开这个文件之后读其他文件的内容,将内容出现的文件号输出。
  • 给出了一个基于音节混淆网络的语音文档内容检索系统,提出了一种基于两阶段解码的查询自动扩展方法,首先通过Viterbi解码算法在混淆音节网格上计算混淆音节的似然得分,然后利用A*解码算法从音节格上产生易混淆的...
  • 小程序描述:输入两个倒排记录,求两个倒排记录的交集 跳表指针合并算法伪代码如下所示:   功能描述: ①运行程序,看到提示“请输入词项word1:”,输入某个倒排记录的词项。 ②运行程序,看到提示“请...
  • 针对当前在最频繁项集挖掘方面的不足, 将集合论引入倒排表以对其进行改进, 然后以此为基础提出了几个命题和推论, 并结合最小支持度阈值动态调整策略, 提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法, ...
  • 查找——索引顺序表和倒排表

    千次阅读 2020-06-26 21:12:52
    查找8.3 索引顺序表和倒排表8.3.1 索引顺序表 8.3 索引顺序表和倒排表 当数据表中的数据元素个数n很大时,如果用顺序查找结构,则查找效率极低。如果采用有序表存储形式的折半查找,则为了维持数据表的有序性,时间...
  • 针对当前在最频繁项集挖掘方面的不足,将集合论引入倒排表以对其进行改进,然后以此为基础提出了几个命题和推论,并结合最小支持度阈值动态调整策略,提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法,...
  • IT项目研发-倒排计划.xlsx
  • ES中的倒排索引是什么

    千次阅读 2022-02-24 17:06:26
    倒排索引,是通过分词策略,形成了词和文章的映射关系表,也称倒排表,这种词典 + 映射表即为倒排索引。 其中词典中存储词元,倒排表中存储该词元在哪些文中出现的位置。 有了倒排索引,就能实现 O(1) 时间...
  • 参考资料-004开业前营运工作倒排表.zip
  • Boolean Retrival(布尔检索) and Posting Lists(倒排索引)问题描述利用文档和词项的布尔关系建立倒排索引,根据倒排索引进行布尔表达式查询.这里只实现AND操作.布尔检索布尔检索模型React了文档和词项集合的...
  • 今天小编就为大家分享一篇python 实现倒排索引的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 王斌老师讲课课件,仅供个人保存,请勿下载。。。。。。。。
  • 基于改进倒排表和集合论的TOP-N最频繁项集挖掘算法
  • 倒排索引 和 倒排表

    千次阅读 2015-06-09 14:45:18
    什么我们要说倒排索引呢?   因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!  在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字...
  • 关于倒排索引的总结

    千次阅读 2019-12-18 17:05:54
    那么什么是倒排索引呢?在知乎上看到一个讲解elasticsearch的倒排索引的帖子。 链接是:https://zhuanlan.zhihu.com/p/33671444 为什么说elasticsearch的倒排索引的检索速度是比关系型数据库的索引查新更快...
  • 倒排索引的英文原名是Inverted index,大概因为Invert有颠倒的意思,所以就被翻译成了倒排,然后我们就会在字面上出现误解:很容易让人理解为从A-Z颠倒成Z-A。其实并不是字面上的意思。 倒排索引源于实际应用中需要...
  • 倒排索引是什么

    千次阅读 2019-03-04 00:11:34
    倒排索引是什么 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最...
  • 所有索引项的集合构成该文件的索引。保存在磁盘上的索引又称索引文件。索引技术是组织大型数据库以及磁盘文件的一种重要技术。索引按照结构可以分为线性索引,树形索引和多级索引。所谓线性索引就是将索引项集合...
  • 推荐系统实战:用户倒排索引的构建
  • MapReduce倒排索引代码

    2019-03-14 19:17:16
    倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted ...
  • 正排索引与倒排索引的理解

    千次阅读 2021-02-05 06:54:20
    前言最近在学习调研ElasticSearch,ES是一款热度较高的开源搜索服务器,能够提供近实时的数据全文检索功能,而实现检索功能一个其中较为重要的思想就是使用倒排索引,之所以成为倒排,与我们关系型数据库如Mysql的正...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 57,757
精华内容 23,102
关键字:

倒排表是什么