`

《Introduce to IR》布尔检索模型

阅读更多

该系列文章是《An Introduce to Information Retrieval》Chapter 1 的读书笔记。

 

 

IR的概念很广泛,即使从钱包中拿出一张信用卡并输入卡号也是一种形式的信息检索。在学术领域,我们这样定义IR:


       信息检索(IR)就是一种从大量数据集合中(通常指存储在计算机中文档)寻找满足信息需求的非结构化(通常指文本)得数据(通常指文档)。

 

 

布尔检索模型(Boolean Retrieval)

 

要点: (1) 倒排/反向索引模型  inverted indexes

          (2) 简单的布尔表达式如何处理这些索引

 

1.1  词—文档的关联矩阵索引  a term-document matrix

 

(1) Unix/Linux  grep- 命令

 

      这个命令或许大家都用过,它是Unix/Linux中用于在指定文件中查找特定的搜索字符串的命令。它的原理是利用正则表达式 在文档集合中进行线性顺序扫描(sort of linear scan)。 这种方式对于现代计算机的运行速度而言,在有限的数据规模下做简单的查询足够应付了。

 

(2) Web data 的搜索面临的现实问题

 

      ▲ 网络在线数据量(web data/online data)巨大,其增长的速度远大于计算机的硬件发展速度。如何快速的检索需要查询的内容? 这一点线性顺序扫描时永远做不到的。

      ▲ web搜索面临的是广大用户群,其查询表达式的方式灵活多样(并不一定是布尔表达式)。甚至有的时候并没有准确的查询含义。比如查询query: Romans NEAR courtyman。 这里的NEAR到底是指Romans,courtyman这两词需要在文章中同一个句子里出现,还是相隔若干词。如何更好的响应用户的灵活多变的查询方法,提供更加人性化得服务呢?

      ▲ 检索结果的排序问题也是一个现实问题。用户需要看到的是最满意的答案,那么查询返回的若干文档,到底哪些与用户查询最相关呢?

 

(3)布尔模型的词—文档关联矩阵索引模型

 

       线性顺序扫面对于web data来说是不可能的。目前,解决高效检索大量非结构化的信息的公认最好手段就是建立索引(indexes) 。下面就是一个简单的索引模型——关联矩阵。

 

       1. 词—文档关联矩阵  如下图,列表示文档,行表示文档中的词。

 

 

           其中如果Term1出现在Doc1中,则矩阵(1,1)标示为1,否则为0。

 

       2. 建立布尔查询表达式(boolean query)。  Antony and Brutus not Caesar 也就是我们需要找到包含Antony ,Brutus同时不包含Caesar 词语的文档。

       3. 使用位运算:    Antony and Brutus not Caesar =  110001 & 110100 & (~110111) =000000. 很可惜,一篇都没有。

 

(4) 关联矩阵模型的缺陷

 

        上面这个简单索引模型并不适合Web data的检索。对于大数据量而言,这个矩阵实在是太大了,不可能全部放进内存。而且更严重的是矩阵太稀疏了。况且对于检索结果的排序问题也是解决不了的。

 

 

1.2  倒排索引  inverted index

 

倒排索引绝对是一个伟大的发现。当前很多搜索引擎或者开发包都使用了这个模型,比如Lucene。

 

(1) 倒排索引结构: 1. 词语组成的字典结构 ——Dictionary   如下图左侧

                            2. 文档组成的位置链 —— Postiong  如下图右侧

        

(2) 创建过程

      1. 将每一个文档中的词语与文档ID(唯一标示文档)组成一个Pair,存入index。如左图A

      2. 将index中的词语按字典序排序。如中图B

      3. 如果相同词语来自同一个文档,则只记录一次。相同词语来自不同文档,则合并成进posting。如右图C

 

(3) 索引存储方法

 

      很显然,对于倒排索引,我们必须把Dictionary和Posting都存储起来。一般Dictionary可以全部加载进内存中,而Posting存放在磁盘中,当需要查找Posting的时候,再会将某一个词语所指向的Posting加载进内存。

 

      Dictionary in menory

             很多时候使用Hash表的形式,也用连续存储的数组结构。

      Posting in menory: 

            1. 单链表( singly linked lists) ,在将新文档插入Posting中的时候付出的代价较少。这一点很适合高频率从网上抓取内容并更新文档。

            2. 可变长数组(variable length arrays),节约了指针所需要的额外空间。并且对于拥有内存缓存区的现代计算机而言,连续内存的结构无疑会增加查询的速度。

            3. 跳跃表(skip lists),一种很先进的存储结构。除了需要额外耗费一些指针空间之外,查找效率极高。Lucene就是用了这种结构。

 

1.3  布尔查询表达式的处理

 

(1)  Posting的合并算法(merge algorithm)

 

       假如我们需要在倒排索引上查找这样一个表达式: Brutus AND Calpurnia。很明显我们需要下面几个步骤:

       1. 在Dictionary中定位Brutus.

       2. 检索Brutus所指向的Posting:  1、2、4、11、31....

       3. 在Dictionary中定位Calpurnia.

       4. 检索Calpurnia所指向的Posting:  2、31、54....

       5. 合并两个Posting.

 

       对于两个有序表的合并算法,可以采用下面的算法: 时间复杂度为O(m+n)

//指针P1,P2分别指向两个Posting链
Posting intersect(p1,p2){

        Posting answer;
        while(p1!=null&&p2!=null){
                if(p1==p2){
                     add(answer, p1->docID);
                     p1=p1->next;
                     p2=p2->next;
                }
                if(p1>p2)  p2=p2->next;
                if(p1<p2)  p1=p1->next;

        }
}
 

(2) 布尔表达式的优化

 

      Brutus AND Caesar AND Calpurnia

 

      表达式的AND顺序按照每一个词的文档频率递增进行优化。 比如 Brutus‘s Ducument Frequence(Brutus所在文档的数量,符号表示DF(Brutus))。DF(Brutus)=1000,DF(Caesar)=10000,DF(Calpurnia)=100。那么查询表达式可以优化成: (Calpurnia AND Brutus) AND Caesar。

 

       理由很简单,Calpurnia AND Brutus的时间复杂度(利用上面的合并算法)为O(1100),其合并后的中间结果R=DF(Calpurnia AND Brutus)<DF(Calpurnia)=100。此时将这个中将结果R AND Caesar 的时间复杂度不会超过O(100+10000)。而且最后结果页不会操作DF<DF(Calpurnia AND Brutus)<100。总的时间复杂度为O(1100+10100)=O(11200)

       如果使用原表达式,Brutus AND Caesa的时间复杂度为O(11000),且中间结果为R=DF( Brutus AND Caesa )< DF(Brutus)=1000。然后R AND Calpurnia的时间复杂度可能达到O(1000+100)。两次AND操作的总时间复杂度为O(11000+1100)=O(12100)

       明显优化之后的时间复杂度会少。如果查询表达式更长,查询词语的DF差距更大,那么优化的效率会更明显

 

       根据上面的优化原理,对于更加复杂的查询表达式(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)。我们一般都会估算OR操作两个词的DF之和的数量,然后进行AND递增排序。

 

       事实上,对于任意的布尔表达式,每一次操作的中间结果(intermediate)越小越好。 这是我们进行优化的原则所在。

 

(3) 自然语言查询 AND 布尔查询表达式

 

       为什么我们对布尔表达式的操作只将AND,很少说OR或NOT呢?

 

       在搜索引擎实际应用的环境下,用户的查询都是自然语言叙述的,很少直接用布尔表达式(你不能要求所有的用户必须逻辑思维缜密吧)。那么对于用户提交的这些查询,都是纯粹的合并操作。

 

       正是这个原因,现实中很多搜索引擎的应用已经退化成了只有AND的布尔模型了。

 

 

分享到:
评论

相关推荐

    Introduce to Algorithms, A Creative Approach

    Introduce to Algorithms, A Creative Approach .英文版

    introduce to NS2

    4. **丰富的网络模型**:包括但不限于TCP/IP协议栈、各种路由协议、多媒体应用等。 5. **脚本语言支持**:采用Tcl(Tool Command Language)作为主要的脚本语言,简化了网络场景的配置过程。 #### 三、NS2的应用...

    introduce to D3D Game Programming code

    2. **顶点和索引缓冲区**:这是3D图形的基础,用于存储模型的数据,如位置、颜色、纹理坐标等。了解如何创建、填充和使用这些缓冲区对于构建3D场景至关重要。 3. **渲染管线**:Direct3D使用渲染管线处理图形数据,...

    introduce to linux.html

    Linux操作系统介绍 Linux,一种基于开源的类Unix操作系统,由芬兰程序员林纳斯·托瓦兹在1991年创建,至今已发展成为一个全球性的、充满活力的生态系统,被广泛应用于服务器、超级计算机、嵌入式设备以及移动设备等...

    Introduce to Java Programming 8th

    《Introduction to Java Programming》第8版是一本深入浅出的Java学习教材,为初学者提供了全面的Java编程知识。这本书涵盖了从基础语法到高级特性的全方位教学,旨在帮助读者掌握Java编程的核心技能。 在本书中,...

    Introduction to linear optimization

    在“Introduction to Linear Optimization”一书中,对线性规划的几何理解进行了介绍,提供了线性规划问题的理论基础。 2. 单纯形方法(The Simplex Method):这是求解线性规划问题的经典算法之一,由乔治·丹齐格...

    Introduction to Lens Design

    Introduction to Lens Design

    Introduce to EIB Control Network and Protocol

    EIB(European Installation Bus,欧洲安装总线)控制网络及协议是一个专为建筑自动化和管理系统设计的通信网络和协议。EIB的目的是使建筑物内的各种电器和设备能够通过一个统一的控制网络进行通信和协调工作,以...

    team introduce.key

    team introduce.key

    Introduction to lens design.pdf

    内容可能包括如何在ZEMAX中建立光学模型、进行光线追迹、优化系统性能、进行公差分析等。 6. 仿真与优化:在光学系统设计完成后,需要进行仿真分析来验证系统性能是否满足设计要求。这可能包括像质评价、公差分析、...

    Introduction to Linear Algebra

    从网上看到Introduction to Linear Algebra这本书(Algebra_Gilbert Strang),介绍的清晰易懂且很到位。就搜集了一些。包括第三版、第四版和讲课笔记。听说第三版比较经典,暂时只上传了第三版和笔记。虽然是英文的...

    Introduce To Design Pattern(设计模式介绍)

    这是对设计模式的简单简绍,希望对大家有用

    Introduction to Linear Algebra.pdf

    Gilbert Strang是一位著名的数学教授,他在麻省理工学院(Massachusetts Institute of Technology,MIT)执教多年,他所编写的《线性代数导论》(Introduction to Linear Algebra)就是一本广受好评的教材,对学习...

    Introduciton to Linear Algebra

    Gilbert Strang's textbooks have changed the entire approach to learning linear algebra -- away from abstract vector spaces to specific examples of the four fundamental subspaces: the column space and ...

    [Introduction.to.Tornado(2012.3)].Michael.Dory.文字版.pdf

    《Introduction to Tornado》是Michael Dory、Adam Parrish和Brendan Berg三人所著,是一本关于Tornado网络服务器的入门与应用概览书籍。Tornado是一个开源的网络框架,最初是为FriendFeed公司的实时服务设计的,...

    Introduction to Classical Mechanics - David Morin.pdf

    根据所提供的文件信息,本书《Introduction to Classical Mechanics - David Morin》涵盖经典力学的基础知识和一些高级主题,以下是本书中的知识点汇总: 1. 经典力学的入门主题:书中包含了经典力学中最基础的主题...

    IntroduceIntroduceIntroduceIntroduce

    在当今职场竞争激烈的环境下,个人的自我介绍对于面试官来说,往往是了解应聘者的第一窗口。HHJ,一位26岁的年轻人,在面试中如何做好自我介绍,显得尤为重要。他将自己描述为勤奋、开放、随和、有责任感的人,这样...

    IR Remote Control introduce and protocol英语文献

    此外,红外发光二极管(IR LED)易于制造且价格低廉,这也促成了红外遥控技术的广泛应用。 尽管人类无法直接看到红外光,但我们可以通过其他方式使其可见。例如,使用视频摄像头或数码相机就可以“看到”红外光。...

Global site tag (gtag.js) - Google Analytics