seo培训

百科首页

初级SEO

当前位置:首页> 初级SEO教程 >倒排索引

名 称:倒排索引
别 称:inverted index
简 述:搜索引擎的重要步骤,文章被索引才能参与排名。
详 述:

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


倒排索引,搜索引擎工作原理中的重要的步骤,被收录的文章只有被索引,才能参与排名。


概述


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


1)海量数据:搜索引擎面对的是海量数据,像Google,百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ,面对如此海量数据 ,使得数据库系统很难有效的管理。


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


相关概念及定义


倒排列表概念


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


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


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


倒排索引概念


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


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


一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。现代搜索引擎的索引都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构,“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构。


构建方法


简单法


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


流程描述如下:


1)将文档分析成单词term标记,


2)使用hash去重单词term


3)对单词生成倒排列表


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


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


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

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


合并法


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


如图 归并示意图:


合并流程:


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


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


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


更新策略


更新策略有四种:完全重建、再合并策略、原地更新策略以及混合策略。


完全重建策略:当新增文档到达一定数量,将新增文档和原先的老文档整合,然后利用静态索引创建方法对所有文档重建索引,新索引建立完成后老索引会被遗弃。此法代价高,但是主流商业搜索引擎一般是采用此方式来维护索引的更新(这句话是书中原话)


再合并策略:当新增文档进入系统,解析文档,之后更新内存中维护的临时索引,文档中出现的每个单词,在其倒排表列表末尾追加倒排表列表项;一旦临时索引将指定内存消耗光,即进行一次索引合并,这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序,这样直接顺序扫描合并即可。其缺点是:因为要生成新的倒排索引文件,所以对老索引中的很多单词,尽管其在倒排列表并未发生任何变化,也需要将其从老索引中取出来并写入新索引中,这样对磁盘消耗是没必要的。


原地更新策略:试图改进再合并策略,在原地合并倒排表,这需要提前分配一定的空间给未来插入,如果提前分配的空间不够了需要迁移。实际显示,其索引更新的效率比再合并策略要低。


混合策略:出发点是能够结合不同索引更新策略的长处,将不同索引更新策略混合,以形成更高效的方法。


应用


反向索引数据结构是典型的搜索引擎检索算法重要的部分。


一个搜索引擎执行的目标就是优化查询的速度:找到某个单词在文档中出现的地方。以前,正向索引开发出来用来存储每个文档的单词的列表,接着掉头来开发了一种反向索引。 正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。


实际上,时间、内存、处理器等等资源的限制,技术上正向索引是不能实现的。


为了替代正向索引的每个文档的单词列表,能列出每个查询的单词所有所在文档的列表的反向索引数据结构开发了出来。


随着反向索引的创建,如今的查询能通过立即的单词标示迅速获取结果(经过随机存储)。随机存储也通常被认为快于顺序存储。


小小课堂SEO自学网相关教程:


【TF-IDF算法】SEOer应善用索引创建过程中的加权方法


谷歌移动优先索引-Mobile-first indexing enabled


【百度索引量】索引的作用?索引是什么


索引是什么?索引库和索引量又是什么意思呢


友链互换应理性看待索引量|SEO研究


索引排序规则决定了关键词排名不稳定|SEO排名培训


内蒙古seo【收录索引】搜狗SEO官方指南六


【合肥seo】百度索引量详解


【德州seo】如何检查Google索引统计信息


【荆州seo】新站一个月索引量大量增加的经验分享


石家庄培训网【收录与索引是什么意思】SEO培训教程

额 本文暂时没人评论 来添加一个吧

取消回复发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

倒排索引

  • 自然排名
    搜索引擎分为自然排名和付费排名,SEO是优化自然排名的技术。
  • 蓝帽SEO
    秉承最初互联网的理念,遵循自然规律创造有价值的内容。
  • 收录
    搜索引擎蜘蛛爬行网站页面并抓取,符合要求的页面可以被收录。
  • 404页面
    客制化404页面提升用户体验度
  • 论坛
    供公开讨论的公共集会场所,一般为发帖讨论东西的网站。
  • 百度知道
    一个基于搜索的互动式知识问答分享平台。
  • 302重定向
    用户请求某网址,却暂时地跳转到了另外的一个网址上。
  • 网址规范化
    防止多个URL链接都可以到达某一相同页面导致的权重分散。
  • 信息抓取
    将非结构化的信息从网站中抓取出来保存到结构化的数据库中。
  • 内部链接
    同一个域名之间的链接。
  • Google AdWords
    通过Google关键字广告来推广网站的付费网络推广方式
  • Robots
    搜索引擎中访问网站的时候要查看的第一个文件。
  • PPS
    pay per sale,中文译为“按销售付费”。
  • 隐藏链接
    正常的链接通过一些方法将链接隐藏不让用户看到。
  • 开放目录
    网景所主持的一项大型公共网页目录。
站点搜索
权5分类目录网站
快审50元/站 高权重优质外链 给我发QQ消息
小小课堂SEO自学网,提供SEO培训、SEO诊断和SEO顾问服务。微信:huowuyan

© 2018 小小课堂SEO自学网 , SEO培训_网站优化培训_搜索引擎优化培训 / 冀ICP备15027596号-9

小小课堂SEO百科 - 用心创造有价值的SEO教程