es_倒排索引详解 男娘i 2024-03-26 18:29 67阅读 0赞 ## 1.正向索引 ## > 正向索引(正排索引):正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。 > “文档1”的ID > 单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;…………。 > “文档2”的ID > 此文档出现的关键词列表。 > ![在这里插入图片描述][c7206784bd504c42892660afe8c3ead4.png] > 正排表结构如图1所示,这种组织方法在建立索引的时候结构比较简单,建立比较方便且易于维护;因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。 > 尽管正排表的工作原理非常的简单,但是由于其检索效率太低,除非在特定情况下,否则实用性价值不大。 ## 2、 反向索引 ## > 反向索引(倒排索引):倒排表以字或词为关键字进行索引,表中关键字所对应的记录表项记录了出现这个字或词的所有文档,一个表项就是一个字表段,它记录该文档的ID和字符在该文档中出现的位置情况。 > 由于每个字或词对应的文档数量在动态变化,所以倒排表的建立和维护都较为复杂,但是在查询的时候由于可以一次得到查询关键字所对应的所有文档,所以效率高于正排表。在全文检索中,检索的快速响应是一个最为关键的性能,而索引建立由于在后台进行,尽管效率相对低一些,但不会影响整个搜索引擎的效率。 > 倒排索引的结构如下: > “关键词1”:“文档1”的ID,“文档2”的ID,…………。 > “关键词2”:带有此关键词的文档ID列表。 ![在这里插入图片描述][f877b3e28fc34ce09148f1fa999b000f.png] ## 3、倒排索引介绍 ## ### 3.1.单词——文档矩阵 ### > 单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图1展示了其含义。下图的每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系。 > ![在这里插入图片描述][f3f4f1b5800f4659b9dcbb16b4722248.png] > 从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其它单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过单词1,而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。 > 搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式,所以本文主要介绍“倒排索引”的技术细节。 ### 3.2.倒排索引基本概念 ### > 文档(Document):一般搜索引擎的处理对象是互联网网页,而文档这个概念要更宽泛些,代表以文本形式存在的存储对象,相比网页来说,涵盖更多种形式,比如Word,PDF,html,XML等不同格式的文件都可以称之为文档。再比如一封邮件,一条短信,一条微博也可以称之为文档。在本书后续内容,很多情况下会使用文档来表征文本信息。 > 文档集合(Document Collection):由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。 > 文档编号(Document ID):在搜索引擎内部,会将文档集合内每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识,这样方便内部处理,每个文档的内部编号即称之为“文档编号”,后文有时会用DocID来便捷地代表文档编号。 > 单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。 > 倒排索引(Inverted Index):倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。 > 单词词典(Lexicon):搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。 > 倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。 > 倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。 > 关于这些概念之间的关系,通过下图可以比较清晰的看出来。 ![在这里插入图片描述][b27a855d68b54a26955bd007f7f116e9.png] ### 3.3.倒排索引简单实例 ### > 倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。 > 假设文档集合包含五个文档,每个文档内容下图所示,在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。 ![在这里插入图片描述][cac49e98d9064746b66db8170137f65e.png] > 中文和英文等语言不同,单词之间没有明确分隔符号,所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流,为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引(参考图3-4)。在图4中,“单词ID”一栏记录了每个单词的单词编号,第二栏是对应的单词,第三栏即每个单词对应的倒排列表。比如单词“谷歌”,其单词编号为1,倒排列表为\{1,2,3,4,5\},说明文档集合中每个文档都包含了这个单词。 ![在这里插入图片描述][937a7f861c304b0ea5f2f3719836b140.png] > 之所以说图4所示倒排索引是最简单的,是因为这个索引系统只记载了哪些文档包含某个单词,而事实上,索引系统还可以记录除此之外的更多信息。图5是一个相对复杂些的倒排索引,与图4的基本索引系统比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。在图5的例子里,单词“创始人”的单词编号为7,对应的倒排列表内容为:(3:1),其中的3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次,其它单词对应的倒排列表所代表含义与此相同。 > 实用的倒排索引还可以记载更多的信息,图6所示索引系统除了记录文档编号和单词频率信息外,额外记载了两类信息,即每个单词对应的“文档频率信息”(对应图6的第三栏)以及在倒排列表中记录单词在某个文档出现的位置信息。 ![在这里插入图片描述][d46f405c4a7b43a6a78181f6888804cd.png] [c7206784bd504c42892660afe8c3ead4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c240f628003a48a28e7a27f1b25f9498.png [f877b3e28fc34ce09148f1fa999b000f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b2d39016b5564583b53e1f525bf1a09c.png [f3f4f1b5800f4659b9dcbb16b4722248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0b7a10d1f8b94fefa66392c37335e2cb.png [b27a855d68b54a26955bd007f7f116e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8dc1b329e1a243d5a91361a65efbb672.png [cac49e98d9064746b66db8170137f65e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4964bd689ebc4152b5c5d7b6cce6a0f9.png [937a7f861c304b0ea5f2f3719836b140.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6b4338e52e21434ea4d0d48e469253a1.png [d46f405c4a7b43a6a78181f6888804cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1df8464d792a4277b2aa51308fb88168.png
相关 es_倒排索引详解 1.正向索引 > 正向索引(正排索引):正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。 男娘i/ 2024年03月26日 18:29/ 0 赞/ 68 阅读
相关 倒排索引 倒排索引的核心组成:(包含两个部分) 单词词典(Term Dictionary):记录所有文档的单词,记录单词到倒排列表的关联关系 单词词 Myth丶恋晨/ 2023年07月03日 03:21/ 0 赞/ 27 阅读
相关 正排索引和倒排索引理解详解 正排索引和倒排索引理解详解 一、正排索引 二、 倒排索引 三、为什么搜索引擎选用倒排索引? 四、倒排索引优点 古城微笑少年丶/ 2022年12月08日 05:17/ 0 赞/ 184 阅读
相关 倒排索引 倒排索引是 es 中非常重要的索引结构,是从文档词项到文档 ID 的一个映射过程。 8.1 "正排索引" 我们在关系型数据库中见到的索引,就是“正排索引”。 8.2 灰太狼/ 2022年10月31日 14:59/ 0 赞/ 221 阅读
相关 深入理解--ES之倒排索引 正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。 在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词 旧城等待,/ 2022年10月24日 05:56/ 0 赞/ 129 阅读
相关 倒排索引 1.什么是倒排索引 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是 ╰半夏微凉°/ 2022年08月27日 11:42/ 0 赞/ 290 阅读
相关 倒排索引 倒排索引简单地就是:根据单词,返回它在哪个文件中出现过,而且频率是多少的结果。这就像百度里的搜索,你输入一个关键字,那么百度引擎就迅速的在它的服务器里找到有该关键字的文件,并根 我不是女神ヾ/ 2022年07月30日 13:25/ 0 赞/ 259 阅读
相关 倒排索引 创建两个文件数据,并上传到hdfs data file edit file file view search data2 abc - 日理万妓/ 2022年06月06日 04:41/ 0 赞/ 348 阅读
相关 倒排索引 1.单词——文档矩阵 单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图3-1展示了其含义。图3-1的每列代表一个文档,每行代表一个单词,打对勾 我不是女神ヾ/ 2022年05月22日 06:47/ 0 赞/ 322 阅读
相关 倒排索引 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的... 小灰灰/ 2020年05月01日 19:45/ 0 赞/ 923 阅读
还没有评论,来说两句吧...