XML地图 深圳SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO教程 » 搜索引擎索引原理

搜索引擎索引原理

2018-10-10 | 人围观 | 关键词:


  搜索引擎索引原理
 

  “吾有三剑,唯子所择;皆不能杀人,且先言其状。一曰含光,视之不可见,运之不知有。其所触也,泯然无际,经物而物不觉。二曰承影,将旦昧爽之交,日夕昏明之际,北面而察之,淡淡焉若有物存,莫识其状。其所触也,窃窃然有声,经物而物不疾也。三曰宵练,方昼则见影而不见光,方夜见光而不见形。其触物也,然而过,随过随合,觉疾而不血刃焉。此三宝者,传之十三世矣,而无施于事。匣而藏之,未尝启封。”
 

  索引其实在日常生活中是很常见的,比如书籍的目录就是一种索引结构,目的是为了让人们能够更快地找‍到相关章节内容。再比如像hao123这种类型的导航网站本质上也是互联网页面中的索引结构,目的类似,也是为了让用户能够尽快找到有价值的分类网站。
 

  在计算机科学领域,索引也是非常常用的数据结构。其根本目的是为了在具体应用中加快查找速度。比如在‍数据库中,在很多高效数据结构中,都会大量采用索引来提升系统效率。
 

  具体到搜索引擎,索引更是其中最重要的核心技术之一,面对海量的网页内容,如何快速找到包含用户查询词的所有网页?倒排索引在其中扮演了关键的角色。本章主要讲解与倒排索引相关的技术。‍
 

  3.1 索引基础
 

  本节通过引入简单实例,介绍与搜索引擎索引有关的一些基本概念,了解这些基本概念对于后续深入了解索引的工作机制非常重要。
 

  3.1.1 单词—文档矩阵
 

  单词—文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图3-1展示了其含义。图3-1的每列代表一个文档,每行代表一个单词,打对钩的位置代表包含关系。
 

  
 

  从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其他单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过词汇1,而其他文档不包含词汇1。矩阵中其他的行列也可做此种解读。
 

  搜索引擎的索引其实就是实现单词—文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型,比如倒排索引、签名文件、后缀树等方式。但是各项实验数据表明,倒排索引是单词到文档映射关系的最佳实现方式,所以本章主要介绍倒排索引的技术细节。
 

  3.1.2 倒排索引基本概念
 

  在本小节,我们会解释倒排索引常用到的一些专用术语,为了表达的便捷性,在本书后续章节会直接使用这些术语。
 

  · 文档(Document):一般搜索引擎的处理对象是互联网网页,而文档这个概念要更宽泛些,代表以文本形式存在的存储对象。相比网页来说,涵盖更多形式,比如Word、PDF、html、XML等不同格式的文件都可以称为文档,再比如一封邮件、一条短信、一条微博也可以称为文档。在本书后续内容中,很多情况下会使用文档来表征文本信息。
 

  · 文档集合(Document Collection):由若干文档构成的集合称为文档集合。比如海量的互联网网页或者说大量的电子邮件,都是文档集合的具体例子。
 

  · 文档编号(Document ID):在搜索引擎内部,会为文档集合内每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识,这样方便内部处理。每个文档的内部编号即称为文档编号,后文有时会用DocID来便捷地代表文档编号。
 

  · 单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。
 

  · 倒排索引(Inverted Index):倒排索引是实现单词—文档矩阵的一种具体存储形式。通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:单词词典和倒排文件。
 

  · 单词词典(Lexicon):搜索引擎通常的索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。
 

  · 倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。
 

  · 倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称为倒排文件,倒排文件是存储倒排索引的物理文件。
 

  关于这些概念之间的关系,通过图3-2可以比较清晰地看出来。
 

  
 

  3.1.3 倒排索引简单实例
 

  倒排索引从逻辑结构和基本思路上讲非常简单。下面我们通过具体实例来进行说明,使读者能够对倒排索引有一个宏观而直接的感受。
 

  假设文档集合包含5个文档,每个文档内容如图3-3所示,在图中最左端一栏是每个文档对应的文档编号,我们的任务就是对这个文档集合建立倒排索引。
 

  
 

  中文和英文等语言不同,单词之间没有明确的分隔符号,所以首先要用分词系统将文档自动切分成单词序列,这样每个文档就转换为由单词序列构成的数据流。为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引(参考图3-4)。在图3-4中,“单词ID”一列记录了每个单词的单词编号,第2列是对应的单词,第3列即每个单词对应的倒排列表。比如单词“谷歌”,其单词编号为1,倒排列表为{1,2,3,4,5},说明文档集合中每个文档都包含了这个单词。
 

  
 

  之所以说图3-4所示的倒排索引是最简单的,是因为这个索引系统只记载了哪些文档包含某个单词,而事实上,索引系统还可以记录除此之外的更多信息。图3-5是一个相对复杂些的倒排索引,与图3-4所示的基本索引系统相比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中出现的次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是一个很重要的计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。在图3-5所示的例子里,单词“创始人”的单词编号为7,对应的倒排列表内容有(3;1),其中3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次,其他单词对应的倒排列表所代表的含义与此相同。
 

 
 

  实用的倒排索引还可以记载更多的信息,如图3-6所示的索引系统除了记录文档编号和单词频率信息外,额外记载了两类信息,即每个单词对应的文档频率信息(对应图3-6的第3列)及单词在某个文档出现位置的信息。
 

  
 

  文档频率信息代表了在文档集合中有多少个文档包含某个单词,之所以要记录这个信息,其原因与单词频率信息一样,这个信息在搜索结果排序计算中是一个非常重要的因子。而单词在某个文档中出现位置的信息并非索引系统一定要记录的,在实际的索引系统里可以包含,也可以选择不包含这个信息,之所以如此是因为这个信息对于搜索系统来说并非必需,位置信息只有在支持短语查询的时候才能够派上用场。
 

  以单词“拉斯”为例,其单词编号为8,文档频率为2,代表整个文档集合中有两个文档包含这个单词,对应的倒排列表为{(3;1;<4>),(5;1;<4>)},其含义为在文档3和文档5出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第4个单词是“拉斯”。
 

  如图3-6所示的倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此,区别无非是采取哪些具体的数据结构来实现上述逻辑结构。
 

  有了这个索引系统,搜索引擎可以很方便地响应用户的查询,比如用户输入查询词“Facebook”,搜索系统查找倒排索引,从中可以读出包含这个单词的文档,这些文档就是提供给用户的搜索结果,而利用单词频率信息、文档频率信息即可对这些候选搜索结果进行排序,计算文档和查询的相似性,按照相似性得分由高到低排序输出,此即为搜索系统的部分内部流程,具体实现方案本书第5章会做详细描述。
 

相关内容推荐:

Top