[原]搜索引擎索引之索引基础

标签: Uncategorized | 发表时间:2012-03-12 10:05 | 作者:flychen
出处:http://flychen.com

    

                                                           本文节选自《 这就是搜索引擎:核心技术详解》第三章


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

 

3.1.1单词—文档矩阵

       单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图3-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-2 倒排索引基本概念示意图

 

3.1.3倒排索引简单实例

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

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

                         

                                                                           图3-3 文档集合

 

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

                                      

                                                           图3-4 简单的倒排索引

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

                                                  

                                                                图3-5 带有单词频率信息的倒排索引

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

                                                                                                                                                  
                                        图3-6 带有单词频率、文档频率和出现位置信息的倒排索引

 

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

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

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

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

作者:malefactor 发表于2012-2-13 22:00:10 原文链接
阅读:1857 评论:2 查看评论

from malefactor's 布拉格 http://blog.csdn.net/malefactor/article/details/7256305


您可能也喜欢:

以求医为例谈搜索引擎排序算法的基础原理

Google Panda 更新那点事

| 搜索引擎技术博客

中文搜索引擎技术揭密:排序技术
来自无觅网络的相关文章:

comScore最新搜索引擎统计数据:Google下,Bing/Yahoo上 (@wolfherder)

饭客网络黑客基础入门系列培训教程 (@qyqblog)

华夏黑客联盟菜鸟基础班培训教程 (@qyqblog)

娱友被搜索引擎狂爬。。。 (@huceo)
无觅

相关 [搜索引擎 索引 索引] 推荐:

uSniff:BT种子搜索引擎

- leqoqo - 软件志
一、uSniff相关信息: 1、官方主页:http://www.usniff.com/ 2、简介:uSniff是一个BT种子搜索引擎,简单、易用、实时是其最大的优点,其搜索引擎数据库包含了17个知名种子站点的种子信息,目的是想发展成为世界上最大的BT种子搜索引擎,而且对于每个种子,该搜索引擎都会进行安全认证,以保证用户的正常使用.

资源搜索引擎

- - 不死鸟 - 分享为王官网
易搜 阿里百度夸克网盘搜索. tg中文搜索 电报资源搜索引擎. 千帆搜索 电报资源搜索引擎. 影视搜 影视聚合搜索引擎. 辅助狗 无捆绑软件搜索引擎. 查报告 可查询各行业的分析报告. 学霸盘 课程资料百度网盘. 库问搜索 PDF文献资料搜索.

人眼启发视觉搜索引擎

- feng823 - Solidot
Google上周宣布将支持声音和图片进行搜索,但一家创业公司在图像搜索方面走在了Google前面. 源自伦敦帝国学院研究项目的创业公司Cortexica,开发出视觉搜索工具,通过手机拍摄产品照片,它会自动呈现价格信息. Cortexica已经发布了一个用于比较酒价格的工具WINEfindr. Cortexica的视觉搜索技术是受到了人眼视觉系统的启发,它能识别出一个目标的关键特征,不受方位、大小、光线亮暗的影响.

比较好的学术搜索引擎

- hfut_chen - C++博客-首页原创精华区
     摘要: 1、http://scholar.google.com/. Google学术搜索滤掉了普通搜索结果中大量的垃圾信息,排列出文章的不同版本以及被其它文章的引用次数. 略显不足的是,它搜索出来的结果没有按照权威度(譬如影响因子、引用次数)依次排列,在中国搜索出来的,前几页可能大部分为中文的一些期刊的文章.

Blekko 对搜索引擎的新探索

- thinkingit - 知乎的博客
Blekko 这款搜索产品做的如何. 从目前我的使用过程来看,Blekko还是很让人激动的. 在谈Blekko之前就要先问:为何在搜索这个看似已经垄断的行业还会有人想去分一杯羹,这些小团队能与Google或微软这样的巨头抗衡吗. 比如之前的Powerset,后来的Cuil,和现在的Blekko. 在Google之前Yahoo是靠人工收录网页,Google的算法和蜘蛛革了搜索的命,一直垄断搜索业十余年,而现在随着WEB 2.0的发展,让人又看到了搜索业革命的火种,可以说Blekko就是这样的一个产品.

Mr.Icons:图标icon搜索引擎

- 壮壮爱 - 够趣堂
之前Anliu在如何更换更好的icon文章里面推荐了4个icon搜索引擎,目前部分已经不复存在. 不过Mr.Icons倒是又一个不错的选择,可以搜索图标icon进行下载,有PNG、ico格式以及不同大小提供下载. Mr.Icons还提供图标icon集打包下载,比如动物图标等. 和之前的介绍几款搜索引擎一样,依然不支持中文.

迅搜全文搜索引擎 XunSearch

- Le - 开源中国社区最新软件
迅搜(xunsearch)是采用 C/C++ 基于 xapian 和 scws 开发的全文搜索引擎解决方案,提供 PHP 语言的开发接口. 支持海量数据高速检索,功能强大,简单易用. 本项目旨在帮助一般开发者针对既有的海量数据,快速而方便地建立自己的全文搜索引擎. 全文检索可以帮助您降低服务器搜索负荷、极大程度的提高搜索速度和用户体验.

搜索引擎的特殊用法

- iVane - 崔凯,前端开发
下周组内分享要讨论“工具”,介绍几个搜索引擎的特殊用法,凑凑数:. 通配符,这么搜可以得到“崔凯前端开发”,也能得到“崔凯大连开发” 崔凯*开发. 用于搜索查询词出现在URL中的页面. 由于关键词出现在URL中对排名有一定影响,因此使用inurl:搜索也是定位竞争对手的一种方式. 该指令搜索结果返回的是页面title中包含关键词的页面.

美国购物搜索引擎评测

- - 月光博客
  专注于购物搜索引擎领域的CPCStrategy在其博客中对美国众多流行的购物搜索引擎在2012年第一季度的流量、收入以及转化率等方面进行了全面的分析与对比,其中的一些发现不管是对商家还是消费者都非常有价值. 我们对其进行了编译,希望对大家有帮助.   这项分析的数据样本主要来自CPCStrategy的100多位客户,涵盖约427万次点击,约8.3万张订单,约116万美金的营销成本以及所带来的约787万美金的收入.

如何高效使用搜索引擎

- - IT技术博客大学习
   把搜索词放在双引号中,代表完全匹配搜索,也就是说搜索结果返回的页面包含双引号中出现的所有的词,连顺序也必须完全匹配. bd和Google 都支持这个指令. 例如搜索: “javar高性能程序开发”.    减号代表搜索不包含减号后面的词的页面. 使用这个指令时减号前面必须是空格,减号后面没有空格,紧跟着需要排除的词.